백준 17298번 오큰수

https://www.acmicpc.net/problem/17298

 

스택 1개, 배열 1개 쓰는 풀이

 

아이디어:

1. 스택에 pair<값, 인덱스> 저장

2. 값을 저장하는 배열 arr[1000001]

3. 일단 비어있으면 push, skip

4. 2493번 탑, 6198번 옥상 정원 꾸미기 문제처럼 스택의 내림차순 유지 (ex. 5 → 2 → 1(top))

5. S.top 보다 입력이 크면 입력보다 작거나 같을 때까지 모두 arr[S.top의 인덱스]에 tmp를 저장 (오큰수 기록)하고 pop

6. 스택에 입력 push

7. arr[스택에 남아있는 값들의 인덱스]에 모두 -1 저장

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int arr[1000001];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, tmp;
	stack<pair<int,int>> S;
	cin >> N;
	
	for(int i = 0; i < N; i++) {
		cin >> tmp;

		if (S.empty()) {
			S.push({ tmp, i });
			continue;
		}

		while (!S.empty() && tmp > S.top().first) {
			arr[S.top().second] = tmp;
			S.pop();	
		}

		S.push({ tmp, i });

	}

	while (!S.empty()) {
		arr[S.top().second] = -1;
		S.pop();
	}

	for (int i = 0; i < N; i ++) {
		cout << arr[i] << " ";
	}

	return 0;

}

 

 

---

스택 1개, 배열 2개 쓰는 풀이

 

풀이 참조: https://unialgames.tistory.com/entry/beakjoonproblem17298

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

 

아이디어:

1. 스택에는 "인덱스"를 넣는다.

2. 현재 수열 A[i]와 정답 수열 (나중에 출력할 수열) answer[i]를 vector로 정의한다.

3. 스택에 넣는 인덱스는 "아직 오큰수를 찾지 못한 인덱스"를 넣는다.

 

4. 최초 (0번째)에는 자연스럽게 인덱스를 스택에 push한다.

5. 스택이 비어있지않고, 스택 top의 숫자(A[myStack.top()])가 현재 수열 숫자(A[i])보다 작다면 (= 오큰수를 찾았다면)

정답 수열 answer에 입력한다.

이때, 정답 수열의 인덱스는 스택의 top에 해당하는 인덱스이다. (해당 인덱스의 오큰수를 찾았으므로)

answer[myStack.top()] = A[i]

스택에서 "오큰수를 찾은" 인덱스에 대해서 모두 pop한다.

6. 5의 과정이 끝나고 새로운 인덱스를 스택에 push한다.

 

7. 마지막에 스택이 비어있지 않다면 오큰수가 없는 인덱스들만 스택에 남은 것이다.

스택이 빌 때까지 모두 pop해주고 정답 수열에서 해당 인덱스를 모두 -1로 변경한다.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, k;

	cin >> N;

	vector<int> A(N, 0);
	vector<int> answer(N + 1, 0);
	stack<int> myStack;

	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int i = 0; i < N; i++) {

		while (!myStack.empty() && A[i] > A[myStack.top()]) { // if the stack is not empty and its top element value is lower than A[i]
			answer[myStack.top()] = A[i]; // add A[i] to the answer array
			myStack.pop(); // pop the all elements which has NGE
		}

		myStack.push(i); // push the new index

	}

	while (!myStack.empty()) {
		answer[myStack.top()] = -1; // set all the elements which don't have any NGE as -1
		myStack.pop(); // pop all the elements
	}

	for (int i = 0; i < N; i++) {
		cout << answer[i] << " ";
	}

	return 0;

}