[BaekJoon] 백준 2493번_탑 for JAVA

 

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

2493번: 탑

 

 

 

 

---

 

내 탑보다 높이가 같거나 큰 탑의 인덱스를 차례대로 출력하는 문제이다.

 

 

탑의 개수가 500,000개 이길래 되지 않을까? 하고 for문으로 갈겼는데 시간 초과가 떴다.

 

 

틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int map[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N+1];
		
		if(N==1) {
			System.out.println("0");
			return;
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++)
			map[i] = Integer.parseInt(st.nextToken());
		
		StringBuilder sb = new StringBuilder();
		sb.append(0).append(' '); // 첫번째는 무조건 0
		for(int i = 2; i <= N; i++) {
			sb.append(find(i)).append(' ');
		}
		
		System.out.println(sb);

	}
	public static int find(int n) {
		for(int i = n-1; i > 0; i--) {
			if(map[i] >= map[n]) return i;
		}
		return 0;
	}

}

 

 

시간 초과가 떠서 괴로워졌음...

 

솔직히 여기서 아이디어 생각이 안나서 다른 사람들꺼 찾아봤다.

 

 

그랬더니 다들 stack을 사용했다!!

 

그러니까 애초에 탑의 높이를 받아오면서 스택에 쌓으면 시간 복잡도가 O(n)이 된다 ㄷㄷ

 

 

스택을 어떻게 사용하냐면... 일단 예시에 있던 6 9 5 7 4를 살펴보자

 

 

예시 탑 그림

 

일단 첫번째 탑의 높이는 6, 두번째는 9이다.

 

그러면 세번째 탑은 9 이상이 아니라면 무조건 두번째 탑이 나와야 한다.

 

만약에 세번째 탑이 9 이상이었다면 네번째 탑은 (세번째 탑보다 크지 않다면) 세번째 탑에 닿게 된다.

 

 

이게 반복을 줄일 수 있는 아이디어이다.

 

 

그렇다면.. 어딘가에 넣어놨던 탑의 높이보다 다음으로 훑은 탑의 높이가 크다면 그 전의 탑은 없애줘도 될 것이다.

 

-> 여기서 stack을 사용해야겠다는 아이디어가 나와야한다.

 

제일 나중에 들어온 놈과 비교해야하기 때문임.

 

그니까 예를 들어 탑의 높이가

 

 

예시

 

이렇게 1,2,3번째에서 차례대로 높아진다고 치자.

 

그러면 네번째는 3번째보다 작은지 먼저 비교해야 한다.

 

그러니까 제일 나중에 들어온 탑과 비교를 먼저 해야한다는 뜻이다. -> 아~ 스택을 써야겠구나! 해야한다...

 

 

 

ㅇㅋ 아이디어는 확인했다!

 

그렇다면 우리가 스택에 넣어야하는건

 

1. 비교할 탑의 높이

2. 그 탑의 번호

 

두 가지 이다.

 

그래서 우리는 탑에 저 두개를 함께 넣어야 한다. 스택에는 배열을 넣을 수 있으므로 배열로 넣을거임

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int map[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N+1];
		
		if(N==1) {
			System.out.println("0");
			return;
		}
		
		Stack<int[]> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
        
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++) {
			int top = Integer.parseInt(st.nextToken());
			
			while(!stack.isEmpty()) { // 앞에 탑이 걸릴때까지 돈다. 안걸리면 밑에서 0 넣어줌
				if(stack.peek()[0] >= top) {
					sb.append(stack.peek()[1]+ " ");
					break;
				}
				stack.pop();
			}
            
			if(stack.isEmpty()) sb.append("0 "); // 스택이 비었으면 0넣어준다.
			stack.push(new int[] {top, i}); // 방금 훑은놈 스택에 넣어줌
			
		}
		
		System.out.println(sb);
			

	}

}

 

 

코드는 이렇게 된다.

 

while문으로 도는 이유는 앞에 탑이 걸릴 때까지 도는거임

 

 

안걸려서 다 사라졌으면 밑에서 0 넣어주고

 

그렇다는건 지금 탐색한애가 제일 크다는거니까 얘에서 뒤에 애들이 걸리겠지 그래서 그냥 푸시로 넣어주면 됨

 

 

 

성능

 

 

성능이 좋진 않다.

 

근데 문제에서 요구하는 방법은 맞는 것 같다.~~