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

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

17298번: 오큰수

---

 처음 문제를 읽었을 때 생각보다 쉽다고 느꼈는데 이중 for문으로 만들면 시간 초과가 떠서 스택으로 다시 푸느라 애먹은 문제이다. 문제의 풀이 방식을 보는데 이렇게 문제에 접근하는 과정이 굉장히 신선하게 다가왔고 두고두고 보고 싶은 풀이 과정이다. 이 문제만 제대로 알면 17299번 오등큰수 푸는 건 좀 쉬운 것 같다.

 

코드

 

 

코드 설명

 메인 함수 전에 수열의 개수 n, 수열을 저장하는 배열 arr, 정답을 저장할 배열 arr, 스택 s를 정의해준다.

참고로 배열 뒤에 {}를 붙인 이유는 모든 배열을 0으로 초기화 해준다는 뜻이다.

int arr[1000001] = {}; // 모든 배열 0으로 초기화
int answer[1000001] = {}; // 모든 배열 0으로 초기화

 

 다음은 메인함수이다.
메인 함수 처음에 밑 코드를 써준 이유는 알고리즘 문제를 C++로 풀 때 이 구문을 추가해주면 속도가 빨라진다.

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

 

수열의 개수 n과 크기가 n인 수열을 입력해준다. 이 수열은 arr에 저장해놓는다.

cin >> n;
for (int i = 0; i < n; i++)
	cin >> arr[i];

 

 

그 다음 코드는 이 문제의 핵심 코드이자 접근하는 방법이 신기한 코드이다.

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

		s.push(arr[i]);
}

for문은 arr 배열의 거꾸로 진행될 예정이다. 

백준에 나와있는 예제 1번으로 예를 들어보면 n = 4, arr = [3, 5, 2, 7]이 된다. 배열은 거꾸로 돌면서 스택이 비어있으면 그 수의 오큰수는 -1이고 스택이 비어있지 않으면 스택의 top이 오큰수가 된다. 

배열을 거꾸로 돌면서 스택에 넣을 예정이고, 스택의 top이 배열의 수보다 작으면 그 수는 오큰수가 아니기 때문에 pop 해준다. 이런 방식으로 계속 진행하다가 스택에 원소가 없는 상태가 되면 그 수의 오큰수는 없으므로 -1이 된다.(참고로 맨 마지막 수열은 오른쪽에 숫자가 없기 때문에 오큰수가 무조건 -1이 된다.)

 

 

마지막으로 answer 배열을 하나하나 출력해주면 끝이다!

	//정답 출력
	for (int k = 0; k < n; k++)
		cout << answer[k] << " ";