Algorithm/Java

[백준/JAVA] 2493번: 탑

dbfl9911 2024. 10. 19. 15:42
반응형

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

 

📌 문제 설명 요약

  • KOI 통신연구소에서는 왼쪽 방향으로 레이저 신호를 보내는 탑들의 구조를 실험 중입니다.
  • 각 탑에서 발사한 레이저 신호는 가장 먼저 만나는 왼쪽에 있는 탑에서만 수신됩니다.
  • N개의 탑이 있을 때, 각각의 탑에서 발사한 레이저 신호를 수신한 탑의 번호를 출력하는 프로그램을 작성합니다.

- 오답 노트

 

❌ 기존 오답 코드

import java.io.*;
import java.util.*;

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()); // 5
        Stack<int[]> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 6 9 5 7 4

        for(int i = 1; i <= N; i++) {
            int height = Integer.parseInt(st.nextToken());
            stack.push(new int[]{i, height}); // 탑들의 [번호, 높이] 순서로 저장
            // stack[[1,6], [2,9], [3,5], [4,7], [5,4]]
        }

        String answer = "";
        while(!stack.isEmpty()) {
            int[] a = stack.pop(); // [5,4]
            int[] b = stack.peek(); // [4,7]
            // [[1,6], [2,9], [3,5], [4,7]]

            if(a[1] <= b[1]) { // ex) 4 < 7
                // 탑 번호 답에 추가
                answer += b[0]; // 4
            } else{ // ex) 7 > 5   ---> 다음 비교로 넘어감 7 < 9
                // a = [4,7]    ----> a = [4,7]
                // b = [3,5]    ----> b = [2,9]
                // [[1,6], [2,9], [3,5]]

            }

        }


    }
}

 

📌 기존 코드의 문제점

  1. 스택 활용 부족
    • 기존 코드에서는 탑의 높이를 비교할 때, stack.pop()과 stack.peek()를 통해 하나씩 비교해가는 구조였습니다. 이렇게 접근하면 모든 탑을 계속해서 검사해야 하므로 불필요한 연산이 발생합니다.
    • 효율적으로 스택을 활용하여 높이가 낮은 탑은 제거하면서 비교하는 방식이 아니어서, 시간 복잡도에서 불리하게 작용합니다.
  2. 코드의 반복과 비효율성
    • 기존 코드에서는 stack.pop()과 stack.peek()를 반복하며 왼쪽 방향의 모든 탑을 비교하고 있지만, 현재 탑보다 낮은 탑들은 제거해도 상관없습니다. 높이가 높은 탑만 남겨두면 레이저 신호가 도달하지 않는 탑을 배제할 수 있습니다.
  3. 출력 방식의 문제
    • 코드의 결과를 String answer로 누적하여 저장하려 했지만, 이는 반복문을 계속해서 수행하게 만들어 출력 성능을 떨어뜨립니다.
    • BufferedWriter와 같은 성능 최적화 출력을 사용하면 효율적으로 답을 출력할 수 있습니다.

 

 

 

 

- 올바른 풀이

 

📌 개선된 접근 방법

  • 스택 활용
    • 각 탑을 스택에 넣으면서 현재 탑보다 낮은 높이의 탑은 모두 제거합니다. 낮은 탑은 현재 탑에 의해 가려지기 때문에 제거해도 무방합니다.
    • 스택에는 [탑의 번호, 탑의 높이]를 저장하여, 특정 탑의 신호가 수신될 경우 가장 가까운 높이가 높은 탑을 쉽게 조회할 수 있게 합니다.
  • 최적화된 출력 방식
    • 결과값을 String answer로 누적하는 대신 BufferedWriter를 사용하여 출력 성능을 높였습니다.
stack.peek()과 height 비교
1. stack이 비어있을 때 stack[(1,6)] 추가
   answer 첫번째 값은 0
2. stack [(1,6)]과 height 9 비교 ---> stack 6이 더 작으므로 stack에서 [1,6] 제거
   answer 두번째 값은 0
3. stack [(2,9)]와 height 5 비교 ---> stack 9가 더 큼 ---> stack[[2,9], [3,5]]
   answer 세번째 값은 2
4. stack [(3,5)]와 height 7 비교 ---> stack 3이 더 작으므로 stack에서 [3,5] 제거
   stack [(2,9)]와 height 7 비교 ---> stack 9가 더 큼 ---> stack[[2,9], [4,7]]
   answer 네번째 값은 2
5. stack [(4,7)]와 height 4 비교 ---> stack 7이 더 큼
   answer 다섯번째 값은 4

 

for(int i = 1; i <= N; i++) {
            // stack.peek()과 height 비교
            int height = Integer.parseInt(st.nextToken()); // 6

            while(!stack.isEmpty() && stack.peek()[1] < height) {
                stack.pop();
            }

            if(!stack.isEmpty()) {
                answer[i-1] = stack.peek()[0];
            }

            // stack[[1,6], [2,9], [3,5], [4,7], [5,4]]
            stack.push(new int[]{i, height}); // 탑들의 [번호, 높이] 순서로 저장
        }

while을 사용하는 이유는 현재 탑이 왼쪽에 있는 여러 개의 낮은 탑들을 모두 건너뛰고, 가장 가까운 높은 탑을 찾아야 하기 때문입니다.

 

if를 쓴다면, 현재 탑 바로 왼쪽에 있는 탑 하나만 검사할 수 있습니다. 하지만, 현재 탑보다 낮은 높이의 탑이 연속으로 여러 개 있다면, 이 탑들은 신호를 수신할 수 없기 때문에 모두 건너뛰어야 합니다. 그래서 while을 사용하여 연속된 낮은 탑들을 모두 제거하고, 가장 가까운 높은 탑만 남기는 겁니다.

 

 

📌 정답 코드

import java.io.*;
import java.util.*;

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()); // 5
        Stack<int[]> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 6 9 5 7 4
        int[] answer = new int[N];

        for(int i = 1; i <= N; i++) {
            // stack.peek()과 height 비교
            // 1. stack이 비어있을 때 stack[(1,6)] 추가
            //    answer 첫번째 값은 0
            // 2. stack [(1,6)]과 height 9 비교 ---> stack 6이 더 작으므로 stack에서 [1,6] 제거
            //    answer 두번째 값은 0
            // 3. stack [(2,9)]와 height 5 비교 ---> stack 9가 더 큼 ---> stack[[2,9], [3,5]]
            //    answer 세번째 값은 2
            // 4. stack [(3,5)]와 height 7 비교 ---> stack 3이 더 작으므로 stack에서 [3,5] 제거
            //    stack [(2,9)]와 height 7 비교 ---> stack 9가 더 큼 ---> stack[[2,9], [4,7]]
            //    answer 네번째 값은 2
            // 5. stack [(4,7)]와 height 4 비교 ---> stack 7이 더 큼
            //    answer 다섯번째 값은 4
            int height = Integer.parseInt(st.nextToken()); // 6

            while(!stack.isEmpty() && stack.peek()[1] < height) {
                stack.pop();
            }

            if(!stack.isEmpty()) {
                answer[i-1] = stack.peek()[0];
            }

            // stack[[1,6], [2,9], [3,5], [4,7], [5,4]]
            stack.push(new int[]{i, height}); // 탑들의 [번호, 높이] 순서로 저장
        }

        // 결과 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 0; i < N; i++) {
            bw.write(answer[i] + " ");
        }
        bw.flush();
        bw.close();
    }
}
반응형