[문제] 백준 2493번 탑

* 출처: 백준 www.acmicpc.net/problem/2493

2493번: 탑

내 생각

 

1. 첫번째 풀이 (시간 초과)

Stack을 두개 두어서 탑을 왔다갔다 시켰다. 결국 스택으로 완전 탐색한 꼴이다.

이렇게 하면 답은 나오지만 시간 초과다.

// 스택 2개 이용 => 시간 초과
public class BOJ_2493_wrong {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(in.readLine());	// 탑 개수
		
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		
		Stack<int[]> original = new Stack<int[]>();
		Stack<int[]> finished = new Stack<int[]>();	// 옮겨 담을 탑
		
		int[] answer = new int[N+1];	// 답안 배열
		
		// init original stack
		for(int i=1;i<=N;i++) {
			int[] building = new int[2];
			int height = Integer.parseInt(st.nextToken());
			building[0] = i;		// 번호
			building[1] = height;	// 높이
			original.push(building);
		}
		
		while(true) {
		//	if(original.isEmpty()) break;
			
			int added = 0;
			int[] target = original.pop();
			finished.push(target);
			
			// 나보다 높이 큰 탑 찾기 (original 스택 끝까지!)
			while(!original.isEmpty()) {
				int[] tmp = original.pop();
				finished.push(tmp);
				added++;
				
				if(tmp[1]> target[1]) {	// 높이 비교: 송신 가능하다면 
					answer[target[0]] = tmp[0];	// 답안 작성
					
					for(int i=0;i<added;i++) {	// original 스택으로 원상 복귀
						original.push(finished.pop());
					}
					break;
				}
			}
			// 못찾았을 때
			if(original.isEmpty()) {
				answer[target[0]] = 0;
				for(int i=0;i<added;i++) {
					original.push(finished.pop());
				}
				break;
			}
			
		}
		
		for(int i=1;i<=N;i++) {
			System.out.print(answer[i]+ " ");
		}
	
	}
}

 

2. 두번째 풀이(***)

 

이 풀이에서의 핵심은, 어차피 내 앞에 있는 탑이 나보다 낮다면, 내 뒤에 있는 탑들은 내 앞에 있는 탑에 송신을 할 수 없다는 점이다. 그래서 스택에서 아예 제외시킨다. 

스택에는 나를 기준으로 나보다 높은 탑들만 적재되는 것이다.

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(in.readLine()); // 탑 개수
		Stack<int[]> stack = new Stack<>();	// 탑 번호, 높이 저장
		
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		
		for(int i=1;i<=N;i++) {
			int currentHeight = Integer.parseInt(st.nextToken());	// 현재 기준 탑의 높이
			while(!stack.isEmpty()) {		// 스택에는 앞에 나보다 큰 거 이외에는 없게 된다.
				int tmp = stack.peek()[1];
				if(tmp>currentHeight) {
					sb.append(stack.peek()[0]).append(' ');
					break;
				}else {
					stack.pop();	// 남아있는 탑이 높이가 나보다 낮다면, 뒤에 있는 탑은 어차피 내가 수신가능할 테니 없애도 된다.
				}
			}
			
			if(stack.isEmpty()) {
				sb.append("0 ");
			}
			stack.push(new int[] {i,currentHeight});	//나를 넣는다.
		}
		System.out.println(sb);
	}
}

 

3. 세번째 풀이 (***)

 

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		String s[] = in.readLine().split(" ");
		int[] tops = new int[N];// 탑의 높이 저장 배열
		int[] ans = new int[N];	// 탑번호 저장 배열
		for(int i=0;i<N;i++) {
			tops[i] = Integer.parseInt(s[i]);
			ans[i] = -1;
		}
		
		for(int i=0;i<N;i++) {
			int currTop = tops[i];	//현재 탑의 높이
			int idx = i-1;			// 이전 탑의 번호
			while(idx >= 0) {
				if(tops[idx]> currTop) {	// 이전 인덱스의 탑의 높이가 더 높다면
					ans[i] = idx;		// 정답
					break;
				}else {					// 해당 인덱스의 높이가 낮다면
					idx = ans[idx];		// 그 인덱스보다 높이가 높은 인덱스로 이동
				}
			}
		}
		for(int i=0;i<N;i++) {
			System.out.print((ans[i]+1) +" ");
		}
	}
}