백준 12789번 도키도키 간식드리미

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

 

아이디어:

1. N번의 입력과 1개의 스택으로 끝낼 수 있다.

2. pos는 대상 번호표 순서로 1부터 시작한다.

3. 들어온 입력이 pos와 같으면 pos를 증가한다.

4. 들어온 입력이 pos와 다르면 스택에 넣는다.

5. 스택 top과 pos를 비교하여 같으면 pop하고 pos를 증가한다.

6. 5의 과정을 while문으로 작성해서 pos에 해당하는 스택 top을 모두 pop한다.

 

입력받은 수(tmp)가 순서(pos)와 일치하면 PASS(pos++), 다르면 스택에서 대기(space.push(tmp))

스택 top도 순서(pos)와 일치하면 PASS(pos++), 이걸 순서와 다를 때 까지 반복

 

참고 풀이: https://zzaekkii.tistory.com/6

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Answer Code
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, tmp, pos = 1;
	stack<int> space;
	cin >> N;
	
	while (N--) {
		cin >> tmp;

		if (tmp == pos)	pos++;
		else space.push(tmp);

		while (!space.empty() && space.top() == pos) {
			space.pop();
			pos++;
		}

	}

	space.empty() ? cout << "Nice" : cout << "Sad";

	return 0;

}

 

---

 

나의 풀이:

1. 우선 대기줄에 서있는 학생을 모두 처리하고 그 뒤에 스택을 처리하도록 했으나 실패

2. 스택을 두 개 생성하여 풀어보려고 했으나 입력한 순서의 반대로 가려고 해서 실패

3. 스택을 두 개와 배열을 하나 생성하고 배열에 순서대로 입력받는다.

4. 입력받은 배열의 반대로 스택에 입력해서 원본 줄과 대기 공간 줄 두 개의 스택을 사용한다.

5. 줄.top이 pos와 같으면 줄.pop, pos++

6. 공간.top이 pos와 같으면 공간.pop, pos++

7. 둘 다 pos가 아닐 때 줄이 비어있으면 만들어질 수 없는 수열이므로 break

8. 둘 다 pos가 아닐 때 줄.top을 공간에 push하고 줄.pop

9. pos가 N + 1이 될 때 까지 반복해서 N + 1이면 Nice, 아니면 Sad 출력

 

// My Code
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, tmp, pos = 1;
	int arr[1001];
	fill(arr, arr + 1001, 0);
	cin >> N;
	stack<int> line;
	stack<int> space;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	for (int i = N - 1; i >= 0; i--) {
		line.push(arr[i]);
	}
	
	while (pos != N + 1) {

		if (!line.empty() && line.top() == pos) {
			line.pop();
			pos++;
		}
		else if (!space.empty() && space.top() == pos) {
			space.pop();
			pos++;
		}
		else {
			if (line.empty()) break;
			else {
				space.push(line.top());
				line.pop();
			}
		}
	}

	pos == N + 1 ? cout << "Nice" : cout << "Sad";

	return 0;

}

 

정답은 맞았으나 시간, 공간 측면에서 비효율적인 풀이이다.