[BaekJoon/백준] 17298번: 오큰수(C/C++)

백준 17298번: 오큰수

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

17298번: 오큰수

---

문제 설명

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

---

입력과 출력

• 입력: 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
• 출력: 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

---

접근 방법

이번 문제는 지문을 대충 읽어 조금 헷갈렸었다. 오른쪽 큰 수 중에서 가장 큰 수를 뽑는게 아니라, 오른쪽 큰 수 중 가장 왼쪽에 있는 수를 뽑는 것이다. 그래서 예제 1번의 3 5 2 7이 출력 결과가 7 7 7 -1이 아닌, 5 7 7 -1이 나오는 것이다.

처음 문제 해결 방법은 단순하게 숫자를 받음과 동시에 배열과 스택을 쌓은 뒤 0번째 배열은 N-0번 반복, 1번째 배열은 N-1번 반복... 이런식으로 하나씩 비교하며 가까운 큰 수를 갱신하고 출력하는 것이었다.

그러나 이 진행 방법은 계속 스택과 배열을 반복 비교해야하고 한번 비교가 끝나면 스택을 다시 채워야해서, 반복문 2개가 겹친다. 그래서 O(n^2)의 시간 복잡도를 가지게 되어 결국 시간 초과로 실패했다.

그래서 고민 끝에 스택을 다시 채울 필요가 없게 배열을 뒤부터 비교해서 스택을 채우는 방식을 선택했다. 예를 들어 배열 [3, 5, 2, 7]에서 7->2->5->3 순으로 시작하면 스택은 없음->(7)->(7,2)->(7,2,5)이 된다.)

---

코드

• 처음 코드(시간 초과로 실패)

#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;

stack<int> s;
int N;
int *arr;

void fill_stack(int j) {
	for (int i = j; i < N; i++)
		s.push(arr[i]);
}

int main(int argc, char *argv[]) {
	int M;
	int *result;
	scanf("%d", &N);
	arr = (int *)malloc(sizeof(int) * N);
	result = (int *)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &M);
		s.push(M);
		arr[i] = M;
		result[i] = -1;		//초기화
	}

	for (int i = 0; i < N; i++) {
		int j = N - i;
		while (j) {
			if (s.top() > arr[i])
				result[i] = s.top();
			s.pop();
			j--;
		}
		fill_stack(j);
	}

	for (int i = 0; i < N; i++)
		printf("%d ", result[i]);

	return 0;
}

• 완성 코드(성공)

#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;

int main(int argc, char *argv[]) {
	int N, M;
	stack<int> s;
	scanf("%d", &N);

	int *arr = (int *)malloc(sizeof(int) * N);
	int *result = (int *)malloc(sizeof(int) * N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &M);
		arr[i] = M;
	}

	for (int i = N-1; i >= 0; i--) {
		while (!s.empty() && s.top() <= arr[i])
			s.pop();

		if (s.empty())
			result[i] = -1;
		else
			result[i] = s.top();

		s.push(arr[i]);
	}

	for (int i = 0; i < N; i++)
		printf("%d ", result[i]);

	return 0;
}

---

결과

백준 제출 결과