[알고리즘] 백준 - 17298번 : 오큰수

알고리즘 문제 출처 : https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

내가 작성한 코드

헷갈려서 많이 헤맸던 문제. 스택 없이도 풀어볼 수 있을 것 같아서 이중 for문으로 도전했다가 시간 초과가 나왔다. 이후 스택을 2개를 사용해보기도 했지만 애시당초 접근이 틀렸다. 자료의 크기가 최대 백만개이므로 이중 반복문을 돌릴 경우 백만의 제곱만큼 시간 복잡도가 소요된다. 

각설하고, 이 문제는 오큰수를 만나지 못한 인덱스를 스택에 넣어야 한다. 우선 0번째 인덱스를 스택에 넣어주고 1부터 시작한다.

for문 1번째 차례) 스택에 있는 0번째 인덱스의 값과 1번째 값을 비교하는데 1번째 값이 더 크다면 오큰수가 되므로 스택에서 0번째 인덱스를 제거하고 answer[0]에 1번째 값을 저장한다. 그리고 1번째 인덱스를 스택에 넣는다.

for문 2번째 차례) 그 다음 1번째 인덱스의 값과 2번째 값을 비교하는데 2번째 값이 더 크지 않다면 2번째 값은 오큰수가 되지 않는다. 그렇다면 2번째 인덱스 또한 오큰수를 만나지 못한 인덱스가 되므로 스택에 넣는다. 

for문 3번째 차례) 현재 스택에는 인덱스 2와 인덱스 1이 있다. 제일 위에 있는 2번째 인덱스의 값과 3번째 값을 비교하는데 3번째 값이 더 크다면 스택에서 인덱스 2를 제거한다. 그렇게 되면 인덱스 1이 제일 위로 오게 되고 인덱스 1과 3번째 값을 비교한다. 계속해서 반복

이렇게 되면 O(N^2)만큼 시간이 소요되는 이중 반복문을 돌릴 필요 없이 O(N)만으로 문제를 해결할 수 있게 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Stack<Integer> stack = new Stack<>(); //아직 오큰수를 만나지 못한 인덱스를 담는다.
		int n = Integer.parseInt(br.readLine());
		String[] numStr = br.readLine().split(" ");
		int[] numInt = new int[n]; //입력받은 숫자를 담을 배열
		int[] answer = new int[n]; //정답을 담을 배열
		for(int i=0; i<n; i++) {//String 배열을 int 배열로
			numInt[i] = Integer.parseInt(numStr[i]);
		}
		stack.push(0); //첫번째 인덱스는 미리 담음
		for(int i=1; i<n; i++) {
			if(stack.isEmpty()) {//스택이 비어있으면 현재 차례 인덱스를 담는다.
				stack.push(i);
			}
			while(!stack.isEmpty() && numInt[stack.peek()]<numInt[i]) {//스택이 비어있지 않고, 오큰수를 찾았다면
				answer[stack.pop()] = numInt[i]; //스택에서 제거하고 정답에 추가
				//스택에서 제거했으니까 그 밑에 있던 인덱스가 가장 위로 오고 반복문 진행
			}
			stack.push(i);//반복문 다음 단계를 위해 현재 차례 인덱스를 담음
		}
		for(int i=0; i<n; i++) {
			if(answer[i]==0) {//오큰수가 없는 수라면
				bw.write(-1+" ");
			}else {
				bw.write(answer[i]+" ");
			}
		}
		bw.flush();
		bw.close();
	}
}