백준 2493번 탑 [Stack] :: 마이구미

이번 글은 백준 알고리즘 2493번 문제 "탑" 을 다뤄본다.

스택을 응용한 문제이다.

백준 2493번 탑 문제 - https://www.acmicpc.net/problem/2493

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 

모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 

그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 

높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 

높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때,

 각 각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라. 

위 문제를 그림으로 표현하면 쉽게 이해가 간다.

아래 그림을 보자.

포토샵을 다루질 못해 이거 만든다고 10분 걸렸다....

위 그림의 화살표를 보자.

4인 탑은 7인 탑이 수신한다.

7인 탑은 9인 탑이 수신한다.

5인 탑은 9인 탑이 수신한다.

9인 탑은 아무도 수신하지 못한다.

6인 탑은 아무도 수신하지 못한다.

문제는 이해했으리라 생각한다.

그렇다면 어떻게 접근을 할 수 있을까?

문제의 알고리즘 분류를 보면 스택이라는 걸 볼 수 있다.

스택을 통해 문제를 해결해보자.

문제를 통해 2가지를 알 수 있다.

1. 현재 탑은 가장 가까이 있는 좌측 탑부터 비교한다.

2. 현재 탑보다 큰 높이는 가진 탑을 수신한다.

이것을 조금 더 생각해보면, 규칙 아닌 규칙을 발견할 수 있다.

9 5 7 3 2의 경우 7은 9에 닿는다.

5를 무시해도 무방하는 것이 보이는가?

또한 7 오른쪽에 있는 탑들도 사실상 7에 닿기 때문에 7 좌측의 탑을 무시해도 무방하다.

얻은 결론은 좌측 탑을 비교할 때 현재 탑보다 낮다면 비교할 필요가 없다는 것이다.

그렇게 되면, 스택에는 현재의 탑보다 높은 탑이 존재하되, top에는 현재 탑을 기준으로 높은 탑이 존재하게 된다.

예를 들어 6 9 5 7 4 가 주어졌을 때를 보자. (첫번째 탑을 넣고 시작한다)

스택에는 6이 존재한다.

1. 현재 탑 9와 스택 top(6)를 비교한다.

2. 현재 탑보다 top이 작으므로 더이상 필요없으므로, pop을 시킨 후 현재 탑을 넣는다.

3. 현재 탑 5와 스택 top(9) 를 비교한다.

4. 현재 탑보다 스택 top(9) 가 크므로, 다른 탑들이 수신할 수도 있으므로, pop 시키지 않는다.

    현재 탑 또한 스택에 넣음으로써 현재 탑이 스택의 top이 된다. (우선순위는 거리이기 때문이다.)

5. 현재 탑 7과 스택 top(5) 를 비교한다.

6. 현재 탑보다 top이 작으므로 더이상 필요없으므로, pop을 시킨 후 현재 탑을 넣는다.

........반복

이와 같은 과정을 반복한다,

이 문제는 시간초과가 많이 뜨는 문제이다.

하지만 스택의 top은 수신받을 탑이기 때문에 일일이 탑들을 찾거나, 비교하는 작업을 할 필요가 없기 때문에 시간 초과를 피할 수 있게 된다.

for(int i=2;i<=n;i++) {
    int value = sc.nextInt();

    while(!rootStack.isEmpty()) {
        if (value < rootStack.peek()) {
            sb.append(indexStack.peek() + " ");
            break;
        }
        rootStack.pop();
    }
    rootStack.push(value);
}

위와 같은 느낌으로 구현된다.

문제는 위치를 찾는 문제이기 때문에 index 관련 스택을 하나 더 만들어서 사용하면 된다.

어려울 거 없다. 높이가 저장된 스택과 똑같이 사용하면 된다.

단순히 인덱스를 위한 스택이다.

for(int i=2;i<=n;i++) {
    int value = sc.nextInt();

    while(!rootStack.isEmpty()) {
        if (value < rootStack.peek()) {
            break;
        }
        rootStack.pop();
        indexStack.pop();
    }

    rootStack.push(value);
    indexStack.push(i);
}

스택의 top을 아주 잘 활용할 수 있는 문제이다.

전체 소스를 통해 확인하길 바란다.

BufferedReader를 통해 문자열을 한번에 받을 경우 런타임 에러가 뜬다.

이유는 정확히 모른다. (너무 길어서 그렇다고 가늠할 수밖에..)

하나씩 입력값을 받아서 작업하길 바란다.

백준 2493번 탑 문제 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/2493.java