[C++] 백준 17298번 오큰수

17298번: 오큰수

자료 구조 - 스택 문제.

알고리즘 분류를 알고 풀어서 쉽게 접근할 수 있었다.

알고리즘 분류를 모르고 풀면 풀 수 있었을지 모르겠다.

 

문제풀이

다음과 같은 생각을 하고 풀었다.

• 큐를 두 개 만든다. 하나는 입력을 받아놓는 큐, 하나는 큐에서 꺼낸 수를 저장해놓는 큐.
  
  
• 입력을 받아놓는 큐에서 하나씩 꺼내보며 꺼낸 수를 저장해놓는 큐의 맨 위와 비교한다.
  만일 큐가 비어있다면 오큰수가 없다는 뜻이다.
  큐가 비어있지 않을 때에는 현재 수와 저장해놓은 큐의 맨 위의 수를 비교한다.
  만일 현재 수가 더 작다면 큐의 맨 위의 수가 오큰수가 된다.
  현재 수가 더 크다면 큐의 맨 위의 수를 pop()하고 다음 수를 비교한다.
  
  오큰수가 없다면 그냥 현재 수를 꺼낸 수를 저장해놓는 큐에 저장해둔다.
  
  
• 결과를 저장해놓아야 하는데 현재 결과를 입력의 반대로 저장하므로,
  결과 큐도 만들어서 결과를 입력한대로 나오도록 만든다.

 

문제 코드

/*
* 백준 17298번 오큰수
* https://www.acmicpc.net/problem/17298
* 자료 구조, 스택
*/
#include <iostream>
#include <stack>
using namespace std;

int numCnt, input;
stack<int> inputStack;
stack<int> numSaveStack;
stack<int> resultStack;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> numCnt;

	while (numCnt--) {
		cin >> input;
		inputStack.push(input);
	}

	while (!inputStack.empty()) {
		int findResult = -1;
		int inputTop = inputStack.top();
		inputStack.pop();

		while (!numSaveStack.empty()) {
			int numSaveTop = numSaveStack.top();
			if (numSaveTop > inputTop) {
				findResult = numSaveTop;
				numSaveStack.push(inputTop);
				break;
			}
			else {
				numSaveStack.pop();
			}
		}
		if (findResult == -1) {
			numSaveStack.push(inputTop);
		}
		resultStack.push(findResult);
	}

	while (!resultStack.empty()) {
		int resultTop = resultStack.top();
		resultStack.pop();
		cout << resultTop << " ";
	}

	return 0;
}

골드4 문제임에도 생각보다 짧게 짜서 맞출 수 있었다.

 

처음에 채점이 오래걸려서 시간초과인가? 시간초과 날 곳이 없는데? 생각했는데 시간초과가 아니였다.

 

백준 17298번 오큰수 · kimyunseok/cpp@a17eba8