오답노트 #17298 : 오큰수

풀이방법 및 문제점

2023.01.17 (1)

시간초과가 발생했다.

논리적 풀이 방식이 틀리지는 않은 것 같다.

모든 예제가 올바르게 해결되고, 하나하나 짚어보았을 때 논리적으로 오류가 있는 부분이 없어보인다.

 

시간초과가 발생한 것은 출력 수 하나마다 새 스택을 하나씩 만들어 푸는 방법을 택해서인 것 같다.

사용하는 스택의 개수를 줄이고, 무엇보다도 add()와 pop()의 수행 횟수를 최대한 줄여야 할 것 같다.

하나의 스택만 사용해서 푸는 방법이 있을까?

 

 

사용한 풀이방법은 다음과 같다.

 

1. 입력값은 1차원 정수 배열 original에 순서대로 저장한다.

 

2. 반복문에서, 0부터 N-1까지의 i에 대하여 다음과 같은 과정을 수행한다.

 

stack을 새로 하나 만든다.

boolean 값 check를 선언하고 false로 초기화한다.

NGE(i+1)를 구한다고 가정했을 때, 입력값의 가장 뒤(original[n-1])부터 original[i]까지 역순으로 stack에 add()한다.

stack의 top을 계속 pop()하면서, top이  i+1보다 큰 경우가 발견되면 check의 값을 true로 바꾸고, 즉시 그 top을 화면에 출력하고 과정을 끝낸다.

stack의 모든 수를 확인했는데도 check의 값이 false라면 화면에 -1를 출력한다.

 

 

 

2023.01.17 (2)

스택 자료구조를 사용하지 않고 1차원 정수 배열을 인덱스로 방문하는 방식을 사용하였더니, 확실히 빨라지긴 하였다.

위의 첫 번째 방식으로 풀었을 때에는 첫 테스트케이스부터 시간초과가 발생하였지만 이번에는 약 38퍼센트까지는 해결이 되었다.

 

알고리즘 자체를 바꿔봐야겠다.

DP를 적용할 수도 있을 것 같고, 인덱스와 값을 동시에 참고하는 Comparator로 1차원 정수 배열을 최초 1회만 정렬한 뒤 이를 참고하여 문제를 풀 수도 있을 것 같다. 이러한 방법을 시도해봐야겠다.

 

코드

Java(2023.01.17 (1))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] original = new int[n];
		for(int i=0; i<n; i++) original[i] =  Integer.parseInt(st.nextToken());
		
		for(int i=0; i<n; i++) {
			int cur = original[i];
			Stack<Integer> stack = new Stack<Integer>();
			for(int j=n-1; j>i; j--) stack.add(original[j]);
			boolean check = false;
			while(!stack.isEmpty()) {
				int top = stack.pop();
				if(top > cur) {
					sb.append(top + " ");
					check = true;
					break;
				}
			}
			if(!check) sb.append(-1 + " ");
		}
		
		System.out.print(sb);
	}

}

 

 

Java(2023.01.17 (2))

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] input = new int[n];
		for(int i=0; i<n; i++) input[i] =  Integer.parseInt(st.nextToken());
		
		for(int i=0; i<n; i++) {
			boolean check = false;
			for(int j=i+1; j<n; j++) {
				if(input[j] > input[i]) {
					sb.append(input[j] + " ");
					check = true;
					break;
				}
			}
			if(!check) sb.append(-1 + " ");
		}
		
		System.out.print(sb);
	}

}