G17298. 오큰수

문제

제출 코드

• 1차시도 - 시간초과

  • 배열을 뒤 순서부터 읽어가면서, 순차적으로 크기가 증가하는 리스트를 만들어뒀다.
  • 배열의 숫자를 하나 읽을때마다 저장해둔 리스트의 앞부분부터 숫자를 비교해서, 현재 숫자보다 작은 수를 가지는 리스트의 앞부분들은 모두 지우고 현재 숫자를 넣는 식으로 코드 작성
  • 위 과정에서 크기비교를 위해 매 타임마다 저장해둔 리스트를 앞에서부터 읽어오는 것이 시간이 오래걸린 듯 했다.

  package gold;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.LinkedList;
  
  public class G17298_NGE {
  
  	public static void main(String[] args) throws IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
  		int N = Integer.parseInt(br.readLine());
  		String[] num = br.readLine().split(" ");
  
  		StringBuilder result = new StringBuilder();
  		LinkedList<Integer> list = new LinkedList<>();
  		result.append("-1");
  		list.add(Integer.parseInt(num[N-1]));
  
  		for(int i=N-2; i>=0; i--) {
  			int now = Integer.parseInt(num[i]);
  			boolean inserted = false;
  			while(!list.isEmpty()) {
  				int head = list.peek();
  				if(head > now) {
  					result.insert(0, head + " ");
  					inserted = true;
  					break;
  				}else {
  					list.poll();
  				}
  			}
  			if(!inserted) result.insert(0, "-1 ");
  			list.addFirst(now);
  		}
  		System.out.println(result);
  	}
  }
  

• 2차시도 - 성공

  • 뒤에서부터 순차적으로 NGE를 계산하는 방법으로 변경
  • NGE값을 저장하지 않고 해당 값의 인덱스를 저장
  • 로직은 다음과 같다.
    1. 바로 옆 배열의 숫자와 크기비교.
    2. 그 숫자가 NGE일시, 현재 숫자의 NGE값으로 그 숫자의 인덱스 값 저장.
    3. 그 숫자가 NGE가 아닐 시, 그 숫자의 NGE로 저장된 값의 위치를 찾아간다.
    4. NGE를 찾을때까지 1~3 반복.
    5. 인덱스가 -1인 값을 찾을 경우, NGE에 -1을 저장하고 다음 턴으로 넘어간다.

  package gold;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class G17298_NGE {
  
  	public static void main(String[] args) throws IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  
  		// 1. 입력
  		int N = Integer.parseInt(br.readLine());
  		String[] s = br.readLine().split(" ");
  		int num[] = new int[N];
  		for(int i=0; i<N; i++) num[i] = Integer.parseInt(s[i]);
  
  		// 2. 각 배열마다 해당 NGE의 인덱스 계산
  		int[] NGE_idx = new int[N];
  		NGE_idx[N-1] = -1;
  
  		for(int i=N-2; i>=0; i--) {
  			int p = i+1;
  			while(p!=-1) {
  				if(num[i]<num[p]) {
  					NGE_idx[i] = p;
  					break;
  				}else {
  					p = NGE_idx[p];
  				}
  			}
  			if(p==-1) NGE_idx[i] = -1;
  		}
  
  		// 3. 출력
  		StringBuilder sb = new StringBuilder();
  		for(int i=0; i<N; i++) {
  			if(NGE_idx[i]==-1) sb.append("-1");
  			else sb.append(num[NGE_idx[i]]);
  			if(i<N-1) sb.append(" ");
  		}
  		System.out.println(sb);
  	}
  }