문제 링크 : https://www.acmicpc.net/problem/24937
코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!
문제 정의
- 높이가 다른 탑 개가 존재
- 각각의 탑이 왼쪽으로 레이저를 쏠 때 신호를 수신한 탑들의 번호 구하기
- 수신하지 않는 경우 0을 출력
접근 방법
각 탑이 수신하는 레이저를 받는 탑은
수신하는 탑으로부터
- 왼쪽에 있으면서
- 높은 탑 중
- 가장 가까운 탑이 수신
이 값을 구하기 위해 스택을 사용했습니다.
- 순회할 때 스택에 인덱스를 저장
- 후보를 찾을 때 스택을 사용해서 탐색
그렇다면 스택에는 어떤 값을 넣어야 할까요?
저는 인덱스를 넣었습니다.
그 이유는 아래 사진과 같습니다.
핵심 로직
1. 레이저 수신 받을 후보 탑 탐색
// 스택에 있는 후보 탑들을 탐색 (가까운 순서부터)
while (!stack.isEmpty()) {
int candidateTop = stack.peek();
// 후보 탑이 현재 탑보다 높은 경우
if (top[candidateTop] > currentTop) {
sb.append(candidateTop).append(' ');
break;
}
// 후보 탑이 현재 탑보다 낮은 경우 -> 후보에서 제거
stack.pop();
}스택으로 현재 탑을 기준으로
- 왼쪽에 있고
- 높은 탑 중
- 가장 가까운 탑을 탐색하는 로직입니다.
2. 스택이 비어있을 때는 0을 출력
// 수신할 탑이 없는 경우
if (stack.isEmpty()) {
sb.append('0').append(' ');
}스택이 비어있다는 의미는
- 나(현재 위치의 탑)의 왼쪽에는
- 나보다 높은 탑이 없다는 것을 의미합니다.
예시
예시를 간단하게 들어보겠습니다.
아래와 같은 입력이 존재한다고 가정해보겠습니다.
5
6 9 5 7 41번 탑 탐색
첫 번째 탑을 탐색하면 어떻게 될까요?
가장 첫 번째 탑인 6인 경우
왼쪽에 자신보다 높은 탑이 없으니 0을 출력합니다.
그러고 자신이 다른 탑의 후보가 될 수 있으니 스택에 넣고요
2반 탑 탐색
두 번째 탑이 9인 경우
스택이 비어있지 않았기 때문에 스택을 조회합니다.
스택에는 1번 탑이 들어있지만
1번 탑의 높이(6)는 현재 탑의 높이(9)보다 낮으므로
이후 다른 탑의 후보가 될 수 없기 때문에 스택에서 제거됩니다.
제거된 후에는 스택이 비어있기 때문에 0을 출력하고
자신을 스택에 넣습니다.
3번 탑 탐색
3반 탑을 탐색할 때 스택에는 2번 탑만이 존재합니다.
스택으로 2번 탐을 탐색할 때 자기 자신보다 높은 탑을 만났기 때문에
해당 탑을 정답으로 출력해야하므로 세 번째 탑은 2를 출력합니다.
이후 자기 자신을 스택에 넣습니다.
4번 탑 탐색
4번 탑을 탐색할 때
스택에는 2번 탑, 3번 탑이 존재합니다.
먼저 가까이에 존재하는 3번 탑부터 탐색하지만
자신보다 크지 않기 때문에
3번 탑을 스택에서 제거하고 2번 탑을 탐색합니다.
2번 탑은 자신보다 크기 때문에
2를 출력하고 자신을 스택에 넣습니다.
5번 탑 탐색
5번 탑을 탐색할 때
스택에는 2번 탑과 4번 탑이 존재합니다.
먼저 현재 탑에 더 가깝게 존재하는 4번 탑을 확인합니다.
자신보다 크기 때문에 4를 출력하고 자신을 스택에 넣습니다.
시간복잡도
코드상으로만 보면 이라고 착각할 수 있습니다.
하지만 모든 탑은 한 번만 탐색되며
스택에는 최대 1번만 들어갔다가 나오기 떄문에
최종 시간 복잡도는 입니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
ArrayDeque<Integer> stack = new ArrayDeque<>();
int N = Integer.parseInt(br.readLine());
int[] top = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
// 각 탑들을 순회 -> 현재 탑 지정
for (int i = 1; i <= N; i++) {
int currentTop = Integer.parseInt(st.nextToken());
top[i] = currentTop;
// 스택에 있는 후보 탑들을 탐색 (가까운 순서부터)
while (!stack.isEmpty()) {
int candidateTop = stack.peek();
// 후보 탑이 현재 탑보다 높은 경우
if (top[candidateTop] > currentTop) {
sb.append(candidateTop).append(' ');
break;
}
// 후보 탑이 현재 탑보다 낮은 경우 -> 후보에서 제거
stack.pop();
}
// 수신할 탑이 없는 경우
if (stack.isEmpty()) {
sb.append('0').append(' ');
}
// 현재 탑은 이후 탑들의 수신 후보가 될 수 있으므로 스택에 추가
stack.push(i);
}
System.out.println(sb);
}
}