[백준]_17298번_오큰 수 구하기[C++]

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

512 MB

63213

21530

15402

32.889%

문제

크기가 N인 수열 A = A1_A2,.. AN이 있다. 수열의 각 원소 Ai 에 대해서 오큰수 NGE(i)를 구하려고 한다.$A_i$의 오큰수는 오른쪽에 있으면서 $A_i$ 보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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

 

---

1단계 : 문제 분석

• N의 최대크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다.
  1. 스택에 새로 들어온 수가 top에 존재하는 수보다 크면 \ 그 수는 오큰수가 된다.
  2. 오큰수를 구한 후 수열에서 오큰수가 \ 존재하지 않는 숫자에 -1을 출력해야 한다.
• 핵심

2단계 ; 손으로 풀기

• 정답 배열의 값을 모두 채운 후 출력하면 문제가 요구하는 답을 구할 수 있다.

문제푸는 순서

1. 스택이 채워져 있고 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장한다. pop은 조건을 만족하는 동안 계속 반복한다. 과정 1을 마치면 과정 2로 넘어간다.
2. 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다.
3. 과정 1~2를 수열길이만큼 반복한 다음 현재 스택에 남아있는 인덱스에 -1을 저장한다.

pop은 정답 배열에 값을 추가하는 것

push는 다음 인덱스를 본다고 생각하면 된다.

1. 처음에 스택이 비어 있으므로 과정 1 없이 과정 2진행해야한다. 즉 현재 인덱스를 스택에 push 하고 다음 인덱스로 넘어간다.
   1. 인덱스 0을 push하고 다음 인덱스로 넘어간다.
2. A[1]은 5이고 A[top]은 3이므로 스택에서 pop을 수행하고 오큰수를 저장하는 결과 배열에 Result[0]에 오큰수 5를 저장한다.
3. 1회 반복으로 스택이 비었으므로 pop은 더 진행하지 않고, 인덱스1을 push하고 다음 인덱스 넘어간다.
4. A[2]는 2이고 A[top]은 5이므로 과정 2를 진행하여 push하고 다음 인덱스로 넘어간다.
5. 스택에 배열 인덱스 3이 7이므로 인덱스 1 번 과 2번이 A[2] 가 7보다 작고, A[1]도 7보다 작으므로 오큰수 7을 Result[1], Result[2]에 저장한다.
6. 수열의 길이만큼 반복 후 스택에 남아있는 index에 -1을 저장하면 정답 배열을 완성할 수 있다.

1. 스택이 비어있으므로, 0을 push, 다음 인덱스 1로 넘어간다
2. A[0] > A[1] 이므로 다시 1을 push 하고 다음 인덱스 2로 넘어간다
3. A[1] > A[2] 이므로 다시 2를 push 하고 다음 인덱스 3으로 넘어간다.
4. A[1] > A[3] 이므로 pop하고 Result[1]에 8을 저장한다.
5. A[2] > A[3] 이므로 pop하고 Result[2]에 8을 저장한다.
6. A[0] > A[3] 이므로 pop을 중단하고 3을 push한다.
7. 다음 인덱스가 없으니 3, 0을 순서대로 pop하며 정답 배열에 -1을 저장한다.

---

3단계 : 슈도 코드 작성

N(수열의 갯수), A(수열 배열), ans(정답 배열)
수열 배열 채우기 
최초 스택 초기화(0 push)

for(N만큼 반복) {
		while(스택이 비지 않고 현재 수열값이 top에 해당하는 수열보다 클 때 까지) {
				정답 배열에 오큰수를 현재 수열로 저장
				스택 pop 수행
		}
		현재 수열을 스택에 push
}

while(스택이 빌 때까지) {
		스택에 있는 인덱스에 대하여 정답 배열에 -1 저장 
		스택 pop수행 
}
정답 배열 출력

• N의 최대크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다.
  1. 스택에 새로 들어온 수가 top에 존재하는 수보다 크면 \ 그 수는 오큰수가 된다.
  2. 오큰수를 구한 후 수열에서 오큰수가 \ 존재하지 않는 숫자에 -1을 출력해야 한다.
• 핵심

2단계 ; 손으로 풀기

• 정답 배열의 값을 모두 채운 후 출력하면 문제가 요구하는 답을 구할 수 있다.

문제푸는 순서

1. 스택이 채워져 있고 A[index] > A[top]인 경우 pop한 인덱스를 이용하여 정답 수열에 오큰수를 저장한다. pop은 조건을 만족하는 동안 계속 반복한다. 과정 1을 마치면 과정 2로 넘어간다.
2. 현재 인덱스를 스택에 push하고 다음 인덱스로 넘어간다.
3. 과정 1~2를 수열길이만큼 반복한 다음 현재 스택에 남아있는 인덱스에 -1을 저장한다.

pop은 정답 배열에 값을 추가하는 것

push는 다음 인덱스를 본다고 생각하면 된다.

1. 처음에 스택이 비어 있으므로 과정 1 없이 과정 2진행해야한다. 즉 현재 인덱스를 스택에 push 하고 다음 인덱스로 넘어간다.
   1. 인덱스 0을 push하고 다음 인덱스로 넘어간다.
2. A[1]은 5이고 A[top]은 3이므로 스택에서 pop을 수행하고 오큰수를 저장하는 결과 배열에 Result[0]에 오큰수 5를 저장한다.
3. 1회 반복으로 스택이 비었으므로 pop은 더 진행하지 않고, 인덱스1을 push하고 다음 인덱스 넘어간다.
4. A[2]는 2이고 A[top]은 5이므로 과정 2를 진행하여 push하고 다음 인덱스로 넘어간다.
5. 스택에 배열 인덱스 3이 7이므로 인덱스 1 번 과 2번이 A[2] 가 7보다 작고, A[1]도 7보다 작으므로 오큰수 7을 Result[1], Result[2]에 저장한다.
6. 수열의 길이만큼 반복 후 스택에 남아있는 index에 -1을 저장하면 정답 배열을 완성할 수 있다.

1. 스택이 비어있으므로, 0을 push, 다음 인덱스 1로 넘어간다
2. A[0] > A[1] 이므로 다시 1을 push 하고 다음 인덱스 2로 넘어간다
3. A[1] > A[2] 이므로 다시 2를 push 하고 다음 인덱스 3으로 넘어간다.
4. A[1] > A[3] 이므로 pop하고 Result[1]에 8을 저장한다.
5. A[2] > A[3] 이므로 pop하고 Result[2]에 8을 저장한다.
6. A[0] > A[3] 이므로 pop을 중단하고 3을 push한다.
7. 다음 인덱스가 없으니 3, 0을 순서대로 pop하며 정답 배열에 -1을 저장한다.

---

3단계 : 슈도 코드 작성

N(수열의 갯수), A(수열 배열), ans(정답 배열)
수열 배열 채우기 
최초 스택 초기화(0 push)

for(N만큼 반복) {
		while(스택이 비지 않고 현재 수열값이 top에 해당하는 수열보다 클 때 까지) {
				정답 배열에 오큰수를 현재 수열로 저장
				스택 pop 수행
		}
		현재 수열을 스택에 push
}

while(스택이 빌 때까지) {
		스택에 있는 인덱스에 대하여 정답 배열에 -1 저장 
		스택 pop수행 
}
정답 배열 출력

---

C++

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

int main()
{
	using namespace std;
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N; //수열 갯수
	cin >> N;
	vector<int> A(N, 0); //수열 배열
	vector<int> ans(N, 0); // 정답배열

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

	stack<int> myStack;
	myStack.push(0);

	for (int i = 0; i < N; i++) {
		//스택이 비지않고 현재 수열이 스택 top위치의 값보다 크면
		while (!myStack.empty() && A[myStack.top()] < A[i]) {
			ans[myStack.top()] = A[i]; //정답 배열에 오큰수를 현재 수열로 저장
			myStack.pop(); //스택 pop수행 
		} 
		myStack.push(i); //신규데이터 push
	}

	//스택이 비워 질 때 까지
   	while (!myStack.empty()) {
		//반복문을 다 돌고 나왔는데 스택이 비지 않다면 빌 때 까지 
		ans[myStack.top()] = -1; // 스택에 있는 인덱스에 대하여 정답 배열에 -1 저장 
		myStack.pop();
	}

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