[BOJ] 2493.탑(stack).java

#. Problem

www.acmicpc.net/problem/2493

* The copyright in this matter is in BOJ

 

#. Resolution Process

1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it

#. Solve

스택 자료구조를 활용해서 어떻게 문제를 해결할지가 포인트이다.

 

앞에서부터 타워를 확인하는 방법도 있고

뒤에서부터 타워를 확인하는 방법도 있다.

#. Code_front

먼저 앞에서부터 타워를 확인하는 방법이다.

 

1. 현재 타워 앞에 또 다른 타워가 없다면(Stack이 비어있다면)

    수신을 받을 타워가 없는 것이므로 res[]에 0을 저장해준다.

2. 현재 타워 앞에 수신을 받을 수 있는지 확인해볼 수 있는 타워가 있다면(Stack이 비어있지 않다면)

    Stack의 top과 비교를 해주는데

    현재 타워가 더 높다면 Stack의 top을 빼내고

    현재 타워가 더 낮다면 Stack의 top에 해당하는 타워의 번호를 res[]에 저장해준다.

    ->  이 과정은 Stack이 비어있지 않고, 현재 타워보다 높은 타워를 찾을 때까지 반복

3. 모든 동작이 끝나고 현재 타워 정보를 Stack에 추가해준다.

 

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

public class BOJ2493 {

	static int N, res[];
	static class Tower {
		int num, height;

		public Tower(int num, int height) {
			this.num = num;
			this.height = height;
		}
		
	}
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		res = new int[N + 1];
		Stack<Tower> towers = new Stack<>();
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			
			int h = Integer.parseInt(st.nextToken());
			
			while(!towers.isEmpty()) {
				// 지금 타워가 더 높다면 pop
				if(towers.peek().height < h) {
					towers.pop();
				} 
				// 지금 타워가 더 낮다면 앞 타워 번호를 저장
				else {
					res[i] = towers.peek().num;
					break;
				}
			}
			
			// 수신을 받을 타워가 없다면
			if(towers.isEmpty()) {
				res[i] = 0;
			}
			
			towers.add(new Tower(i, h));
		}
		
		for (int i = 1; i <= N; i++) {
			System.out.print(res[i] + " ");
		}
	}

}

#. Code_back

다음으로 뒤에서부터 타워를 확인하는 방법이다.

 

1. Stack 이 비어있다면 현재 타워 번호를 Stack에 추가해준다.

2. Stack이 비어있지 않고, i번째 타워가 Stack의 top에 해당하는 타워보다 크다면 

    Stack의 top에 해당하는 타워는 i번을 저장하고 Stack에서 빼내는 과정을 반복한다.

3. 동작이 끝나면 i번째 타워를  Stack에 추가해준다.

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

public class BOJ2493_v2 {

	static int N, res[], towers[];

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		res = new int[N + 1];
		towers = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			towers[i] = Integer.parseInt(st.nextToken());
		}

		solve();

		for (int i = 1; i <= N; i++) {
			System.out.print(res[i] + " ");
		}
	}

	private static void solve() {
	
		Stack<Integer> st = new Stack<>();
		
		for (int i = N; i >= 1; i--) {
			// Stack이 비어있다면 push
			if(st.isEmpty()) st.push(i);
			else {
				// Stack이 비어있지 않고, i번째 타워가 stack의 top보다 크다면
				while(!st.isEmpty() && towers[i] > towers[st.peek()]) {
					// stack의 top을 빼내고 stack top index에 i번을 저장
					res[st.pop()] = i;
				}
				// 동작이 끝나면 i번째 타워를 stack push
				st.push(i);
			}
			
		}
		
	}

}