백준 17298 - 오큰수

 

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

17298번: 오큰수

스택 자료구조를 이용해 필요한 값만 저장해야 한다.

 

이 필요한 값을 무엇으로 설정하느냐에 따라 풀이가 두 가지로 나뉜다.

 

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);

* 이 코드는 다른 분의 블로그를 참고한 코드인데 출처가 기억나지 않습니다. 주인께서 읽으시면 알려주세요