오늘의 코드. 13일차 (백준/12789번 도키도키 간식드리미)

문제 제목을 보고 내 눈을 의심하며 들어왔다. 이것이 바이럴 마케팅일까?

 

Baekjoon / Problem No. 12789  (도키도키 간식드리미)

 

Problem

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

 

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다.

Input

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

Output

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다. 

 

---

Solution

저 방대한 양의 문제를 보고 내용을 간추려보자면, 결국 현재 줄을 어떤(?)식으로 잘 빼고 넣으면서 순서에 맞게 배치할 수 있느냐의 문제이다.

 

사진을 보면 알겠지만, 스택(stack)구조를 가지고 있는 "한 명씩만 설 수 있는 공간"이 있다. 순서에 맞게 줄을 서려면, 순서에 맞지 않는 부분들을 잠시 저장했다가, 순서상 필요할때마다 끄집어 내면 된다.

 

사실상 솔루션 자체가 코드이다.

 

(절대 분량을 줄이려고 노력한 것이 아니다! 스택의 개념을 하나부터 열까지 다 설명하지 않는 이상, 여기서 더 이야기를 꺼내는건 가독성 측면에서 좋지 못하다. 그야말로 장황한 문제에 장황한 풀이가 되어버린다.)

---

Code

#include <cstdio>
#include <stack>

using namespace std;

int main()
{
    stack<int> Line;

    int N, turn;

    int Now = 1;

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &turn);
        if (turn == Now) // 현재 간식받을 사람과 줄서있는 순서가 일치함.
            Now++;
        else
            Line.push(turn); // 순서가 일치하지 않으면 스택에 잠시 저장.

        while (!Line.empty() && Line.top() == Now) // 순서대로 다 빠지고 나면, 스택안에서도 순서에 맞게 보내줘야함
        {
            Line.pop();  // 이미 스택 안에서도 꼬여있는 경우, 그저 Sad한 것. (슬플 뿐)
            Now++;
        }
    }

    if (Line.empty())
        printf("Nice");
    else
        printf("Sad"); 
}

 

---

Review

문제의 제목과 문제의 내용 자체가 일단 신선한 충격이었다.

 

백준이라는 사이트에 있는 문제 하나일 뿐이지만, 사실 백준에 대한 인식에 무엇인가 괴리감이 들었다.

어지러울 정도로 장황한 내용도 한몫한다.

 

다만 스택구조 자체와, 줄 세우기 아이디어는 꽤 유용하게 쓰이므로 나름 신선한 충격과 의미를 동시에 전달한 명작(??)문제가 아닐까?