[백준] 탑 2493번 (🥇 골드5)

사이트

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

 

문제

 

분석

실수

문제 자체는 이해하는데에 어렵지 않았다.. 하지만 필자가 잘못짚어서 계속 해맸다...

 

먼저 필자는 List를 이용해 풀려고 했다. 계속 비교하면서 제거하고 하면 되지 않을까? 라는 생각을 해봤다.  

package datastructure;

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

public class DataStructure2493 {

    static List<Integer> top = new ArrayList<>();
    static int n;
    static List<Integer> result = new ArrayList<>();

    static int information = 0;

    static int index = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            int input_num = Integer.parseInt(st.nextToken());
            top.add(input_num);


            if (i != 0) {
                if (information < input_num) {
                    information = input_num;
                    index = i;
                    result.add(0);
                } else if (information == input_num) {
                    result.add(0);
                } else {
                    for (int j = i - 1; j >= index; j--) {
                        if (input_num < top.get(j)) {
                            result.add(j + 1);
                            break;
                        }
                    }
                }
            } else {
                information = input_num;
                index = i;
                result.add(0);
            }
        }

        for (Integer i : result) {
            System.out.print(i + " ");
        }
    }


}

 

코드는 이렇다. 시간초과를 생각해서 입력받을 때부터 비교를 하고 하는 식으로 했으나....

그 결과 시간초과가 계속 떴다... 물론 테스트 케이스는 다 맞았다... 

 

 

하지만 코드의 문제점은 좀 보였다. n은 최대 500,000까지 받을 수 있다. 

그러나 필자의 코드대로 진행을 하면 최악의 경우의 수일때가 있다.

 

간단한 예시를 보면 첫번째 탑이 100,000,000 이고 마지막 500,000 탑이 99,999,999 이고 중간에는  마지막 탑보다 큰 탑이 없다 무조건 첫번째 탑이다!!!

 

그럼 이렇게 볼때 마지막 탑은 첫번째 탑으로 가기 위해 500,000 번을 돌아야된다 ㅋㅋㅋㅋㅋ 그러니 시간초과가 뜰 수밖에 

 

그래서 이 문제의 핵심은 Stack이다! 즉 초반 부터 비교해서 아닌것들은 제거하는 식으로 가야될거 같다.

 

성공

package datastructure;

import javax.swing.plaf.nimbus.State;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class DataStructure2493 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<int[]> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();


        for (int i = 0; i < n; i++) {
            int top = Integer.parseInt(st.nextToken());
            boolean flag = false;
            while (!stack.isEmpty()) {
                if (stack.peek()[0] > top) {
                    sb.append(stack.peek()[1]);
                    sb.append(" ");
                    stack.push(new int[]{top,i+1});
                    flag=true;
                    break;
                }
                stack.pop();
            }
            if(!flag){
                sb.append("0 ");
                stack.push(new int[]{top,i+1});
            }
        }

        System.out.println(sb.toString().trim());

    }


}

 

이게 전체 코드이다. 차근차근 보자! 

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Stack<int[]> stack = new Stack<>();
StringBuilder sb = new StringBuilder();

 

먼저 초기 설정은 위와 같이 해두었다. 참고로 sb는 출력하기 위해 넣었다.

 

for (int i = 0; i < n; i++) {
    int top = Integer.parseInt(st.nextToken());
    boolean flag = false;
    while (!stack.isEmpty()) {
        if (stack.peek()[0] > top) {
            sb.append(stack.peek()[1]);
            sb.append(" ");
            stack.push(new int[]{top,i+1});
            flag=true;
            break;
        }
        stack.pop();
    }
    if(!flag){
        sb.append("0 ");
        stack.push(new int[]{top,i+1});
    }
}

 

당연히 입력받을 때부터 비교하도록 진행을 시켜두었다! 

 

일단 입력이 문제와 같이 6 9 5 7 4 로 가정을 해보자! 

 

처음 top 변수가 5가 된다. 그리고 while로 들어오고 싶으나 스택이 없으므로 바로 if문으로 간다. 

당연히 flag가 false이므로 sb에 0을 추가하고 stack에 푸쉬하고 자취를 감친다... 

 

다음 top 변수가 9가 된다. while로 들어오게 되는데 d이 또한 if 문에 걸리지 않아서 stack.pop()을 하게 된다!! 

그럼 또 다 비어서 if 문으로 가게 되고 이 또한 0을 추가하고 statck에 푸쉬하고 자취를 감친다.

 

다음 top 변수가 5가 된다. while로 들어오게 되고 이때 if문에 걸린다. 그 후 이전 9의 위치인 2번째인 2를 sb에 추가하고 push를 한다음 braek를 하면서 while이 끝나게 된다.!! 

 

다음 top 변수는 7이 된다. while로 들어오게 되고 5 > 7 이 안맞으므로 pop()을 해서 5는 제거가 되고 다시 9 > 7 비교를 한다. 당연히 성립이 되고 또 9의 위치인 2가 추가되서 계속 진행된다!!!

 

이런식으로 쭉 진행하면 불필요한 비교또한 안해도 되고 시간 절약을 할 수 있다. 

 

 

 

전체 코드

package datastructure;

import javax.swing.plaf.nimbus.State;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class DataStructure2493 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<int[]> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();


        for (int i = 0; i < n; i++) {
            int top = Integer.parseInt(st.nextToken());
            boolean flag = false;
            while (!stack.isEmpty()) {
                if (stack.peek()[0] > top) {
                    sb.append(stack.peek()[1]);
                    sb.append(" ");
                    stack.push(new int[]{top,i+1});
                    flag=true;
                    break;
                }
                stack.pop();
            }
            if(!flag){
                sb.append("0 ");
                stack.push(new int[]{top,i+1});
            }
        }

        System.out.println(sb.toString().trim());

    }


}

 

결과

느낀점

 

엄청 쉬운 문제였는데 너무 돌아서 풀었다.... 분발하자 진짜!!

취업준비때 코테는 필수니깐 열심히 해야된다.