백준
백준 17298 - 오큰수
황태건
2023. 8. 2. 12:14
https://www.acmicpc.net/problem/17298
17298번: 오큰수
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
www.acmicpc.net
스택 자료구조를 이용해 필요한 값만 저장해야 한다.
이 필요한 값을 무엇으로 설정하느냐에 따라 풀이가 두 가지로 나뉜다.
1. 오름차순으로 증가하는 수열의 원소
첫 번째 값을 제외한 나머지 원소들 중, 오름차순으로 증가하는 원소들만 스택에 저장하면 된다.
이를 구현하기 위해 배열의 끝에서부터 역으로 순회하며, 현재 확인하는 배열의 원소가 스택의 top보다 작아지도록 스택을 관리한다.
while (!S.empty() && S.top() <= A[i]) S.pop();
2. '오큰수'를 구하지 못한 인덱스
이번에는 배열의 시작부터 정방향으로 순회한다. 매 반복문마다, 스택에 저장된 인덱스들에 대해 그 인덱스에 해당하는 수와 현재 확인하는 원소를 비교한다. 현재 원소가 더 클 경우 현재 원소는 스택의 인덱스보다 큰(오른쪽에 있는) 수 중 값이 더 큰 수 이므로 오큰수이다.
현재 인덱스에서는 다음 원소를 확인할 수 없으므로, 즉 오큰수를 구할 수 없으므로 현재 인덱스는 무조건 스택에 저장한다.
//NGE[i] : i번 원소의 오큰수
while (!S.empty() && v[i] > v[S.top()]) {
NGE[S.top()] = v[i];
S.pop();
}
S.push(i);
* 이 코드는 다른 분의 블로그를 참고한 코드인데 출처가 기억나지 않습니다. 주인께서 읽으시면 알려주세요