[C++] 백준 2493번 탑

스택을 이용해서 푸는 문제.

우선순위 큐로도 풀 수 있는 문제다.

자료구조의 기본적인 문제라고 한다. 평이 좋았던 문제였다.

 

문제풀이

탑들은 왼쪽 방향으로 레이저 신호를 보낸다.

만일, 자신의 왼쪽에 자신의 높이보다 큰 탑이 있을 경우에, 그 탑이 자기 자신의 레이저 신호를 받는 탑이 된다.

레이저 신호는 하나의 탑만 수신 가능하다.

즉, 스택, 우선순위 큐를 이용해서 탑의 높이를 기록해두는데,

지금 내가 탐색하는 탑의 높이보다 높은 탑의 높이가 나올 때까지 pop한다.

어차피 지금 탐색하는 탑보다 낮은 높이의 탑은 필요가 없기 때문이다.

그리고 stack에 넣을 때, 해당하는 높이가 몇번째 탑인지도 기록해 주어야 한다.

 

예제 6 9 5 7 4를 예로 들어보자.

 

1. stack : empty

input : 6

-> stack : 6

 

2. stack : 6

input : 9

6 < 9, 6 pop

-> stack : 9

 

3. stack : 9

input : 5

9 > 5

-> stack : 9, 5 

 

4. stack : 9, 5

input : 7

5 < 7, 5 pop 

9 > 7

-> stack : 9, 7

 

5. stack : 9, 7

input : 4

7 > 4

-> stack : 9, 7, 4

 

굵게 칠해진 부분들이 탑에서 쏜 레이저를 왼쪽에 있는 탑이 맞았을 경우이다.

• stack이 비어있지 않고, (비어있다면 그냥 해당 탑의 높이를 stack에 push)
• 자신보다 높이가 높은 탑이 있다면,

해당 높이의 탑의 idx가 현재 탑이 쏜 레이저를 맞는 탑의 순번이다.

 

코드로 살펴보자.

 

사용한 STL과 변수

스택을 사용해서 풀기위해 stack STL을 사용했다.

• numCnt : 입력받는 숫자의 개수
• input : 입력받는 수
• st pair형 스택 : 첫번째가 탑의 index, 두번째가 탑의 높이를 나타내는 스택이다.
• tower 배열 : 각 번째 수의 탑이 쏜 레이저를 어떤 순번의 탑이 맞는지 저장해두는 배열이다.

메인함수

처음에 숫자의 수를 입력받는다.

그리고 각 입력받는 수마다 위에서 고려했던 것처럼 구현해주면 된다.

• 만일 첫번째라면, 그냥 push한다. (사실 이 부분은 지워도 될 것 같다.)
• i번째라면, 스택이 비어있지 않고 스택에 자기 자신의 높이보다 낮은 높이가 없을 때까지 스택을 pop한다.
• 위 조건을 만족했을 때, stack이 비어있지 않다면, stack의 맨 위에있는 요소가 자신이 쏜 레이저를 맞는 탑의 높이이다. 그 탑의 idx를 twoer[i]에 저장해둔다.
• 현재 탑의 정보 { 인덱스, 높이 }를 스택에 넣어준다.

 

그리고 최종적으로 각 타워가 쏜 레이저를 몇번째 탑이 맞는지를 저장하는 tower 배열을 출력해주면 된다.

 

골드5 문제였다.

아마도 스택 문제임을 몰랐을 때, 골드5 문제라고 생각이 들 것 같았다.

처음에 스택 문제인 것을 알고 접근해서 빠르게 풀 수 있었다.

120ms 풀이는 위에서 말했다시피 우선순위 큐를 사용해서 푼 것이다.

문제 자체도 스택 문제로 분류되어 있고, 풀이 시간도 스택이 더 빠르므로 따로 풀이는 올리지 않겠다.

(풀이 자체가 엄청 다르거나 하지는 않는다.)

 

GitHub - kimyunseok/study-record: my study-record

코드는 여기서 확인 가능하다.