[BOJ] 18115 - 카드 놓기 JAVA

www.acmicpc.net/problem/18115

18115번: 카드 놓기

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

예제 입력 1

5

1 1 1 1 1

예제 출력 1

5 4 3 2 1

예제 입력 2

5

2 3 3 2 1

예제 출력 2

1 5 2 3 4

 

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int[] ans = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int num = n;
        int idx1 = 0, idx2 = 1, idx3 = n-1;
        for(int i = 0; i < n; i++) {
            int inst = arr[i];
            if(inst == 1) {
                ans[idx1] = num;  // idx2가 왼쪽으로 이동하는 경우는 없기 때문에 ans[idx1]은 검사 없이 바로 넣어도 됨
                if(ans[idx1 + 1] == 0) idx1 += 1;  // 다음 인덱스가 이전에 수행한 2번 명령에 의해 값이 들어왔을 수도 있음
                else idx1 = idx2 + 1;  // idx2는 조정한 후에 num을 넣기 떄문에 idx2+1 해주는 것이 맞다(이 시점에선 아직 이전 반복에서 놓은 idx2 좌표를 유지하고 있는 것임)
            }else if(inst == 2) {
                if(ans[idx1+1] == 0) idx2 = idx1 + 1;  // 1번 명령 이후 idx1은 새롭게 갱신되었으니 idx1+1만 확인해주면 됨
                else idx2 += 1;  // idx1와 가장 가까운 답이 정해지지 않은 좌표
                ans[idx2] = num;
            }else if(inst == 3) {  // 뒤에서 넣는 건 3번 하나 뿐이므로 인덱스를 하나씩 왼쪽으로 밀기만 하면 됨
                ans[idx3] = num;
                idx3 -= 1;
            }
            num -= 1;
        }

        for(int i = 0; i < n; i++) sb.append(ans[i] + " ");
        System.out.println(sb.toString());
    }
}

 

명령에 따라 적절한 위치에 N~1의 번호를 넣으면 된다.

 

큐나 덱을 사용하자니 끝이 아닌 위치에 넣어야 할 때는 앞이나 뒤의 것을 모두 뺀 다음 다시 집어넣어야 하기 떄문에 시간 초과가 날 것 같았다. (N = 1,000,000)

 

큐, 덱이 아니라 배열을 사용해야했다. 인덱스를 하나하나 계산해야 하는 골치아픈 문제.

 

1. idx2이 왼쪽으로 넘어와 idx1을 침범하는 경우는 없기 때문에 idx1은 따로 검사를 거치지 않고 바로 넣어주면 된다.

2. 뒤쪽으로 넣는 경우는 3번 명령 하나밖에 없으므로 3번에 대해서는 별 다른 처리 없이 idx3을 왼쪽으로 하나씩 넘겨주기만 하면 된다.

3. 명령 2의 경우가 문제다. 1번 명령을 수행한 후 idx1가 이동하여 idx2를 침범하였다면 idx2를 새롭게 잡아줘야 한다.

반대로 명령 1을 수행 후 idx1을 오른쪽으로 이동할 때도 idx2를 고려해야 한다.

 

 

 

 

 

 

 

he1fire.tistory.com/84

처음에 내가 생각했던 방식도 가능한가보다..

전부 뺐다 전부 집어넣어야 한다는 시간적인 문제를 reverse를 통해 해결했다.