공부 85일차: 백준 17298번 오큰수 자바 Java

17298 오큰수

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

 

---

백준 17298번 문제 오큰수

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

알고리즘 분류를 눌러보면 알 수 있듯이, 스택으로 풀라고 분류된 문제이다

 

스택이 아니라 다음과 같이 일반 배열로 풀게 되면

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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        int num = 0;
        int answer = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 0; i < n; i++) {
            num = arr[i];
            
            for(int j = i+1; j < n; j++) {
                if(num < arr[j]) {
                    answer = arr[j];
                    break;
                }
                else {
                    answer = -1;
                }
            }
            
            if(num == arr[n-1])
                answer = -1;
            
            System.out.print(answer+" ");
        }
        
 
    }
 
}
 

 

이클립스에선 답이 잘 도출되지만 백준에선 시간 초과가 뜬다

 

 

따라서 스택을 이용해서 풀 생각을 하고 접근해야 한다

https://st-lab.tistory.com/196

시간복잡도 때문에 대부분 인덱스값을 사용하는데,

위의 블로그가 배열도 한 개만 만들고 그림도 이해하기 쉬워서 참고했다

 

그림이 친절하게 나와있긴 하지만, 더 제대로 이해하기 위해 내가 예제를 토대로 과정을 서술해보았다

 

arr[] = { 3, 5, 2, 7 }

 

stack empty → push

stack [  ]

 

push(0)  → push 하는 순간 다음 숫자로 넘어감

stack [ 0 ]

 

arr[stack.peek() (=0)] < arr[1 → push한 0 다음 숫자]

3 < 5

arr[stack.pop() (=0)] = arr[1]

stack [  ]

 

stack empty → push

stack [  ]

 

push(1) → push 하는 순간 다음 숫자로 넘어감

stack [ 1 ]

 

arr[stack.peek() (=1)] > arr[2 → push한 1 다음 숫자]

5 > 2

stack [ 1 ]

 

arr[stack.peek()] > arr[i] → push

push(2) → push 하는 순간 다음 숫자로 넘어감

stack [ 1 , 2 ]

 

arr[stack.peek() (=2)] < arr[3 → push한 2 다음 숫자]

arr[stack.pop() (=2) = arr[3]

stack [ 1 ]

 

배열이 비어있지 않으므로 한 번 더

arr[stack.peek() (=1)] < arr[3]

arr[stack.pop() (=1)] = arr[3]

stack [  ]

 

stack empty → push

stack [  ]

 

push(3) → push 하는순간 다음 숫자로 넘어가지만 주어진 배열의 인덱스 끝자리라 다음 없음

stack [ 3 ]

 

반복문 종료

 

스택에 있는 수 = 오른쪽에 해당 수보다 큰 자리가 없었던 수, 즉 오큰수가 없는 수스택이 빌 때까지 arr[stack.pop() (=3)] = -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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack();
        
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());    //입력된 숫자대로 배열 채우기
        }
        
        for(int i = 0; i < n; i++) {
            
            while(!stack.empty() && arr[stack.peek()] < arr[i]) {    //스택이 비어있지 않고 스택[맨윗값]이 스택[현재순서]값이 작다면
                arr[stack.pop()] = arr[i];    //arr[스택맨윗값]의 오큰수는 arr[현재순서]
            }
            
            stack.push(i);    //스택이 비어있거나 arr[스택맨윗값]이 더 크다면 push / push하면 비교값은 arr[push한 수+1]로 넘어간다
        }
        
        while(!stack.empty()) {
            arr[stack.pop()] = -1;    //스택에 남아 있는 수 = 오큰수가 없는 수의 값을 -1로
            
        }
        
        for(int i = 0; i < n; i++) {
            sb.append(arr[i]).append(' ');    //arr[0] ~ arr[n-1] 차례대로 나열
        }
        
        System.out.println(sb);
    }
 
}
 

 

위에 적은대로, 주석에 적은대로 짜봤다

(참고한 블로그를 보니 똑같았다)

 

 

 

---

혼자 엄청 고민하던 문제도 다른 사람들 풀이를 보면 허무하기도 하고 재밌기도 하고 얼른 그렇게 되고 싶기도 하고..