[백준] 2493. 탑 (자바 JAVA)

[ 문제 ]  [백준] 2493. 탑 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/2493

2493번: 탑

---

# 접근 방법 및 풀이 

 

• 단순히 for문 두개로 탐색 돌렸는데 역시나 시간초과 ㅎㅎ.. 왜 N범위를 제대로 안 읽고 푸는지.. 다시한번 느꼈다.
• 두번째는 스택으로 풀었다. 왼쪽에서 오른쪽으로 탐색할지, 오른쪽에서 왼쪽으로 탐색할지 고민해서 시간이 조금 걸렸다.
• ans[]배열을 N 크기만큼 생성해 각각의 idx에 해당하는 답을 담기로 했다.
• 스택이 비어있다면 일단 스택에 push를 해주고, 스택이 비어있지 않다면 비교해야한다.

• 0	1	2	3	4
  6	9	5	7	4

• 0부터~N-1까지 for문으로 차례대로 idx를 탐색하면서, 스택이 비어있지 않으면서 현재 내 값 top[idx]이 스택의 꼭대기 값보다 더 작다면 (stack.peek() >= top[idx]) 그 꼭대기 값의 idx+1이 정답이 될 것이다.
• 만약 top[idx] > stack.peek()보다 더 크다면, 스택에서 pop해준다.
• 그리고 top[idx]번째 값이 더 크든 안 크든 stack에 push해준다. 내 뒤에있는 값이 현재 top[idx]보다 더 작을 수 있기 때문이다.
• 그림을 그려가며 풀면 이해가 쉽게 될 것이다.
• 자세한건 코드참조

# 주의할 점 

 

• N이 50만이므로 최대 50만*50만 탐색하면 시간초과 나기때문에 다른 자료구조를 생각해봐야한다.

 

JAVA 코드

시간초과 코드 (오답)

package Gold;

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

public class bj2493_탑 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int top[] = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < top.length; i++) {
			top[i] = Integer.parseInt(st.nextToken());
		}
		int ans[] = new int[N];
		out: for (int i = N-1; i > 0; i--) {
			for (int j = i-1; j >=0 ; j--) {
				if(top[i] <= top[j]) {
					ans[i] = j+1;
					continue out;
				}
			}
		}
		for (int i = 0; i < ans.length; i++) {
			System.out.print(ans[i]);
			if(i != N-1)
				System.out.print(" ");
		}
	}
}

정답 코드

package Gold;

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

public class bj2493_탑 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int top[] = new int[N];
		StringTokenizer st = new StringTokenizer(in.readLine());
		for (int i = 0; i < top.length; i++) {
			top[i] = Integer.parseInt(st.nextToken());
		}
		int ans[] = new int[N];
		Stack<Point> stack = new Stack<Point>();
		for(int i = 0; i < N; i++) {
			if(stack.isEmpty()) {
				stack.add(new Point(i, top[i]));
			}else {
				while(!stack.isEmpty()) {
					if(stack.peek().y >= top[i]) {
						ans[i] = stack.peek().x+1;
						break;
					}else {
						stack.pop();
					}
				}
				stack.add(new Point(i, top[i]));
			}
			System.out.print(ans[i] + " ");
		}
	}
}

 

REVIEW

답을 ans배열에 넣고 따로 for문으로 ans배열 찍으니까 시간초과 나길래, 답 구하자마자 찍는걸로하니까 간신히 통과.. 다른 시간초 빠른거 보니까 StringBuilder로 찍었더라.. 그치만 바꾸기 귀찮..