문제 링크 : https://www.acmicpc.net/problem/17298
이 문제는 주어진 N의 값이 1,000,000이므로 완전탐색으로 풀 경우 반복문을 2번 이상 돌게 되어 시간 초과가 나게 됩니다. 따라서 이 문제는 반복을 최소로 하면서 어떻게 효과적으로 문제를 해결할 수 있을지에 대한 고민이 필요합니다.
이 문제는 문제 자체를 잘 해석해보면 쉽게 접근할 수 있습니다. 오큰수를 구하는 방법은 자기 자신보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 수입니다. 즉 여기서 쪼개서 생각해볼 수 있는 부분은 크게 3가지입니다.
- 자기 자신보다 크다
- 자기 자신보다 오른쪽에 있다
- 여러 후보군들 중 가장 왼쪽에 있다(가장 먼저 나온 값이다)
위의 3가지 조건을 코드로 구현하면 됩니다. 반복문을 돌려 자기 자신에서부터 오른쪽으로 이동시키고(2번 조건 만족), 자기 자신보다 크다면(1번 조건 만족), 결과 배열에 넣은 후 더 이상 오른쪽으로 이동시키지 않는 방법으로 구현하면 됩니다.(3번 조건 만족)
하지만 이 부분을 코드로 직접 구현하기에는 복잡한 부분이 많았습니다. 우선 문제에 나와 있는 [9,5,4,8]의 경우처럼 제일 앞의 수가 가장 클 경우 배열을 다시 한 번 돌아야하기 때문에 결국 시간 초과가 발생합니다.
따라서 이 부분을 해결하기 위해 스택을 사용한 임시 저장 공간을 도입했습니다. 자기 자신의 인덱스를 스택에 저장하고, 반복문을 통해 오른쪽으로 계속 이동시키다가 스택의 peek 값보다 큰 값이 나타나게 된다면 스택 안에 저장되어있는 모든 인덱스를 현재의 수로 치환, 그렇지 않다면 다시 스택에 인덱스를 저장하여 궁극적으로 스택에는 현재 바라보고 있는 수보다 작은 수들만 존재하게 되어 오큰수를 확인할 수 있습니다.
스택을 사용한 이유는 자기 자신의 수가 아닌 오른쪽으로 이동 중에 발견되는 수를 기준으로 가장 왼쪽에 있는 수가 가장 최근에 검사한 수이기 때문입니다. 즉 LIFO 구조로 되어 있기 때문에 스택으로 문제를 해결하였습니다.
다음은 문제 풀이 코드입니다.
import java.util.*;
import java.io.*;
public class Main{
static int N;
static int[] req = new int[1000001];
static int[] res = new int[1000001];
static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
req[i] = Integer.parseInt(st.nextToken());
res[i] = -1;
}
for(int i=0;i<N;i++){
// 스택에 있는 가장 최근의 숫자와 현재 숫자와 비교해서 현재 숫자가 더 클 경우 스택에 있는 모든 인덱스를 현재 숫자로 넣기
while(!stack.isEmpty() && req[stack.peek()] < req[i]){
int idx = stack.pop();
res[idx] = req[i];
}
// 현재 숫자의 인덱스를 저장
stack.push(i);
}
// 출력 수가 많기 때문에 반복문을 돌려 System.out 진행 시 너무 느림
// StringBuilder를 통해 한번에 출력
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++){
sb.append(res[i]);
sb.append(" ");
}
System.out.println(sb);
}
}
