백준 G4 2493 탑

 

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

2493번: 탑

 

기존에 푼 방법

 

완전탐색으로 하면 시간초과 나온다. 중요한 점은 탑의 높이와 탑의 위치를 저장하는게 필요하다.

이는 HashMap을 활용해도 되고 1차원 배열을 활용해도 되고 클래스를 만들어도 괜찮다.

 

다음은 내가 푼 로직이다.

왼쪽에서부터 접근할 필요는 없다고 생각했다. 왜냐하면 레이저는 오른쪽에서 왼쪽으로 쏘고 있으니깐.

 

만약 오른쪽에서 접근을 한다면 어떻게 될까?

 

 

먼저 4를 저장한다. 4보다 큰 탑의 높이를 만나면 그때 탑 높이가 4인 부분에서 출력해야할 값은 탑 높이 7의 위치일 것이다.

이렇게 되면 4는 필요가 없을 것이다. 

7을 저장한다.

5와 7을 비교한다. 7이 더 크다. 5를 저장한다.

5와 9를 비교한다. 9가 더 크다. 5는 9의 위치를 가리킬 것이다.

7과 9를 비교한다. 9가 더 크다. 7는 9의 위치를 가리킬 것이다.

 

이 과정에서 왜 스택이 필요한지 알 수 있다.

LIFO 마지막에 저장된 것을 꺼낼 수 있는 스택의 특징을 참고해서 오른쪽에서 왼쪽으로 탑을 저장하면서 가장 최근에

저장된 탑과 현재 비교해야할 탑을 서로 비교하는 것이다.

 

하지만 내 방법은 시간이 좀 걸렸다.

왜 그럴까?

1. 먼저 모든 탑의 정보를 받는 과정에서 기간이 추가된다.

2. 출력을 하는 과정에서 다시 모든 탑의 개수 만큼 배열을 돌아야 한다.

 

import java.util.*;
import java.io.*;

public class Main {
	
	static int n;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		// 탑의 위치와 높이를 저장한 map 탑의 높이는 고유한 값이다.
		Map<Integer, Integer> topMap = new HashMap<Integer, Integer>();
		// 스택 생성
		Stack<Integer> stack = new Stack<>();
		// 결과 배열
		int[] result = new int[n];
		// 탑의 높이를 저장한 배열
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// 탑의 높이를 저장
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		// 오른쪽부터 돈다.
		for(int i = n-1; i >=0; i--) {
			int curNum = arr[i];
				// 스택이 비어있으면 스택이랑 map에 넣고 멈추기
				if(stack.isEmpty()) {
					// map에는 현재 탑의 높이와 위치를 넣는다.
					topMap.put(curNum, i);
					stack.add(curNum);
				} else {
					// 스택이 비어있지 않다면 계속 비교한다.
					while(true) {
						if(stack.isEmpty()) {
							// 스택이 비어있으면 현재 값을 넣고 break;
							topMap.put(curNum, i);
							stack.add(curNum);
							break;
						}
						
						// 스택 top가져오기
						int stackTop = stack.peek();
						// 현재 높이가 스택에 있는 탑의 높이보다 크면
						if(curNum > stackTop) {
							// result[스택탑의 위치] = 현재 돌고있는 탑의 위치
							result[topMap.get(stackTop)] = i+1;
							// 스택에서 제거한다.
							stack.pop();
							
						} else {
							// 현재 높이가 스택에 있는 탑의 높이보다 작다면
							// map과 스택에 저장한다.
							topMap.put(curNum, i);
							stack.add(curNum);
							break;
						}
					
					} // end of while
				}
		}
		for(int i = 0; i < n; i++) {
			System.out.print(result[i] + " ");
		}
	}
	    
}

 

다른 사람들의 풀이방법으로도 풀어봤다.

다른 사람들은 왼쪽에서부터 타워를 추가할 때 스택이 비어있으면 해당 탑의 위치에 결과는 0을 출력하고

스택에 탑을 추가했다.

타워 높이 6을 추가하기 전에 스택은 비어있었다. 0을 해당 위치에 출력한다.

그리고 6을 추가한다.

 

타워 높이 9를 추가하기 전에 스택에서 6을 꺼내 비교해봤다. 9가 더 크네

6을 제거한다.

while문으로 다시 돌고

스택이 비어있어 0을 해당 위치에 출력하고 9를 추가한다.

타워 높이 5를 추가하기 전에 스택에서 9를 꺼내 비교해봤다. 5가 더 작네

타워 높이 5에서 쏜 레이저는 9에 맞을 것이다. 9의 위치를 정답에 출력한다.

5를 스택에 추가한다.

 

 

타워 높이 7를 추가하기 전에 스택에서 5를 꺼내 비교해봤다. 7이 더 크네

타워 높이 7에서 쏜 레이저는 5를 넘어가버릴 것이다. 5는 쓸모가 없다. 5를 pop 한다.

 

 

타워 높이 7를 추가하기 전에 스택에서 9를 꺼내 비교해봤다. 7이 더 작네

타워 높이 7에서 쏜 레이저는 9를 맞출 것이다. 9의 위치를 출력하고 스택에 7을 추가한다.

 

 

타워높이 4를 추가하기 전에 스택에서 7를 꺼내 비교해봤다. 4가 더 작네

타워 높이 4에서 쏜 레이저는 7를 맞출 것이다. 7의 위치를 출력하고 스택에 4를 추가한다.

끝 -

 

 

 

import java.util.*;
import java.io.*;

class Tower {
	int height;
	int index;
	
	public Tower(int height, int index) {
		this.height = height;
		this.index = index;
	}
}

public class Main {
	
	static int n;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		Stack<Tower> stack = new Stack<>();
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < n; i++) {
			int height = Integer.parseInt(st.nextToken());
			
			if(stack.isEmpty()) {
				sb.append("0 ");
				stack.push(new Tower(height, i+1));
			} else {
				while(true) {
					// 스택이 비어있으면 정답을 추가하고 새로운 타워를 스택에 넣자.
					if(stack.isEmpty()) {
						sb.append("0 ");
						stack.push(new Tower(height, i+1));
						break;
					}
					
					// 스택이 비어있지 않다면
					else {
						Tower tower = stack.peek();
						
						// 스택에서 꺼낸 탑의 높이가 현재 비교할 탑 높이보다 크다면
						if(tower.height > height) {
							// 현재 비교할 탑은 스택에 있는 탑에 레이저를 쏠 것이기 때문에
							// 현재 위치의 정답은 스택에 있는 탑의 위치이다.
							sb.append(tower.index + " ");
							stack.push(new Tower(height, i+1));
							break;
						} else {
							// 스택에서 꺼낸 탑의 높이가 현재 비교할 탑 높이보다 작다면
							// 스택에 있는 탑은 이제 쓸모가 없다 지워주자.
							stack.pop();
						}
					}			
				}
			}
		} // end of for
		System.out.println(sb.toString());
	}
	    
}