[자바] 백준 1835 - 카드 (boj java)

문제 : boj1835

 

  이걸 어찌 구해야할지 상당히 난감해보일 수 있다. 그럼 반대로 이미 출력의 답을 알고 있다고 할 때, 이 문제에서 제시된 방법대로 진행할 경우 정말 1,2,3,... 이 순서대로 뜰지 확인해볼 수 있을까? 물론 문제에서 제시된대로 코드를 구현만 하면 확인해볼 수 있다.

 

  그렇다면, 이미 답을 알고있다고 가정하고 시뮬레이션을 돌려보자. 그리고 뽑히는 순서대로 1,2,3... 을 넣어준 후, 답의 출력순서대로 다시 짜맞춰주면 된다. 무슨 말이냐면, 아래 그림을 봐보자.

 

  그리고 자바에서 클래스는 주소값을 기준으로 저 링크를 연결해두기 좋다. 그러니 ?로 된 카드들을 배열에 넣어두고, 해당 값들을 덱에다가 미리 넣어둔다(위 그림의 '1'에서 위쪽 파란거 3개가 배열, 아래쪽이 덱에 들어간걸 뜻함). 이후 실제 문제에서 제시된대로 시뮬레이션을 돌려서 위 그림처럼 역으로 결과값을 써주면 된다. 최종적으로 배열에 있는 값을 순서대로 출력해주면 답이 될 것이다.

 

  추가로, 현재 덱의 크기보다 큰 횟수를 움직일 경우 어차피 한바퀴 돌면 제자리이므로 '%'연산을 사용해서 매번 덱을 돌리는 횟수를 현재 덱 크기 이하로 줄일 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    class Card { int ans = -1; }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Card> dq = new ArrayDeque<>();
        Card[] arr = new Card[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new Card();
            dq.addLast(arr[i]);
        }
        for (int i = 1; i < n; i++) {
            int cnt = i%dq.size();
            while (cnt-->0) {
                dq.addLast(dq.pollFirst());
            }
            dq.pollFirst().ans = i;
        }
        dq.pollFirst().ans = n;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(arr[i].ans).append(' ');
        System.out.println(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}