17298 오큰수 with C++

문제

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

17298번: 오큰수

단순히 for문을 두 번 중첩해서 찾는(매 for문마다 오큰수를 찾는) 코드를 바로 작성해서 제출하면 시간초과로 통과하지 못합니다.

해결한 방법

1. 입력받은 숫자를 stack에 push한다.
2. 다음 숫자를 stack의 가장 위 숫자와 비교해서 더 크다면 result 배열에 저장한다.
3. 2번을 반복하되 result[idx]에 이미 값이 있다면 idx에 1을 빼고 다시 2를 반복한다. (빈칸 찾기)
4. 숫자 배열이 끝날때까지 1,2,3 단계를 거치고 숫자 배열이 끝나면 결과를 출력한다.

#include <iostream>	
#include <stack>
#define MAX 1000000
using namespace std;

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

	// 입력
	int n;
	cin >> n;

	int* li = new int[MAX];
	int* result = new int[MAX]();
	for (int i = 0; i < n; i++){
		cin >> li[i];
	}

	// result 배열 만들기
	stack<int> num_stack;
	num_stack.push(li[0]);
	int idx;
	for (int i = 1; i < n; i++){
		idx = i;
		while (!num_stack.empty() && num_stack.top() < li[i]) {
			idx--;
			if (!result[idx]) {
				result[idx] = li[i];
				num_stack.pop();
			}
		}
		num_stack.push(li[i]);
	}

	// result 출력
	for (int i = 0; i < n; i++){
		if (!result[i])
			cout << -1 << " ";
		else
			cout << result[i] << " ";
	}

	delete[] result;
	delete[] li;

	return 0;
}

개선한 방법

1. 입력한 숫자 배열을 거꾸로 인덱싱합니다.
2. stack의 top에 인덱싱한 수보다 낮은 수가 있다면 제거합니다
3. 제거가 불가능할때까지 2를 반복합니다.
4. stack의 top의 수를 result배열에 저장합니다. 만약 stack이 비었다면 -1을 저장합니다.
5. stack에 인덱싱한 수를 push합니다.

1) 역순으로 인덱싱하기때문에 stack에 있는 수가 인덱싱한 수보다 큰 수가 있다면 가장 가까운 오큰수가 찾아지게 됩니다.

 

2) 숫자를 제거하는 것은 가장 가까운 큰 수를 찾는 과정입니다.

 

3) 숫자를 막 제거해도 어차피 자신보다 작은 수들만 제거하게 되고 자신을 stack에 push할 예정이니 제거된 수가 다음 인덱싱할 수들의 오큰수가 될 수 없어서 괜찮습니다.

#include <iostream>	
#include <stack>
#define MAX 1000001
using namespace std;

int li[MAX];
int result[MAX];

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

	// 숫자 개수 입력
	int n;
	cin >> n;

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

	// result 배열 작성
	stack<int> num_stack;
	for (int i = n - 1; i >= 0; i--) {
		while (!num_stack.empty() && num_stack.top() <= li[i])
			num_stack.pop();
		
		if (!num_stack.empty())
			result[i] = num_stack.top();
		else
			result[i] = -1;
		
		num_stack.push(li[i]);
	}

	// 출력
	for (int i = 0; i < n; i++){
		cout << result[i] << " ";
	}

	return 0;
}

위 코드는 백준 onteeae님의 코드를 참고했습니다.

출처: https://www.acmicpc.net/source/34727456

 

풀이를 보고 이 문제를 해결하셨다면 다음 문제인 오등큰수 문제를 같은 방법을 적용해서 풀어보시는것도 좋을듯 합니다.

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