문제 풀이 (JAVA)
import java.util.*;
public class part5_6 {
public static void main(String[] args) {
// 공주 구하기
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int [] a = new int[N];
for(int i=0; i<a.length; i++) {
a[i]=i+1;
}
int K = input.nextInt();
int answer = solution(a,K);
System.out.print(answer);
}
private static int solution(int [] arr, int k) {
int result =0;
Queue<Integer> que = new LinkedList<>();
// 큐 초기값 추가(왕자들의 배열)
for(int i=0; i<arr.length; i++) {
que.add(arr[i]);
}
int num=0;
while(que.size() != 1) { // 큐의 사이즈가 1개가 남을때까지 반복
for(int i=0; i<k; i++) {
if(i != k-1) { // K-1개 추가
num = que.peek();
que.add(num);
}
que.poll(); //K개 제거
}
}
result = que.poll(); // 마지막 큐 결과값 추가
return result;
}
}
주요 핵심 포인트
1. 비교할 배열의 초기 큐 값을 저장한다.
2. 큐의 사이즈가 1이 될때까지 큐의 첫번째 값부터 비교하여 K개만큼 제거하고 K-1개를 마지막 큐에 추가한다.
개선해야할 사항
1. 해당 문제는 순번이 중요한 문제로 실전 문제에서 이와 같은 순번 문제가 나올 시 큐로 풀 수 있도록 생각하도록 하자.
'알고리즘' 카테고리의 다른 글
[선택정렬] 선택 정렬 (인프런 알고리즘 6-1) (0) | 2022.06.27 |
---|---|
[큐] 교육과정 설계(인프런 알고리즘 5-7) (0) | 2022.06.26 |
[스택] 쇠막대기 (인프런 알고리즘 5-5) (0) | 2022.06.26 |
[스택] 후위식 연산(postfix) (인프런 알고리즘 5-4) (0) | 2022.06.20 |
[스택+이차원행렬] 크레인 인형뽑기(카카오) (인프런 알고리즘 5-3) (0) | 2022.06.19 |