[백준] 1835번 - 카드 (Silver 4)

문제 링크

[백준] 1835번 - 카드 (Silver 4)

문제 설명

다음의 과정을 통해 얻어진 카드가 1부터 N까지 순서대로 정렬되도록 하는 카드의 초기 순서를 구한다.

1. 첫 번째 카드를 맨 뒤로 옮기고, 첫 번째 카드를 빼낸다.
2. 남은 카드 중 첫 두 장의 카드를 맨 뒤로 옮기고, 첫 번째 카드를 빼낸다.
3. 남은 카드 중 첫 세 장의 카드를 맨 뒤로 옮기고, 첫 번째 카드를 빼낸다.
4. 맨 뒤로 옮기는 카드가 계속 한 장씩 늘어나는 구조이다. 이를 한 장만 남을 때까지 반복한다.

정답 코드 및 설명

카드의 초기 순서가 1부터 N까지 순서대로 정렬되어 있다고 하자.
이 때 문제에서 주어진 과정을 수행하면 어떤 순서로 정렬되는지를 구할 수 있다.
이를 이용하면 역으로 과정 수행 후 카드가 순서대로 정렬되기 위한 초기 순서도 구할 수 있다.

아래 코드에서 repeat 메소드가 그 역할을 수행한다.
repeat 메소드에서 Map cardOrder에 i번째로 들어가는 원소를 살펴보자.

• value : i. 몇 번째로 나온 카드인지를 의미한다.
• key : i번째로 나온 카드가 처음 몇 번째였는지를 의미한다.

이제, 역으로 과정 수행 후 카드가 순서대로 정렬되려면 어떻게 되어야하는지를 생각해보자.
초기에 i번째에 있던 카드가 무엇이어야 하는지를 생각하면 된다.
cardOrder에 (key, value)가 들어있다면, value번째에 나오는 카드가 key번째 카드다.
결과가 1부터 N까지 순서대로 정렬되기를 원한다면 key번째 카드는 value여야 함을 알 수 있다.
따라서, cardOrder.get(i)를 i를 1부터 N까지 출력해주면 원하는 카드의 초기 순서를 출력한 것이 된다.

import java.io.*;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ1835 {
    int n;
    Queue<Integer> cards = new LinkedList<>();
    HashMap<Integer, Integer> cardOrder = new HashMap<>();

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            cards.add(i);
        }
    }

    void repeat() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++)
                cards.add(cards.poll());
            cardOrder.put(cards.poll(), i);
        }
    }

    void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(cardOrder.get(i)).append(' ');
        }
        bw.write(sb.toString());
        bw.close();
    }

    void solution() throws IOException {
        input();
        repeat();
        print();
    }

    public static void main(String[] args) throws IOException {
        new BOJ1835().solution();
    }
}