[BOJ] 백준 12789번: 도키도키 간식드리미 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/12789

---

1. 생각

stack 응용 문제를 하나 들고 와봤다.

T자 모양의 대기열에서 순번대로 간식을 받을 수 있는지 없는지 판별하는 문제이다.

 

처음의 생각은 대기열에 있는 학생들 중 현재 차례(시작값 : 1)에 해당하는 학생은 간식 받는 곳으로 내보내고,

나머지는 모두 스택에 쌓은 뒤 스택에 있는 학생들은 추후에 하나씩 빼가면서 현재 차례에 해당 하지 않는 학생이 있으면

Sad로 판별하려고 했다.

 

2. 난관 & 해결 방법

for (int i = 0; i < N; i ++){
    std::cin >> num;
    if (turn == num)
        turn ++;
    else
        st.push(num);
}
while (!st.empty() && st.top() == turn){
    st.pop();
    turn ++;
}

 

우선 초기 대기열의 학생들을 스택으로 옮기거나,

turn (차례, 초기값 = 1) 과 동일하면 바로 간식을 받도록 해줬다.

이 과정이 끝나면 대기열은 모두 비고, 스택에만 학생 대기열이 쌓여있게 된다.

그 후 이 스택도 마찬가지로 turn과 동일하면 pop하면 된다.

 

예시)

5

5 4 3 1 2

 

5 push -> 4 push -> 3 push -> 1 pop -> 2 pop -> 3 (stack에서) pop -> 4 (stack에서) pop -> 5 (stack에서) pop

위 과정으로 모든 학생이 간식을 받을 수 있게 되는 코드 로직이다.

하지만 여기서 반례가 있다.

 

반례)

5

1 4 3 2 5

 

위의 코드를 통한 과정만 거친다고 가정하면,

1 pop -> 4 push -> 3 push -> 2 pop -> 5 push

이후 스택에는 위에서부터 5 3 4 가 쌓여있다.

이러면 5가 제일 위에 있으므로 '불가능' 판정이 된다.

 

하지만, 이 케이스는 원래 '가능'한 케이스이다.

1 pop -> 4 push -> 3 push -> 2 pop -> 3 (stack에서) pop -> 4 (stack에서) pop -> 5 (대기열에서) pop

이렇게 진행된다면 모든 학생이 간식을 받을 수 있게 된다.

 

두 진행방법의 차이는,

stack에 쌓인 학생도 turn이 되면 언제든 pop이 될 수 있어야 하는데,

대기열에서 stack에 먼저 다 쌓아버린 뒤에 stack을 하나씩 pop 하게 되면 불가능하다.

따라서, 대기열에서 stack에 쌓는 동안, stack에 쌓인 학생이 turn 이 되면 pop 해줘야 한다.

 

for (int i = 0; i < N; i ++){
    std::cin >> num;
    if (turn == num)
        turn ++;
    else
        st.push(num);
    while (!st.empty() && st.top() == turn)
    {
        st.pop();
        turn ++;
    }
}

if (st.empty())
    std::cout << "Nice\n";
else
    std::cout << "Sad\n";

 

위 코드에서 단순히 while문을 for문 안쪽으로 넣어주면 로직이 완성된다.

새 값을 넣어주고 나서 stack에 쌓인 값들이 다음 turn에 해당되면 pop하도록 해줬다.

 

그 후 stack이 비어있으면 Nice (가능), 값이 들어있어서 모든 학생이 pop 되지 못하면 Sad (불가능) 을 출력한다.

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <stack>

int main(void){
    int N, num, turn;
    std::stack <int> st;
    turn = 1;
    std::cin >> N;
    for (int i = 0; i < N; i ++){
        std::cin >> num;
        if (turn == num)
            turn ++;
        else
            st.push(num);
        while (!st.empty() && st.top() == turn)
        {
            st.pop();
            turn ++;
        }
    }

    if (st.empty())
        std::cout << "Nice\n";
    else
        std::cout << "Sad\n";
    return (0);
}

 

[ 결론 ]

 

단순하게 대기열에서 바로 pop 안되는 데이터는 스택으로 다 옮기고

추후에 스택에서 다 pop 하려 했는데, 여기서 반례를 알게 되었다.

출구가 2군데라는 것을 완전 놓친 것이다.

 

아무래도 이런 stack이나, queue의 응용 문제들은

어떤 식으로 값이 도출될 수 있는지에 대해서 많이 고민해보고 풀어야할 것 같다.