백준 17298번 c++

 

처음에는 동적 배열에 수를 입력 받은 뒤 , 값을 비교하면서 출력하는 방식으로 코드를 짰다.

하지만 그냥 배열로 입력 받아도 1000000 이상은 못받게 배열 크기를 정하면 되기에 하나씩 입력받아 바로 배열에 저장하는 방식으로 고쳤다. 

 

단순하게 A[i] 의 값이 오른 쪽에 있는 어떤 수 보다 크면

바로 그 수가 큰 수 중에서 왼쪽에 있는 수라고 생각을 했기 때문에 

A[i] < A[j]  // j 는 i 보다 큰 수 ;  일때 

 A[j]의 값이 NGE 값 이라고 생각하고 코드를 짰다. 

결과는 제대로 나오나, 백준에 넣으니 틀렸다고 나온다.

#include <iostream>


using namespace std;

int main ()
{
	int N;

	cin >> N;
	
	

	for (int i = 0; i < N; i++) //숫자를 입력받아서 배열에 저장
	{
		cin >> x;
		
		A[i] = x;
	}

	
	for (int i = 0 ; i < N; i++)
	{	
		
			
			
			for (int j = i + 1; j < N; ) 
			{
				
				
				if (A[i] > A[j] )
				{
					j++;
					if (j == N)
					{
						cout << "-1 ";
						break;
					}
					
					continue;


				}
				else {
					cout << A[j]<<" ";
					break;

				}
				cout << "-1 ";
			}
	}
	
	
	return 0;

}

값은 맞게 나오나 숫자가 커질 수록 시간 복잡도가 들어나다 보니 틀린 것 같다.

다시 찾아보니 stack으로 구현하여 문제를 풀어야 한다는 것을 알았다. 

 

배열의 맨 뒤 인덱스 값 부터 시작해서 큰 수는 넣고 작은 수는 pop 하는 방법으로 스택에 큰 수 들만 넣어 두고 , 더 이상 스택에 값이 없다면 -1 을 넣는 방식으로 진행을하였다

 

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

		if (stack.empty()) B[i] = -1;
		else B[i] = stack.top();

		stack.push(A[i]);
	}

	// 정답 출력
	for (int i = 0; i < N; i++)
		cout << B[i] << " ";