//GitHub https://github.com/vellimole0621
백준 11866번 : 요세푸스 문제 0
(문제 - https://www.acmicpc.net/problem/11866 )
문제 설명 : 숫자 N, K를 받아, N명의 사람이 원순열을 이룰 때. K번째 사람을 제거한다. 사람이 모두 제거될 때까지 반복할 때. 제거되는 사람의 순서를 출력하라
풀이 : N, K를 입력받음 >> N 기준 배열 생성 >> 기준이 될 변수 초기화 >>제거 될 변수 초기화 >> 원 따라 제거(첫 번째) >> while 문 생성해서 조건에 맞춰 반복 제거 (제거한 값은 -1을 곱해서 음수라는 조건으로 매 반복시 무시하고. 제거 횟수가 N가 동일할 때까지 반복) >> 반복한 값 출력
//11866 번
package S2208;
import java.util.*;
public class Solve220826 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
// N 과 K 입력 받기
int N = sc.nextInt();
int K = sc.nextInt();
// N 기준, 배열 생성
int[] N_B = new int[N];
for(int j = 0; j < N; j++){
N_B[j] = j + 1;
}
// 기준이 될 변수 초기화
int num = 0;
int k_num = 1;
// 제거된 값 담을 배열 생성
int[] num_r = new int[N];
// 원 따라 제거
int kill = K-1;
num_r[num] = N_B[kill];
N_B[kill] *= -1;
num++;
while(num != N){
while(k_num != K + 1){
if(kill == N){
kill = 0;
}
if(N_B[kill] < 0){
kill++;
}else{
kill++;
k_num++;
}
}
k_num = 1;
kill--;
if(kill >= N){
kill -= 7;
}
num_r[num] = N_B[kill];
N_B[kill] *= -1;
num++;
}
// 결과 값, 출력
System.out.print("<");
for(int i = 0; i < N-1; i++){
System.out.print(num_r[i]+", ");
}
System.out.print(num_r[N-1]+">");
sc.close();
}
}
어려웠던 점 : 이번에도 반복문을 사용할 때, 너무 많은 반복문을 그냥 사용해서 시간 초과가 발생하였다. 항상 작성할 때에 불필요하게 중복되는 부분이 발생하였는지 체크하자.
'프로그래밍 > Java' 카테고리의 다른 글
[자바 JAVA/알고리즘] 백준 10773번 : 제로 (0) | 2022.08.22 |
---|---|
[자바 JAVA/알고리즘] 백준 1978번 : 소수 찾기 (0) | 2022.08.22 |
[자바 JAVA/알고리즘] 백준 1157번 : 단어 공부 (0) | 2022.08.19 |
[자바 JAVA/알고리즘] 백준 1152번 : 단어의 개수 (0) | 2022.08.19 |
[자바 JAVA/알고리즘] 백준 1105번 : 팔 (0) | 2022.08.19 |