[백준] 2493번_탑_Java

문제 링크 👉🏻 https://www.acmicpc.net/problem/2493

👀 문제 접근

---

레이저 신호를 수신하는 탑 찾기

모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하며, 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

🔎 해결 방식

---

입력

• 탑의 수 n 을 입력한다.
• n개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다.
  탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

수신한 탑 번호 찾기

• 탑 높이가 저장된 tops 배열을 순회한다.
  • 현재 탑 높이와 stack 의 top인 인덱스에 해당하는 탑 높이와 비교한다.
  • 현재 탑 높이가 더 높으면 pop한다. stack 이 비면 while 문이 멈춘다.
    
  • stack 이 비어있지 않으면 answer[i] 를 stack.peek 에 1 더한 값을 저장한다.
    • 스택에 원소가 하나라도 있다는 것은 레이저 신호를 만나는 탑이 있다는 것을 의미
    • 스택이 비어있으면 만나는 탑이 없다는 것을 의미한다.
  • stack 에 i 를 추가한다.

💻 구현 코드

---

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

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());
        String[] input = br.readLine().split(" ");
        Stack<Integer> stack = new Stack<>();

        int[] tops = new int[n];
        int[] answer = new int[n];

				// 입력한값 Integer 변환
        for (int i = 0; i < n; i++) {
            tops[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < n; i++) {
		        // 현재 탑과 stack의 top에 저장된 인덱스의 탑 높이를 비교
		        // 현재 탑 높이가 작을때까지 pop
            while (!stack.isEmpty() && tops[i] > tops[stack.peek()]) {
                stack.pop();
            }
						
						// 스택이 비어있지 않은 경우
						// -> 레이저가 닿는 탑이 있다는 뜻
            if (!stack.isEmpty()) {
                answer[i] = stack.peek() + 1;
            }
            stack.add(i);
        }
        
        // 결과 출력
        for (int a : answer) {
            System.out.print(a + " ");
        }
    }
}

✨ 마무리

---

프로그래머스에 있는 주식가격 문제와 상당히 유사한 문제였다. 그 문제를 풀어보려고 열심히 머리를 굴려봤지만 결국 풀지 못하고 풀이의 도움을 받았다. 유사한 문제를 풀어 봤어서 이 문제는 내 힘으로 풀 수 있었던 것 같다. 시간이 좀 걸렸지만, 오랜만에 알고리즘 문제를 풀면서 문제에 대한 생각도 좀 해 봄으로써, 다시 공부에 집중하는 계기가 될 수 있을 것 같다.