[BOJ] 2493번 탑

개요

스택을 이용한 문제

N개의 높이가 서로 다른 다른 탑들이 왼쪽 방향으로 레이저 신호를 발사할 때 수신하는 탑의 번호를 출력한다.

문제링크

코드

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

public class Baekjoon2493 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] tower = new int[n];
        Stack<Integer> s = new Stack<>();
        int[] result = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0;i<n;i++)
            tower[i] = Integer.parseInt(st.nextToken());

        s.push(0);
        for(int i=1;i<n;i++) {
            while(!s.isEmpty()) {
                if(tower[i]<=tower[s.peek()]) {
                    result[i] = s.peek()+1;
                    break;
                }
                else
                    s.pop();
            }
            s.push(i);
        }
        for(int i: result)
            bw.write(i+" ");
        bw.flush();
        bw.close();
    }
}

해결 과정

처음엔 탑들의 높이를 저장하는 배열 tower[] 와 수신한 탑의 순서를 저장하는 배열 result[] 만 가지고 문제를 풀이했다.

for(int i=n-1;i>0;i--) {
    for(int j=i-1;j>=0;j--) {
        if(tower[i]<=tower[j]) {
            result[i] = j+1;
            break;
        }
    }
}

레이저가 오른쪽에서 왼쪽방향으로 나아가니깐 배열의 오른쪽부터 비교해서 i번째 탑보다 높이가 큰 j번째 탑이 나오면 결과배열에 j의 순서(j+1)을 저장하고 break로 다음 i로 이동하는 방식이다.

하지만 이방식은 불필요한 계산을 많이하게 되서 시간초과가 났다.

우리에게 필요한 것은 i번째 탑보다 큰 j번째 탑이니깐 스택을 이용해 계산을 줄여보기로 했다.

스택을 사용하면 어차피 작아서 비교할 필요도 없는 연산은 빠지게 된다.

s.push(0);
for(int i=1;i<n;i++) {
    while(!s.isEmpty()) {
        if(tower[i]<=tower[s.peek()]) {
            result[i] = s.peek()+1;
            break;
        }
        else
            s.pop();
    }
    s.push(i);
}

for문 순회마다 스택에 배열값을 삽입 해주고

배열의 i번째 값을 스택의 윗부분과 비교해서 스택이 크면 결과값에 스택에 저장된 탑의 순서를 저장하고 아니면 스택을 pop해준다.

이런식으로 필요한 부분만 비교해주니깐 해결이 되었다.

결과