[백준][JAVA] 2493 탑

바킹독 스택강의를 듣고 응용문제를 풀면서 생각했던 과정들이다!!

📌문제 설명

백준 2493 탑

 

일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다.

 

조건

1. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사한다.
2. 모든 탑에는 레이저 신호를 수신하는 장치가 설치되어 있다.
3. 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예시 6, 9, 5, 7, 4

예시의 그림 설명

이렇게 생각하면 된다!!

그래서 출력이 0 0 2 2 4가 나온다.

1번과 2번 탑은 아무곳도 안닿아서 0이 출력되고 3번과 4번 탑은 2번탑에 막히기 때문에 2가 출력된다. 그리고 5번탑은 4번탑에 막혀서 4가 출력된다!!

💡생각

처음에는 스택과 관련된 강의를 듣는 중 푸는 연습문제라서 스택을 이용해서 접근을 해야겠다고 생각했다!! 그래서 두개의 스택을 이용해서 Push와 Pop을 서로 반복하면서 Stack의 사이즈를 이용해서 문제를 해결하려고 했었다.

나의 생각

이런식으로 생각을 하고 접근을 했는데 갈수록 코드가 복잡해지고 예제 이외의 다른 반례를 넣었을때 오류가 발생할 수 있겠다고 생각했다. 생각끝에 해결을 못했고 바킹독 스택 응용문제의 정답 코드를 확인하고 풀이를 진행했다!!

🔥풀이

코드에서는 하나를 넣고 비교를 진행하고 있었다.

만약 스택에 들어와 있는 값과 비교를 했을 때 자신의 값이 더 크다면 계속해서 POP를 수행하는 구조였다. 그리고 자신의 높이보다 큰 탑을 만났을 때 해당 탑의 위치를 출력하고 push해주는 구조였다!!

풀이!!

문제를 풀때 좀 더 단순하게 생각할 필요가 있는 거 같다!!

import java.io.*;
import java.util.Stack;
public class Main {
    static class Pair{
        int x;
        int y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        public int getX(){return x;}
        public int getY(){return y;}
    }
    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];
        String[] str = br.readLine().split(" ");
        int i = 0;
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(100000000, i));
        for(String temp : str){
            i++;
            while(stack.peek().getX()<Integer.parseInt(temp)){
                stack.pop();
            }
            System.out.print(stack.peek().getY()+" ");
            stack.push(new Pair(Integer.parseInt(temp), i) );
        }
    }
}