오른쪽 후보 중 가장 가까운 답을 찾아요
앞 스택 레슨은 열린 상태를 보관했고 큐 레슨은 처리 순서를 보관했어요. 이번에는 아직 답이 될 수 있는 위치를 스택에 보관해요. 원소 값과 위치 번호는 다르므로 스택에는 번호를 넣어요.
현재 값보다 작거나 같은 오른쪽 값은 ‘더 큰 값’의 답이 될 수 없어요. 오른쪽부터 읽으면 처리한 후보들은 모두 현재 위치 뒤에 있어요. 답으로 사용할 가까운 번호가 top에 오도록 후보를 정리해요.
후보를 버려도 되는 이유를 읽어요
오른쪽에서 본 먼 값이 4이고, 그보다 가까운 새 값이 6이라면 왼쪽 원소에게 먼 4가 첫 번째 더 큰 값이 될까요? 4가 클 정도로 현재 값이 작으면 더 가까운 6도 크기 때문에 6이 먼저예요. 현재 값이 6 이상이면 4도 답이 아니에요.
따라서 더 가까운 큰 값이 온 경우 작은 먼 후보는 버릴 수 있어요. 같은 값도 엄격히 큰 답이 아니므로 비교에 등호를 포함해 제거해요. 현재 위치를 처리하고 나서 그 번호를 다음 왼쪽 원소의 후보로 넣어요.
없는 답과 중복값을 직접 확인해요
{3,1,3,5}의 각 답은 3·2·3·−1이에요. 첫 3 뒤의 같은 3은 답이 아니고 더 먼 5가 첫 큰 값이에요. 값 1의 답은 가장 가까운 오른쪽 3의 번호 2예요.
마지막 원소는 뒤에 후보가 없어 −1이에요. 빈 vector에서는 반복도 실행하지 않아요. 이 목표는 후보를 유지하는 응용이므로 처음에는 각 위치 뒤를 직접 훑어 답을 확인해도 돼요.
직접 풀어봐요
각 인덱스 i의 오른쪽에서 values[i]보다 큰 값이 처음 나오는 인덱스를 반환해요. 그런 값이 없으면 그 위치의 결과는 −1이에요. 결과 길이는 입력 길이와 같아요.
길이는 0100, 원소는 −10001000이에요. 실행용 입력은 n과 n개 값, 출력은 결과 인덱스를 공백으로 구분한 한 줄이며 빈 결과는 빈 줄이에요. 하네스가 입출력을 처리해요.
예시 1: values={2,1,4,3,5} → [2,2,4,4,-1]. 0·1번의 다음 큰 값은 2번, 2·3번의 다음 큰 값은 4번이에요.
예시 2: values={6,5,4} → [-1,-1,-1]. 모든 값의 뒤에 더 큰 값이 없어요.
예시 입력
5 2 1 4 3 5
예상 결과
2 2 4 4 -1
예시 입력
3 6 5 4
예상 결과
-1 -1 -1
핵심 개념
stack-queue: 먼 후보를 대체하는 가까운 후보 인덱스를 유지해요.