[백준 / BOJ] 2493 탑 (Java)

문제

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

2493번: 탑

서로 다른 높이를 갖고있는 N개의 탑이 있다.

이 탑을 일렬로 세우고 탑의 꼭대기에서 왼쪽으로 레이저를 발사한다.

이때, 레이저는 처음 만나는 탑만 수신할수있다.

 

각 탑에서 레이저를 발사할때, 각 탑별로 레이저를 수신하는 타워를 출력하는 문제다.

---

풀이

스택으로 푼 문제다.

N이 500,000이므로, 완탐으로 풀경우 시간초과가 발생한다.

 

문제의 조건중 "레이저는 처음 만나는 탑만 수신할수있다." 를 잘 생각해보면, 다음을 알수있다.

타워는 자기보다 더 높은 타워를 처음 발견한 순간부터, 이후에 나오는 타워에 절대로 레이저를 보낼수없다. 따라서, 모든 타워는 첫번째로 만나는 자기보다 큰 타워만 고려해된다.

 

탐색을할때, 자기보다 높은타워인경우, 스택에서 제거한후(더 이상 다른 타워로 레이저를 보낼수없기때문에) 업데이트 해주고, 낮은 타워인경우 스택에 집어넣는다.

 

쉽게말해, 이 문제를 푸는 핵심은 스택을 증가수열을 유지시키는데 있다.

 

주요 소스코드

    private void shootLaser(int num, int idx){
        while(!stack.isEmpty() && stack.peek().num < num) ans[stack.pop().idx] = idx;
        stack.add(new Num(num, idx));
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/2493%20%ED%83%91/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃