[C++] 백준 12789. 도키도키 간식드리미

문제

메모리 초과

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int n, tmp;
	cin >> n;

	if (n == 1) {
		cout << "Nice";
		return 0;
	}

	stack<int> s;
	int line = 1;
	while (line <= n) {
		if (!s.empty() && s.top() == line) {
			s.pop();
			line++;
			continue;
		}
		cin >> tmp;
		if (tmp == line) {
			line++;
		}
		else {
			s.push(tmp);
		}
	}

	if (s.empty()) {
		cout << "Nice";
		return 0;
	}

	while (!s.empty()) {
		if (s.top() == line) {
			s.pop();
			line++;
		}
		else {
			cout << "Sad";
			return 0;
		}
	}
	cout << "Nice";

	return 0;
}

풀이

금방 풀 줄 알았더니 반례도 많고 반례를 찾았나 싶었는데 이번엔 메모리 초과다.
잔디매니절님의 조언을 듣고
while문 안에서 입력을 n번 받으면 break 하도록 만들었다.

정말 마음에 들지 않는 코든데 너무 배고픈 나머지 냅다 제출
이런 날도 있는거지 뭐

이게 굴러간다고 코드

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int n, tmp;
	cin >> n;

	if (n == 1) {
		cout << "Nice";
		return 0;
	}

	stack<int> s;
	int line = 1;
	int cnt = 0;
	while (1) {
		if (line > n) break;
		if (cnt > n) break;

		if (!s.empty() && s.top() == line) {
			s.pop();
			line++;
			continue;
		}
		cin >> tmp;
		cnt++;
		if (tmp == line) {
			line++;
		}
		else {
			s.push(tmp);
		}
	}

	if (s.empty()) {
		cout << "Nice";
		return 0;
	}

	while (!s.empty()) {
		if (s.top() == line) {
			s.pop();
			line++;
		}
		else {
			cout << "Sad";
			return 0;
		}
	}
	cout << "Nice";

	return 0;
}

깔끔한 잔디매니절님 코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> v;
int main() {
	int n, tmp;
	cin >> n;

	if (n == 1) {
		cout << "Nice";
		return 0;
	}

	// 입력 받으면서 풀면 지저분하니까 일단 다 받기
	for (int a = 0; a < n; ++a) {
		cin >> tmp;
		v.push_back(tmp);
	}
	stack<int> s;
	int line = 1;
	int idx = 0;

	while(idx < n){ // 아무튼 대기줄 사람은 다 써보자
		if (v[idx] == line) { // 대기줄 맨 앞이 현재 차례
			++idx;
			++line;
		}
		else { // 아니라면
			if (!s.empty() && s.top() == line) { // 대기공간 맨위가 차례
				s.pop();
				++line;
			}
			else { // 아니라면 대기 공간에 줄 맨 앞사람 넣어주기
				s.push(v[idx]);
				++idx;
			}
		}
	}

	if (s.empty()) { // 대기공간 + 대기줄 = 0 -> 성공
		cout << "Nice";
		return 0;
	}

	while (!s.empty()) { // 대기 공간 처리해주기
		if (s.top() == line) {
			s.pop();
			line++;
		}
		else {
			cout << "Sad";
			return 0;
		}
	}
	cout << "Nice";

	return 0;
}

채점

나 원