문제

입출력

첫 번째 구현 도전(실패)

1. 1~N까지 for ( i = 1부터 N까지)를 돌리고 cnt++시킴
2. cnt가 K가 되면 그때의 i를 큐에 집어넣는다.
3. queue가 다 찰 때까지 이를 반복해야하는데 i가 N이 되었는데 queue가 다 안찼다면 i = i % N 을 해줘서 반복
4. queue가 다 차면 반복문 끝 및 queue 출력

내가 생각했던 방법이 안되었던 이유

예를 들어 N이 7이고 K 가 3일 때
for문을 돌린다고 가정하자
그러면

 for(int i = 1; i<=N; i++){
		cnt++;
        if(cnt == K)
        	queue.offer(i);
            cnt = 0;
         }
         else if(i == N){
         	i = i % N;
         }
          
           ...
    }       

이런식으로 갔을 것이다.
그런데 여기서 문제가 생긴다.

for문을 돌려보면
[1round]
queue.offer(3)
queue.offer(6)

이렇게 되면 2라운드에서 i가 3이나 6일 때는 cnt++;를 하면 안된다.
즉, queue에 이미 들어간 수를 거를 수 없다는 문제점이 생겼다.

이 때문에 flag[] 까지 넣어봐서 해보려고 했는데
이렇게 풀라고 하는 문제가 아닌 것 같아서 철회

두번 째 구현 도전(실패)

이미 큐에 들어간 수를 거르기 위해 링크드리스트에 넣어서 다시 구현을 해보았다.
근데 너무 코드가 더러워지기 시작했다. 계속 이상한 변수만 추가하게 되는..
점점 억지로 답을 위해서만 풀어나가는 느낌이 들어서 철회

하도 안풀려서 결국 구글링..을 했더니..
큐 하나로 풀리는 문제였네..? 눈물나네

구현(성공)

import java.io.*;
import java.util.*;

public class Main {


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
      //  1. 1~N까지 Queue에 offer한다.

      //   2. K - 1 번째까지는 첫 번째 값을 맨 뒤로 보낸다.

      // 3. K번째 일때는 poll해서 출력한다.

      //  4. Queue의 사이즈가 1개일 때까지 반복한다. 
      //(Queue의 요소가 1개면 어차피 그것만 빼서 출력하면 되기 때문)

        Queue<Integer> q = new LinkedList<>();

        // Queue에 1~N까지 값을 offer한다.
        for (int i = 1; i <= N; i++) {
            q.offer(i);
        }


        StringBuilder sb = new StringBuilder();
        sb.append("<");


        while(q.size() !=1){
            // K - 1번째까지는 처음에 있던 값을 맨 뒤로 보낸다.
            for(int i = 0; i < K -1; i++){
                q.offer(q.poll());
            }
            sb.append(q.poll()+", ");
        }

        // Queue의 사이즈가 1일 때는 단순히 poll하면 된다.
        sb.append(q.poll() + ">");
        bw.write(sb.toString() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

내가 너무 좁게 생각하고 있었던 것 같다.
큐를 더 자유롭게 활용하는 능력이 필요하다!!