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

유지연·2023년 4월 6일
0

PS

목록 보기
6/16

백준 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)을 공백으로 구분해 출력한다.


코드

❗ 시간 초과 코드 (벡터+단순 반복)

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int num;
	cin >> num;
	vector<int> nge;
	vector<int> result;

	for (int i = 0; i < num; i++) {
		int number;
		cin >> number;
		nge.push_back(number);
	}

	for (int i = 0; i < num - 1; i++) {
		for (int j = i + 1; j < num; j++) {
			if (nge[i] < nge[j]) {
				result.push_back(nge[j]);
				break;
			}
		}
		if (result.size() != i + 1) result.push_back(-1);
	}

	result.push_back(-1);

	for (int i = 0;i < result.size();i++) {
		cout << result[i] << ' ';
	}

	return 0;

}

❗ 정답 코드 (stack, pair)

#include <iostream>
#include <algorithm>
#include <stack> 
#include <queue>
#include <vector>
using namespace std;

int main() {
	
	ios::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	stack<pair<int, int>> input_st;
	cin >> tc;
	vector<int> result(tc, -1);

	for (int i = 0; i < tc; i++) {
		int num;
		cin >> num;

		while (!input_st.empty() && input_st.top().first < num) {
			result[input_st.top().second] = num;
			input_st.pop();
		}
		input_st.push(make_pair(num, i));
	}
	

	for (int i = 0; i < tc; i++) {
		cout << result[i] << ' ';
	}
	vector<int>().swap(result); //메모리 해제
	return 0;
}


코드풀이

처음 17298번을 보고 solved.ac 난이도가 골드4이길래, 쫄고 시작했는데 너무 금방 풀어버려서 오잉 뭐지? 하는 찰나에 시간초과를 맞이했다🤕 (아직도 난이도 골드에도 쪼는 나...)
처음에는 단순히 입력값을 vector로 받고, 자신보다 오른쪽에 있는 원소들을 탐색하다가 자신의 값보다 큰 원소를 만나면 그 값을 result vector에 저장하는 방식으로 코드를 짰다. 제출을 해보니 시간초과가 뜨길래 살며시 알고리즘 분류가 스택으로 되어 있는 것을 확인하고는 다시 머리를 굴리기 시작했다.

이 문제는 지난 포스팅에서 다루었던 후위 표기식와 매우 유사한 문제 풀이 구조를 가지고 있었다. 스택에 입력값을 저장하면서 일정 기준이 만족되거나 만족되지 않았을 때 취할 액션만 정해주면 끝이다.

❗ 알고리즘

오큰수는 자신보다 오른쪽에 있는 큰 수들 중 가장 왼쪽에 있는 수이다. 따라서 stack에 값을 저장하면서 stack의 top보다 큰 수가 들어오려고 하는 경우, 그 수가 stack top의 오큰수가 되는 것이다. 오큰수를 저장하기 위한 자료구조로는 vector를 선택하였고 모든 값을 -1로 초기화 시켜놓았다. 오큰수가 없는 경우는 -1을 출력해야하기 떄문이다.

while (!input_st.empty() && input_st.top().first < num)
위와 같은 반복문 조건을 통해 stack의 top이 input 값(num) 보다 작은 경우는 num값을 vector [stack top의 index]에 저장하고 해당 top값을 pop해주었다.

❗ pair

여기서 또 한가지의 포인트는 stack에 입력값을 저장해줄 때 pair 클래스를 이용하여 (입력값, index) 형태로 저장했다는 것이다. 특정 원소의 오큰수를 구한 후, result vector의 올바른 index에 넣어주어야 하기 때문에 index의 값도 함께 저장한 것이다. 그리고 서로 연관된 두 가지 값을 동시에 다루기 위해서는 pair가 가장 적당할 것이라고 생각했다.

  • pair의 사용
    pair는 utility 헤더파일에 포함된 STL이다. utility 헤더파일은 algorithm, vector 헤더파일에 이미 포함되어 있기 때문에 algo나 vector 헤더파일을 이미 선언했다면 중복하여 선언하지 않아도 된다.

  • pair <type1, type2> p;
    p.first : p의 첫번째 인자 반환
    p.second : p의 두번째 인자 반환

  • 값 저장하기
    1) p.first = 1;
    p.second = 2;

    2) make_pair (1, 2);

스택에 pair를 저장하고 싶은 경우, stack<pair<type1, type2>> 형태로 사용하면 된다.


이렇게 무사히 스택의 특징을 이용하여 시간제한을 극뽁하고 문제를 해결할 수 있었다. 계속해서 스택을 이용하는 문제를 풀다보니 이제 어느 경우에 스택을 사용하고, 어떤 특징들을 사용하는지 사알짝 감이 오는 것 같기도 하고?? 😋 아직 많이 부족하지만 예전에 비하면 확실히 생각하는 방법이나 문제에 접근하는 방법을 알아가는 것 같아서 좋다. 더 열심히 해서 더 많이 성장할 수 있기를!! 빠이링 해야지~💪

profile
Keep At It

0개의 댓글