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

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

12789번: 도키도키 간식드리미

어떤 문제인가?

일단 우리 학교 대회 문제다ㅋㅋ 괜히 반갑게 느껴진다.

문제는 1번부터 N번까지 번호표가 존재하고 번호표 순서대로 간식을 받을 수 있는지 없는지 여부를 출력하면 된다.

 

 

접근 방법

문제를 읽자마자 스택과 큐를 사용해야겠다고 떠올렸다.

 

 

stack<int> waiting;
queue<int> student;
vector<int> after;

현재 줄이 서있는 곳인 큐로, 대기 공간은 스택으로, 간식 받는 곳은 벡터로 구현하기로 했다.

 

 

int n;
cin >> n;
for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    student.push(a);
}

입력된 n번 만큼 정수를 입력받고 큐에 추가해준다.

 

 

 

 

int now = 1;

while (!student.empty()) {
    if (student.front() == now) {
        after.push_back(now);
        now++;
        student.pop();
    } else if (!waiting.empty() && waiting.top() == now) {
        waiting.pop();
        after.push_back(now);
        now++;
    } else {
        waiting.push(student.front());
        student.pop();
    }
}

1번부터 간식을 차례대로 받아야 하기 때문에 순서를 나타내는 now를 1로 초기화했다.

 

그리고 큐가 빌 때까지 반복문을 실행한다.

 

첫 번째 경우, 현재 줄 서 있는 곳의 맨 앞사람이 간식을 받을 차례.

이 경우에는 그냥 벡터에 추가해 준 다음 now를 1 증가시켜 다음 간식받을 사람의 번호표를 찾을 수 있도록 한다.

 

두 번째 경우, 대기 중인 공간의 top에 있는 사람이 간식을 받을 차례.

이 경우에도 마찬가지로 벡터에 추가해 준 다음 now를 1 증가시켜 다음 간식받을 사람의 번호표를 찾을 수 있도록 한다.

 

마지막 경우, 위의 모든 경우가 아닐 경우.

이 경우에는 대기 공간(스택)에 현재 서있는 줄(큐)의 첫 번째 사람을 추가해준다.

 

while (!waiting.empty()) {
    after.push_back(waiting.top());
    waiting.pop();
}

이제 예외 처리를 위해 대기 공간(스택)에 있던 사람들을 간식받는 곳(벡터)에 추가해준다.

 

 

bool possible = true;

for (int i = 0; i < after.size() - 1; i++) {
    if (after[i] > after[i + 1]) {
        possible = false;
        break;
    }
}

이제 가능 여부를 따지기 위해 벡터를 for문을 돌며 탐색한다.

만약 이전 인덱스의 값이 이후 인덱스의 값보다 크다면 번호표 순서대로 정렬된 것 이 아니다.

따라서 possible을 false로 바꾼 후 break로 탈출한다.

 

if (possible) {
    cout << "Nice";
} else {
    cout << "Sad";
}

 

possible의 값에 따라 출력해주면 끝!

 

무엇이 어려웠는가?

사실 자료구조 과목을 수강하면서 실습시간에 풀어봤던 문제와 비슷한 것 같다.

그래서 딱히 어려운 부분 없이 수월하게 풀 수 있었다.

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/12789.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.