Baekjoon17298: 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

추상화

반복문을 사용해서 풀 수 있을까 생각했지만 N의 크기가 100만까지므로 1초라는 시간 안에 연산을 못할 것으로 예상했다.
스택을 이용해서 풀 수 밖에 없는 문제인 것 같다. 

          오큰수로 값을 바꿔주기 위해서 숫자들의 배치 순서는 계속 유지되어야 한다.(스택을 두 개 사용하지 않는 배열+스택)

1) 스택 안에 숫자를 넣는다는 고정관념을 버린다
       → 숫자자체를 넣을 수도 있지만 숫자를 넣은 배열 index를 넣을 수도 있다
       → 숫자를 잠시 저장한다 = index 를 스택에 넣고 큰 수를 만날 때마다 stack최상단 index부터 값을 바꾼다

2) 규칙성의 이해: 수열을 다음과 같이 가정한다: 3 5 2 7 9 5 4 8

3	5	2	7	9	5	4	8
0	1	2	3	4	5	6	7

      → 각각에는 index가 있다고 한다: 0 ~7
      → index[0] 일 때: 3이다, 일단 3의 값은 냅둔다 stack = index[0]
           index[1] 일 때: 3보다 큰 5를 만났으므로 index[0]은 5로 바뀐다. index[1]은 아직 5의 값을 저장한다.
                                    stack = index[1]
           index[2] 일 때: 2는 5보다 작다. 값이 아직 바뀌지 않았다. 2의 값은 저장한다. stack = index[1], index[2]
           index[3] 일 때: 7을 만났다 2보다 크다. index[2] = 7이고 index[1]도 저장된 값이 5이므로 7로 바꾼다. 7은 저장한다 
                                    stack = index[3]
           index[4] 일 때: 9를 만났다. 7보다 크다 index[3]= 9이고 현재 index는 9값을 가진다. stack = index[4]
           index[5] 일 때: 5는 9보다 작으므로 5라는 값은 저장된 채 지나간다. stack = index[4], index[5]
           index[6] 일 때: 현재 저장된 최소값 5보다 작으므로 값을 저장하고 지나간다. stack = index[4], index[5], index[6]
           index[7] 일 때: 현재 저장된 최소값 4보다 크므로 이전 저장된 index[6]=8, index[5]=8. stack = index[4]

3) 현재 저장하고 있는 index 중 최소값보다 커지는 수를 만날 때 스택에 저장된 값을 바꾼다
       i) 현재 가지고 있는 최소값을 3이라고할 때 3이 최소값이므로 모두 3보다 크다. 그 값들을 { 10, 8, 6, 5, 3 } 이라고 한다
      ii) 3보다 큰 7을 만났다고 하면 모두 값은 바뀌고 스택에는 { 10, 8, 7 } 이 남게된다. 최소값은 7이된다
     iii) 만약 ii)에서 7이 아닌 같은 3을 만났으면 최소값은 3, 더 작은 수 2를 만났으면 최소값은 2가 될 것이다
     iv) 즉 무슨 절차를 밟든 현재항은 무조건 최소값이 된다. 
      v) 현재항이 최소값이면? 현재항을 제외하면 이전항이 최소값이 된다
            → 결론: stack에 남아있는 index의 값은 내림차순(3 2 1)정렬이 된다

4) 3)의 결론을 통한 코드화
   i) 배열을 0~N-1까지 탐색, 현재 배열의 값을 이전 배열의 값과 비교
  ii) 현재 배열의 값이 작든 크든 이 배열의 값은 최소값이 되며 stack에 push된다.
  ii) stack에 저장된 top부분에 해당하는 수와 배열의 수를 계속 비교해 배열의 값이 stack의 top보다 커지는 순간
      현재 배열의 값이 최소값이 될 때까지 stack의 index를 삭제한다

BufferedReader

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
	static int[] arr;
public static void main(String[] args) throws IOException{
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 Stack<Integer> stack = new Stack<Integer>();
	 StringBuilder sb = new StringBuilder();
	 StringTokenizer st;
	 int N = Integer.parseInt(br.readLine());
	 arr = new int[N];
	 st = new StringTokenizer(br.readLine()," ");
	for(int i=0; st.hasMoreTokens(); i++) {
		arr[i] = Integer.parseInt(st.nextToken());}
     //여기까지 입력값을 통해 수열을 배열 안에 집어넣음   
        
        
	stack.push(0); //처음 index는 비교할 것이 없으므로 넣어주고 시작한다
	
    for(int i=1; i<N; i++) {
  
		while(!stack.isEmpty() && arr[i]>arr[stack.peek()]) {
					arr[stack.pop()] = arr[i]; }
        //arr[i]가 arr[i-1]보다 작을 때는 어차피 아래 push를 통해 index가 추가된다
        //arr[i]가 arr[i-1]보다 커지는 순간은 연산이 시작된다
        //arr[i-1]과 비교하지 않고 저장되어있는 값 모두와 비교하므로 arr[stack.peek()]와 비교한다
		
        stack.push(i);
	//현재 수가 이전 수보다 크기가 작든 크든 시행 마지막에 stack에 현재 수의 index가 저장된다
    
	}
	while(stack.size()!=0) {
		arr[stack.pop()] = -1;}//stack에 남아있는 index는 모두 -1로 바꿔준다
        
	for(int i=0; i<N; i++) {
		sb.append(arr[i]+" ");
	} //배열을 텍스트화
    
	System.out.print(sb.toString());
}}

 

Scanner

import java.io.*;
import java.util.Scanner;
import java.util.Stack;
public class Main {
	static int[] arr;
public static void main(String[] args) throws IOException{
	 Stack<Integer> stack = new Stack<Integer>();
	 StringBuilder sb = new StringBuilder();
	 Scanner sc = new Scanner(System.in);
	 int N = sc.nextInt();
	 arr = new int[N];
	 arr[0]=sc.nextInt();
	stack.push(0); 
	for(int i=1; i<N; i++) {
		arr[i]=sc.nextInt(); //scanner기 때문에 따로 하나씩 빼서 쓸 수 있다
		while(!stack.isEmpty() && arr[i]>arr[stack.peek()]) {
					arr[stack.pop()] = arr[i]; }
		stack.push(i);
	}
	while(stack.size()!=0) {
		arr[stack.pop()] = -1;}
	for(int i=0; i<N; i++) {
		sb.append(arr[i]+" ");
	}
	System.out.print(sb.toString());
}}

*코드의 길이는 줄었지만 메모리 사용은 급증했다