[C++] 17298: 오큰수

쩡우·2022년 11월 21일
0

BOJ algorithm

목록 보기
7/65

17298번 오큰수 (acmicpc.net)

문제

크기가 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

풀이

스택을 이용한 풀이 문제이다!

input과 output 배열을 만들어 주었고,
수열을 input 배열에 쭉 입력받았다.
input 배열의 뒤에서부터 검사를 실행한다.

현재 요소를 검사하는 알고리즘은 다음과 같다.

  1. 스택이 비어있지 않고, 스택의 맨 위 요소가 현재 요소보다 작거나 같으면, 스택의 맨 위 요소를 없앤다. --> 스택이 비거나 스택의 맨 위 요소가 현재 요소보다 클 때까지 반복

  2. 1번이 끝난 후, 스택이 비어있으면 현재 요소의 output 값은 -1이다.

  3. 1번이 끝난 후, 스택이 비어있지 않으면 현재 요소의 output 값은 스택의 맨 위 요소이다.

  4. 2번 혹은 3번이 끝난 후, 스택의 맨 위에 현재 요소를 넣어준다.

1번은 현재 요소보다 큰 요소가 오른쪽에 있었는지 찾는 과정이다.

1번에서 오른쪽에 현재 요소보다 큰 요소가 없다면 스택이 빌 때까지 pop할 것이고, 2번에서 output에 -1을 넣어줄 것이다.

1번에서 오른쪽에 현재 요소보다 큰 요소가 있다면, pop을 하는 while문이 종료될 것이고, 현재 스택의 가장 위에 있는 요소는 현재 요소보다 큰 요소 중 가장 왼쪽에 있는 요소일 것이다. 그러므로 3번에서 현재 요소의 output 값에 스택의 맨 위 요소를 넣어줄 것이다.

(부가 설명)

"현재 요소보다 큰 요소 중 가장 왼쪽에 있는 요소"를 A라고 할 때
2번 혹은 3번을 진행한 후에,
현재 요소는 ->
여태까지 확인한 요소 중,
A의 왼쪽에 있고,
A보다 작은 값 중에 가장 큰 값이 된다.
그러므로 스택의 가장 윗부분에 push해준다.

스택은 항상 위에서부터 아래로 오름차순으로 정렬되어 있을 것이다.

마지막으로 output array를 쭉 출력해 주면 정답이다.

코드

#include <iostream>
#include <stack>

using namespace std;

void input_data(void);
void right_biggest(void);
void prt_result(void);

int input[1000000];
int output[1000000];
int n;
stack<int> stk;

int main(void)
{
	input_data();
	right_biggest();
	prt_result();

	return (0);
}

void input_data(void)
{
	cin >> n;

	int i = -1;

	while(++i < n)
		cin >> input[i];

	return ;
}

void right_biggest(void)
{
	int i = n;

	while (--i >= 0)
	{
		while (!stk.empty() && stk.top() <= input[i])
			stk.pop();

		if (stk.empty())
			output[i] = -1;
		else
			output[i] = stk.top();

		stk.push(input[i]);
	}

	return ;
}

void prt_result(void)
{
	int i = -1;

	while(++i < n)
		cout << output[i] << " ";

	return ;
}

히히😀😀

profile
Jeongwoo's develop story

0개의 댓글