[BOJ 12789] 도키도키 간식드리미

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

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

문제 분석

• 시간 제한 : 1초 Big-O계산 약 1억
• 대기줄 : <queue>이용, 사용 가능한 공간 : <stack>이용
  (queue와 stack을 이용할 예정이므로 시간제한에 대한 걱정을 덜해도 괜찮겠구만)

풀이 방식

• 대기줄이 빌때 까지 반복
  • 대기줄 queue이나 공간 stack의 맨앞에 다음 순서가 있는지 확인
  • 없으면 stack에 queue 맨앞에 있는 값 넣어주기
• 대기줄 비면 공간 빌때 까지 반복
  • 공간 stack의 맨앞에 다음 순서가 있는지 확인
  • 없으면 stop
• 대기줄과 공간이 둘다 비었으면 NICE!, 아니면 SAD

int order = 1;
int n;
bool isNice = true;
stack<int> space;
queue<int> waiting;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int j = 0; j < n; j++) {
        int x;
        cin >> x;
        waiting.push(x);
    }
    while (!waiting.empty()) {
        if (order == waiting.front()) {//이번 순서가 대기줄 queue에 있으면 
            waiting.pop();
            order++;
        } else {
        	//비어있는 stack에 top접근하면 오류남
            if (!space.empty() && order == space.top()) {//이번 순서가 공간stack에 있으면
                space.pop();
                order++;
            } else {//이번 차례 없으면 
                space.push(waiting.front());
                waiting.pop();
            }
        }
    }
    while (!space.empty()) {//공간이 빌때 까지
        if (order == space.top()) {//이번 순서가 공간stack에 있으면
            space.pop();
            order++;
        } else {//없으면
            isNice = false;
            break;//승환이는 슬퍼ㅠ
        }
    }
    if (isNice) cout << "Nice";
    else cout << "Sad";
    return 0;
}

22번째줄 코드, stack의 top에 접근하는 과정에서 비어있는 경우에 대한 예외처리를 안해주어 애를 좀 먹었다.
나머지 논리는 금방 생각하여 시간이 오래걸리지는 않았다.

느낀 점

• <stack>,<queue> 등등에 stl을 사용할 때 비어있는 위치에 접근을 하는 건 아닌지에 대한 예외처리를 확실히 해주어야 겠다는 생각 이 들었다.
• 처음에 문제를 보고 사용가능한 공간에서 다시 대기줄로 이동할 수 있는 줄 알고 문제를 어떻게 풀어야 하나 막막했다.
• 보다 보니까 이렇게는 언제나 가능 할 거 같아 문제 이해 방식을 바꿨고 풀이 방식에 대한 논리는 바로 생각해냈다.

시간 복잡도

• queue,stack에서 front,top에 대한 접근, 삭제 -> O(1)
• queue가 빌때 까지 반복 -> O(n)
• stack이 빌때 까지 반복 -> O(n)
  ➣ O(n)