<BOJ>2493번: 탑

라모스·2021년 9월 12일
0

BOJ

목록 보기
2/22
post-thumbnail

문제


2493번: 탑

접근

  • 탑이 수평 직선에 일렬로 서 있고, 모든 탑에선 탑 순서의 반대 방향(왼쪽 방향)으로 레이저를 발사함.
  • 레이저를 발사할 때 가장 먼저 만나는 단 하나의 탑이 수신 가능하다는 점을 주목하자.
  • 발사한 탑보다 높이가 낮으면 수신 불가.
  • 레이저를 수신하는 탑이 존재하지 않을 수도 있음.

내 코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static Stack<int[]> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            while (!stack.isEmpty()) {
                if (stack.peek()[0] < temp) stack.pop();
                else {
                    sb.append(stack.peek()[1] + " ");
                    break;
                }
            }
            if (stack.isEmpty())
                sb.append(0 + " ");
            stack.push(new int[] {temp, i+1});
        }
        System.out.println(sb);
    }
}
  • 스택에 int타입 배열을 넣는데, 인자는 높이와 번호이다.
  • 어차피 루프를 돌면서 탑의 높이를 입력 받기 때문에 해당 인덱스 번호도 같이 저장하기 위해 배열로 표현한다.
  • 스택에 배열 하나하나가 들어가면 탑의 정보가 하나하나 들어가는 것이다.
  • 바로 옆에 위치한 탑의 높이를 비교할 때, peek() 메소드를 적절히 사용할 것.
  • 가장 먼저 수신하는 탑의 번호를 리턴시켜야 하기 때문에 스택의 상단에 어떤 정보가 있는지를 고려할 것.

이 문제를 풀 때, '하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다' 라는 조건을 제대로 읽지 않고 풀다가 몇 시간동안 고민했다.

'맞왜틀' 과정을 거치고 엉뚱한데서 저 조건을 읽지 않았음을 깨닫게 되자 바로 답을 도출해 낼 수 있었다.

profile
Step by step goes a long way.

0개의 댓글