[BOJ/Java] 2493 탑

1차 시도

stack 문제이길래 순진하게도 그냥 stack으로만 하면 속도가 나오는 줄 알았다.

생각한대로 구현은 어찌저찌 해냈다. 하지만 6%에서 시간 초과... 생각해보면 당연하다. pop, push 계속 일어나고.. stack도 3개나 쓰고. 그래서 stack 사용을 포기 하고 그냥 완전탐색 방향으로 선회했다.

 

-> 코드 변수가 너무 많아지고 복잡해지면 잘못 가고 있다는 사실을 깨닫자..

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

public class BOJ2493_1st_Failure {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(in.readLine());
		Stack<int[]> stackOrigin = new Stack<int[]>(), stackTemp = new Stack<int[]>();
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 1; i <= n; i++) {
			stackOrigin.push(new int[] { Integer.parseInt(st.nextToken()), i });

		}
		int[] taken = null, nextTaken, answer = new int[n];
		int currentIndex = n - 1;
		boolean flag = true;
		while (true) {
			// 6. stack 모두 empty면 탈출
			if (stackOrigin.isEmpty() && stackTemp.isEmpty())
				break;
			if (flag == true) {
				taken = stackOrigin.pop();
			}
			// 1. taken과 nextTaken의 높이([0]) 비교
			nextTaken = stackOrigin.pop();
			// 2. 다음 pop이 크면 answer[currentIndex]에다가 nextTaken[1] 할당
			if (nextTaken[0] > taken[0]) {
				answer[currentIndex--] = nextTaken[1];
				stackOrigin.push(nextTaken);
				// 5. stackTemp.isEmpty()가 아니면 
				while (!stackTemp.isEmpty()) {
					// 다시 stackTemp.pop()을 stackOrigin에 push
					stackOrigin.push(stackTemp.pop());
				}
				flag = true;
			}
			// 4. stackOrigin.isEmpty되면 answer[currentIndex]에 0 할당
			else if (stackOrigin.isEmpty()) {
				answer[currentIndex--] = 0;
				// 5. stackTemp.isEmpty()가 아니면 
				while (!stackTemp.isEmpty()) {
					//다시 stackTemp.pop()을 stackOrigin에 push
					stackOrigin.push(stackTemp.pop());
				}
				flag = true;
			}
			// 3. 작으면 stackTemp에다가 push하고 다음 꺼내고 다시 1로
			else {
				stackTemp.push(nextTaken);
				flag = false;
			}
		}
		for (int el : answer) {
			sb.append(el).append(" ");
		}
		in.close();
		System.out.println(sb);
	}

}

 

2차 시도

단순한 탐색 구현이 됐다. 뒤에서부터 앞의 모든 것들을 비교해주고... 비교해주고...

지금 와서 다시 코드를 보니 stack이라는 개념에 꽂혀가지고 다 넣어놓고 비교할 생각을 했던 것 같다.

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

public class BOJ2493_2nd_Failure {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(in.readLine());
		int[][] originList = new int[n][2];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < n; i++) {
			originList[i] = new int[] { Integer.parseInt(st.nextToken()), i + 1 };
		}
		int[] answer = new int[n];
		for (int i = n - 1; i > 0; i--) { // 뒤에서부터 보면서
			for (int j = i - 1; j >= 0; j--) { // 앞의 것들이랑 비교해가면서
				if (originList[i][0] < originList[j][0]) {
					answer[i] = originList[j][1];
					break;
				}

			}
		}
		for (int el : answer) {
			sb.append(el).append(" ");
		}
		in.close();
		System.out.println(sb);
	}

}

 

해결 코드

결국 1시간 반이 지나도록 해결하지 못했고 반 동기들과 이야기하는 시간이 찾아왔다. 해결하신 분들이 몇 분 있어서 여러 설명을 듣다보니까 이 문제에서 이용되는 stack의 개념이 와닿아서 들은 설명을 토대로 스스로 한번 구현해봤고 결국은 통과해냈다. 감동

 

입력할때마다 비교를 해주게 되면 시간복잡도를 줄일 수 있다. 매번 입력을 그냥 다 받아놓고 하려니까 결국 완전탐색 방향으로 귀결되는 것.

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

// 중요한 포인트는 입력할 때마다 비교를 수행하는 것 -> 시간 복잡도를 줄이는 방법이 된다.
public class BOJ2493 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(in.readLine()); // 비교할 높이의 개수
		Stack<int[]> stackH = new Stack<int[]>(); // 비교할 높이를 담아 줄 stack
		StringTokenizer st = new StringTokenizer(in.readLine());
		int[] currentH, topH;
		for (int i = 1; i <= n; i++) {
			// 사용해줄 객체 { 높이, index }
			currentH = new int[] { Integer.parseInt(st.nextToken()), i };
			// stack이 비어있지 않을 때 == 현재 높이랑 비교해줄 높이가 stack 안에 있다는 것
			while (!stackH.isEmpty()) {
				topH = stackH.peek(); // stack top
				// 현재 높이보다 top이 높으면 peek의 index를 sb.append
				if (currentH[0] < topH[0]) {
					sb.append(topH[1] + " ");
					// 그 외의 stack 안의 값은 비교할 필요가 없으므로 탈출
					break;
				}
				stackH.pop();
			}
			// stack이 비어있으면 0 넣기
			if (stackH.isEmpty())
				sb.append("0 ");
			stackH.push(currentH);
		}
		in.close();
		System.out.println(sb);
	}
}