[17298] C++ : 오큰수

지난주에 풀기 시작했는데 어제에서야 푼 문제이다. 사실 여행가고 노느라 안 푼 시간 제외하면 2일정도 고민해서 푼 것 같다. 처음으로 푼 골드 난이도 문제였는데 확실히 30분 컷 가능한 실버에 비해 고민거리도 많고 예외도 많은 것 같다. 

 

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 

4
3 5 2 7

예제 출력 1 

5 7 7 -1

예제 입력 2 

4
9 5 4 8

예제 출력 2 

-1 8 8 -1

 

풀이

이 문제는 문제를 읽는 것 보다 그냥 예제 출력을 보는 것이 더 빠르게 이해된다. 그냥 뒤쪽에 본인보다 큰 수가 있으면 가장 가까운 수로, 없다면 -1로 표현을 하면 된다. 

일단 기본적인 알고리즘 자체는 간단하다. 

while(모든 input 값)
if (stack이 비어있다면)
      input 값 push
else
     top과 input 값 비교
              top이 더 크면 push
              top이 더 작으면 pop => top이 더 클 때 까지 무한 반복
    input 값 push

이런 방식으로 해결하면 된다. 사실 이 문제는 시간제한이나 메모리 제한이 없다면 정말 쉽게 해결할 수 있는 문제이지만, 문제는 수열 A의 크기가 1,000,000 까지 주어진다는 것이다.

그래서 이리 저리 피해다니면서 만든 첫 코드가 아래와 같다.

#include <iostream>
#include <deque>

using namespace std;

int main()
{
	deque<int> nonfind;
	deque<int> find;
	int n;
	cin >> n;
	int topindex = 0;
	for (int i = 0; i < n; i++)
	{
		int number;
		cin >> number;
		if (nonfind.empty())
			nonfind.push_back(number);
		else
		{
			if (nonfind.back() > number)
				nonfind.push_back(number);
			else {
				while (!nonfind.empty() && nonfind.back() < number) {
					find.push_back(number);
					nonfind.pop_back();
				}
				nonfind.push_back(number);
			}
		}
	}

	while (1)
	{
		if (find.empty())
		{
			cout << "-1" << "\n";
			break;
		}
		else if (nonfind.size() == 1)
		{
			cout << find.front() << " ";
			find.pop_front();
		}
		else if (nonfind.front() > find.front())
		{
			cout << -1 << " ";
			nonfind.pop_front();
		}
		else if (nonfind.front() == find.front())
		{
			cout << find.front() << " ";
			find.pop_front();
		}

	}

	return 0;
}

 예제 케이스가 모두 통과되었기 때문에 제출한 코드였는데 반례가 있었는지 오답이 떴다. 알고 보니 그냥 내 알고리즘 자체에 문제가 있었다. 값이 가장 큰 문제점은 input 순서를 알 수 없어서 출력될 때 뒤죽박죽 된다는 것이었다. 예를 들어 예제 입력 1의 출력 직전 메모리 형태를 도식화하면 아래와 같다.

 

빨간 글씨가 출력 순서이다. 오큰수를 정확하게 찾았으나 출력 순서가 케이스마다 달라서 할 수 없었다. 이 문제를 해결하기 위한 뾰족한 방안이 떠오르지 않아 2일이나 걸렸다.

그래서 새로 만든 방법은 linked list와 stack을 혼합한 형태이다. 그림으로 그리면 아래와 같다.

check는 nonfind 안에 있으면 false 밖에 있으면 true라고 나타낸다. 만약 false면 출력할 때 -1로 표시하면 된다. 물론 프로그램이 길어지면 정말 느리게 작동하지만 메모리 문제는 어느 정도 해결한 것 같다.위 방식으로 푼 코드는 아래와 같다.

 

<정답 코드>

using namespace std;

typedef struct num {
	bool check;
	int data;
	struct num* link;
}Num;

int main()
{
	stack<Num*> nonfind;
	int n;
	Num* start = NULL;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		Num *number = (Num*)malloc(sizeof(Num));
		cin >> number->data;
		number->check = false;
		number->link = NULL;
		if (i == 0)
			start = number;
		if (nonfind.empty())
			nonfind.push(number);
		else
		{
			nonfind.top()->link = number;
			if (nonfind.top()->data > number->data)
				nonfind.push(number);
			else {
				while (!nonfind.empty() && nonfind.top()->data < number->data) {
					nonfind.top()->data = number->data;
					nonfind.top()->check = true;
					nonfind.pop();
				}
				nonfind.push(number);
			}
		}
	}
	for (Num* p = start; p; p = p->link) {
		if (p->check)
			cout << p->data << " ";
		else
			cout << -1 << " ";

	}
}