[백준] 12789번: 도키도키 간식드리미

알고리즘 & 백준 문제풀이 메모

[백준] 12789번: 도키도키 간식드리미

볼륨조절불가 2024. 7. 27. 19:37

728x90

문제 링크

https://www.acmicpc.net/problem/12789

풀이 과정

# 문제에서의 예시
1번을 통과시키기 위해 1번 앞에 있는 5번, 4번을 모두 왼쪽 공간으로 이동시킨다.
그리고 2번을 통과시키기 위해 앞의 3번을 왼쪽 공간으로 이동시킨다.
줄에 있는 사람이 다 없어졌다면, 왼쪽 공간의 3~5번이 왼쪽 공간으로 들어온 순서의 반대로 통과한다.

원래 서있던 줄에서는 순서대로 빠져나갈 수 있고, 왼쪽 공간에서는 들어온 순서의 반대로 빠져나가는 것을 이용해 문제를 해결해야 한다.

1번을 먼저 통과시키기 위해, 입력으로 들어온 순서 정보를 큐에 저장한 뒤 순차적으로 조사하면 문제 상황을 구현할 수 있다.

큐의 앞부분을 확인하고 제거하는 식으로 큐를 순차적으로 조사할 수 있다.

(이때 제거의 의미는 원하는 번호를 큐에서 찾아 라인을 통과함 or 앞사람이 왼쪽 공간으로 이동함을 의미)

큐의 앞부분을 조사할 때 1번이면 통과시키고, 아니라면 왼쪽 공간으로 이동시켜야 한다.

삽입한 순서의 반대로 추출할 수 있는 스택의 특성을 이용하면 왼쪽 공간을 스택으로 구현할 수 있다.

1번이 통과한 이후, 다음 번호인 2번을 찾을 때 큐와 스택의 윗부분을 조사하면 된다.

(1번이 통과하기 전 2번이 스택으로 이동했을 수 있기 때문)

스택의 윗부분에 2번이 없다는 것은 스택 안쪽에 2번이 있다는 뜻이고, 스택의 후입선출 원리에 의해 2번을 통과시킬 수 없다는 의미가 된다. 즉 Sad.

코드

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));
        int n = Integer.valueOf(br.readLine());
        
        Queue<Integer> queue = new LinkedList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 줄 상태를 큐에 저장
        for(int i = 0; i < n; i++) {
            int studentNum = Integer.valueOf(st.nextToken());
            queue.offer(studentNum);
        }

        Stack<Integer> stack = new Stack<>();
        // 라인을 통과해야 하는 번호 order
        // 이 order를 큐와 스택의 원소랑 직접 비교
        int order = 1;
        
        while(!queue.isEmpty()) {
            // 큐 앞부분 확인
            if(queue.peek() == order) {
                queue.poll();
                order++;
            } 
            // 스택 윗부분 확인
            else if(!stack.isEmpty() && stack.peek() == order) {
                stack.pop();
                order++;
            }
            // 큐 앞부분에 없으면 스택에 추가
            else {
                stack.push(queue.poll());
            }
        }
		
        // 큐에서 사람들이 다 이동한 뒤 스택에 남은 사람들 확인
        int originalSize = stack.size();
        for(int i = 0; i < originalSize; i++) {
            if(stack.peek() == order) {
                stack.pop();
                order++;
            } else {
                break;
            }
        }
		
        // 스택이 다 비었으면 모든 사람들이 라인을 통과했다는 의미
        if(stack.isEmpty()) {
            System.out.println("Nice");
        } else {
            System.out.println("Sad");
        }
    }
}

느낀 점

이번 문제에서 스택을 이용하는 아이디어를 떠올리긴 쉬웠지만, 큐가 아닌 리스트를 이용해 줄을 구현한 결과 문제 상황과 코드가 쉽게 와닿지 않았다.

그리고 order라는 변수를 이용해 라인을 통과시킬 번호를 정하는 전략도 처음에는 떠올리지 못했다.

처음에는 리스트 내에서 최솟값을 구한 뒤 리스트 앞에 있는 번호는 모조리 스택으로 이동시키는 전략을 사용했는데, 구현하자니 머리가 아파 결국 검색을 할 수밖에 없었다.

아무튼 이번 문제를 통해 크게 두 가지를 느낄 수 있었다.

문제에서 제시하는 상황과 비슷한 자료구조(큐, 스택)를 사용하면 이해하기 편하다.
순서대로 통과시키기 위해 순서 자체를 저장하는 변수를 활용할 수 있다.

728x90