백준 알고리즘 기초 : 자료구조 (2)

17298. (오큰수) 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

두 개의 풀이 방식이 있습니다. 더 이해하기 편한 걸로 코드를 구현해보시는 걸 추천합니다 :D

개인적으로 저는 2번이 이해하기가 더 쉬웠습니다.

 

1) 오큰수를 찾지 못한 값들을 stack에 저장하는 경우

 

vector <int> input(n); // 입력받은 값들
stack <int> index; // 오큰수를 찾지 못한 값들

- Stack에는 오큰수를 찾지 못한 값들이 쌓일 예정이다. (정확히는 몇번째로 입력한 값인지가 쌓인다.)

- 입력값들은 따로 배열 (혹은 벡터)에 저장될 예정이다. (input)

- 입력값들이 저장된 배열에는 오큰수들이 저장될 예정이다. (input)

 

알고리즘 설명

1) 스택이 비어있으면 원소의 index를 push 해준다.

2) 그렇지 않다면, 스택의 Top과 input[i]를 비교한다.

2-1) input[top]보다 input[i]가 크다면

input[top]의 오큰수는 input[i]가 된다. input[top]에 오큰수를 저장해준다.

top은 오큰수를 찾았기 때문에 stack에서 pop을 해준다.

새로운 input[top]과 input[i]을 비교해준다

2-2) input[top]보다 input[i]가 작거나 같으면 = 오큰수를 찾지 못했다면

i를 stack에 push 해준다.

 

=> 예를 들어, 7 5 4 8 ... 로 저장되어있다고 생각할 때, 7 5 4는 모두 오큰수를 찾지 못한 상태이다.

4의 오큰수가 8로 결정되었을 때, 4의 오큰수(8)가 5의 오큰수가 될 가능성이 있기 때문에 비교를 해주는 것이다.

=> 예를 들어, 7 6 4 5...로 저장되어있을 때 4의 오큰수는 5가 된다. 4의 오큰수(5)가 6의 오큰수가 되는지 확인해보면 6>5이므로 4의 오큰수(5)는 6의 오큰수가 될 수없다. 그 뜻은 6의 왼쪽에 있는 오큰수를 찾지 못한 모든 값들은 5보다 크다는 뜻이 된다. 

#include<iostream>
#include<string>
#include <vector>
#include <stack>
using namespace std;

void rBig(vector <int> &input) {
	stack <int> index;
	for (int i = 0; i < input.size(); i++)
	{
		while (!index.empty() && (input[index.top()] < input[i])) {
			input[index.top()] = input[i];
			index.pop();
		}
		index.push(i);
	}
	while (!index.empty()) {
		input[index.top()] = -1;
		index.pop();
	}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector <int> input(n);
	for (int i = 0; i < n; i++)
	{
		cin >> input[i];
	}
	rBig(input);
}

https://st-lab.tistory.com/196

[백준] 17298번 : 오큰수 - JAVA [자바]

자세한 그림과 함께 설명되어있으므로, 이해가 되지 않았다면 참고하는 것을 추천한다.

 

 

2) 오큰수 후보들을 Stack에 저장하는 경우

vector <int> input(n); // 입력받은 값들
stack <int> big; // 오큰수의 후보

- Stack에는 오큰수의 후보들이 쌓일 예정이다.

- 입력값들은 따로 배열 (혹은 벡터)에 저장될 예정이다. (input)

- 입력값들이 저장된 배열에는 오큰수들이 저장될 예정이다. (input)

- 가장 오른쪽부터 접근을 시작한다.

 

알고리즘 설명

1) 스택이 비어있다면 오큰수가 존재하지 않는다는 뜻이다. 

2) 스택이 비어있지 않다면 오큰수가 존재하는지 확인해보아야 한다.

2-1) 스택의 top이 input[i]보다 작다면 스택의 top은 다른 값들의 오큰수가 될 가능성이 0이다.

그러므로 후보 stack에서 pop을 하여 없애준다.

2-2) 스택의 top이 input[i]보다 크다면 input[i]의 오큰수는 스택의 top 값이 된다.

3) input[i]도 누군가의 오큰수가 될 수 있으므로 마지막엔 항상 stack 에 push 해준다.

 

#include<iostream>
#include<string>
#include <vector>
#include <stack>
using namespace std;

void rBig2(vector <int> &input) {
	stack <int> big;
	for (int i = input.size() - 1; i >= 0; i--)
	{
		while (!big.empty() && (input[i] >= big.top())) {
			big.pop();
		}
		if (big.empty()) {
			big.push(input[i]);
			input[i] = -1;
		}
		else {
			int temp = big.top();
			big.push(input[i]);
			input[i] = temp;
		}
	}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector <int> input(n);
	for (int i = 0; i < n; i++)
	{
		cin >> input[i];
	}

	rBig2(input);
}

https://reakwon.tistory.com/196

[스택] BOJ17298 오큰수 문제 풀이 및 전체 코드(C++)

자세한 그림과 함께 설명되어있으므로, 이해가 되지 않았다면 참고하는 것을 추천한다.

 

 

 

17299. (오등큰수) 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

#include<iostream>
#include<string>
#include <vector>
#include <stack>
using namespace std;
int freq[1000001] = {0, };

void rFreq(vector<int>input) {
	stack <int> fIndex;
	for (int i = 0; i < input.size(); i++)
	{
		while (!fIndex.empty() && freq[input[i]] > freq[input[fIndex.top()]]) {
			input[fIndex.top()] = input[i];
			fIndex.pop();
		}
		fIndex.push(i);
	}
	while (!fIndex.empty()) {
		input[fIndex.top()] = -1;
		fIndex.pop();
	}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector <int> input(n);
	for (int i = 0; i < n; i++)
	{
		cin >> input[i];
		freq[input[i]]++;
	}

	rFreq(input);
}

freq 배열을 추가로 하나 만들어주면 되는 문제이다. 

 

 

자료구조 문제는 여기서 마무리 하도록 하겠다.

나중에 시간이 되면 자료구조 참고문제를 풀어봐야겠다.