https://www.acmicpc.net/problem/2493
오답 발생한 풀이 - 시간 초과
1. 아이디어
1) 입력 각 탑의 높이를 배열 int[] heights에 저장
- 배열 index: 탑 번호
[1]~[n]사용
2) 왼쪽 탑 hegihts[1] 부터 오른쪽 탑 heights[n] 까지 확인
heights[i]에서 발사한 레이저를 수신하는 탑 번호를result[i]에 저장- 이전 왼쪽 탑들의 높이와 현재 탑의 높이
heights[i]비교
① 이전 왼쪽 탑의 높이가 더 크거나 같은 경우, 레이저 수신 O
- 이전 왼쪽 탑의 번호 출력
② 이전 왼쪽 탑의 높이가 더 작은 경우, 레이저 수신 X
- 확인한 이전 왼쪽 탑을
completed Stack에서 pop 하여,temp Stack에 push- 그 다음 왼쪽 탑과 다시 비교
temp Stack의 원소들을completed Stack으로 복구- 확인 완료한
[i]번 탑을completed Stack에 push
2. 자료구조
int[] heights: 입력 탑 높이int[] result: 출력
=>result[i]:[i]번 탑에서 발사한 레이저를 수신하는 탑 번호Stack<Pair> completed: 확인 완료된 탑의(idx, height)저장Stack<Pair> temp: 탑 높이 순서 복구하기 위한 temp 저장 용도
3. 시간 복잡도
- 왼쪽 탑 부터 오른쪽 탑 까지 차례로 레이저 수신한 탑 찾기 (전부 확인하는 방법): O(n^2)
= 0 + 1 + 2 + ... + (n-1) = (n-1)n / 2
=> n 최대값 대입: 약 125 x 10^9 >> 1.5억 (시간 초과 !!)
※ [i]번 탑이 발사한 레이저를 수신한 탑 찾기: [i-1] ~ [1]번 탑 확인
- 최대
(i-1)번 확인
코드
import java.io.*;
import java.util.*;
class Pair {
public int idx; // 탑 번호
public int height; // 탑 높이
public Pair(int idx, int height) {
this.idx = idx;
this.height = height;
}
}
public class Main_TimeOver {
static int n; // n개 탑
static int[] heights; // 각 탑의 높이
static int[] result; // 출력
static Stack<Pair> completed = new Stack<>(); // 확인 완료된 탑 (번호, 높이)
static Stack<Pair> temp = new Stack<>();
static void solution() {
// 가장 왼쪽 탑이 발사한 레이저를 수신하는 탑 존재 X
completed.push(new Pair(1, heights[1]));
result[1] = 0;
for (int i = 2; i <= n; i++) {
// [i]번 탑이 발사한 레이저를 수신하는 탑 찾기
result[i] = getReceiverTopIdx(i);
// temp 의 원소들 복구
backup();
// 확인 완료된 [i]번 탑 추가
completed.push(new Pair(i, heights[i]));
}
}
/* [idx]번 탑이 발사한 레이저를 수신하는 탑의 번호 반환 */
static int getReceiverTopIdx(int idx) {
while (!completed.isEmpty()) {
Pair completedTop = completed.peek();
if (completedTop.height >= heights[idx]) {
// [idx]번 탑이 발사한 레이저를 수신한 경우
return completedTop.idx;
}
else {
// [idx]번 탑이 발사한 레이저를 수신하지 못한 경우
// => pop() 하여 temp에 저장 후, 다음 탑 확인
temp.push(completed.pop());
}
}
return 0; // 레이저를 수신하는 탑 존재 X
}
static void backup() {
while (!temp.isEmpty()) {
completed.push(temp.pop());
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
heights = new int[n + 1]; // 탑 번호 [1] ~ [n] 사용
result = new int[n + 1];
for (int i = 1; i <= n; i++) {
heights[i] = Integer.parseInt(st.nextToken());
}
solution();
StringBuilder sb = new StringBuilder(); // 출력
for (int i = 1; i <= n; i++) {
sb.append(result[i]).append(" ");
}
System.out.println(sb);
}
}정답 풀이
1. 아이디어
1) 입력 각 탑의 높이를 배열 int[] heights에 저장
- 배열 index: 탑 번호
[1]~[n]사용
2) 왼쪽 탑 hegihts[1] 부터 오른쪽 탑 heights[n] 까지 확인
heights[i]에서 발사한 레이저를 수신하는 탑 번호를result[i]에 저장- 이전 왼쪽 탑들의 높이와 현재 탑의 높이
heights[i]비교
① 이전 왼쪽 탑의 높이가 더 크거나 같은 경우, 레이저 수신 O
- 이전 왼쪽 탑의 번호 출력
② 이전 왼쪽 탑의 높이가 더 작은 경우, 레이저 수신 X
- 확인한 더 낮은 이전 왼쪽 탑을
Stack에서 pop- 그 다음 왼쪽 탑과 다시 비교
- 확인 완료한
[i]번 탑을Stack에 push
※
Stack에서[i]번 탑보다 먼저 저장된 아이템 =[i]번 탑보다 높이가 더 큰 탑
Stack에서 비교 대상 아이템 개수를 줄임으로써, 시간 복잡도를 낮춤
2. 자료구조
int[] heights: 입력 탑 높이int[] result: 출력
=>result[i]:[i]번 탑에서 발사한 레이저를 수신하는 탑 번호Stack<Pair> stack: 확인 완료된 탑의(idx, height)저장
=> 레이저 수신 확인 과정에서,Stack에 저장된 탑들 중 현재 탑보다 낮은 높이의 탑은 pop하여 제거
3. 시간 복잡도
-
왼쪽 탑 부터 오른쪽 탑 까지 차례로 레이저 수신한 탑 찾기 (전부 확인하는 방법): O(n^2)
= 0 + 1 + 2 + ... + (n-1) = (n-1)n / 2
=> n 최대값 대입: 약 125 x 10^9 >> 1.5억 (시간 초과 !!) -
Stack에 현재 탑보다 높이가 낮은 탑을 제외시켜 비교 대상 아이템 개수 줄이는 방법: O(n^2) 미만
코드
import java.io.*;
import java.util.*;
class Pair {
public int idx; // 탑 번호
public int height; // 탑 높이
public Pair(int idx, int height) {
this.idx = idx;
this.height = height;
}
}
public class Main_Better {
static int n; // n개 탑
static int[] heights; // 각 탑의 높이
static int[] result; // 출력
static Stack<Pair> stack = new Stack<>();
static void solution() {
// 가장 왼쪽 탑이 발사한 레이저를 수신하는 탑 존재 X
stack.push(new Pair(1, heights[1]));
result[1] = 0;
// 왼쪽 탑부터 오른쪽 탑 차례로 확인
for (int i = 2; i <= n; i++) {
while (!stack.isEmpty()) {
Pair prevTop = stack.peek();
// [i]번 탑이 발사한 레이저를 수신한 경우
if (prevTop.height >= heights[i]) {
result[i] = prevTop.idx;
break;
}
// [i]번 탑이 발사한 레이저를 수신하지 못한 경우
else {
stack.pop(); // 현재 [i]번 탑보다 높이가 낮은 이전 왼쪽 탑 pop
}
}
// 확인 완료된 [i]번 탑 추가
stack.push(new Pair(i, heights[i]));
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
heights = new int[n + 1]; // 탑 번호 [1] ~ [n] 사용
result = new int[n + 1];
for (int i = 1; i <= n; i++) {
heights[i] = Integer.parseInt(st.nextToken());
}
solution();
StringBuilder sb = new StringBuilder(); // 출력
for (int i = 1; i <= n; i++) {
sb.append(result[i]).append(" ");
}
System.out.println(sb);
}
}
Silver Star