[백준] 2493. 탑

문제

 

풀이

처음에는 배열의 끝에서부터 탐색을 시작해서 자신보다 큰 값을 만날 때까지의 모든 요소들을 같이 초기화하는 방식을 생각했다. 하지만 이 경우에는 아래 방향의 화살표 모양(ex. 5 2 1 3 4) 경우를 커버하지 못해서 다른 방법을 생각해봤다.

최종적으로는 스택 두개를 사용해서 하나의 스택(A)은 입력 순서대로 들어가 있고 나머지(B)는 꺼낸 값을 저장했다. 꺼낸 값을 B 스택에 넣기 전에 B스택의 top이 더 작은 경우에는 꺼낸 값의 인덱스가 top의 결과가 된다. 인덱스를 찾는 방법에 대해서는 Map을 통해서 초기 입력시 해당 값을 key로 인덱스를 value로 저장해서 O(1)로 찾을 수 있도록 했다.

Map을 통한 구현

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		HashMap<Integer, Integer> idxMap = new HashMap<>();

		int[] result = new int[N];
		Stack<Integer> src = new Stack<>();
		Stack<Integer> ready = new Stack<>();
		
		String[] line = br.readLine().split(" ");
		for (int i = 0; i < line.length; i++) {
			int input = Integer.parseInt(line[i]);
			idxMap.put(input, i + 1);
			src.push(input);
		}
		
		while(!src.isEmpty()) {
			int top = src.pop();
			int topIdx = idxMap.get(top);
			while(!ready.isEmpty()) {
				if (top < ready.peek()) break;
				int idx = idxMap.get(ready.pop());
				result[idx-1] =  topIdx;
			}
			ready.push(top);
		}

		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}
}

Map을 사용한 경우 메모리를 너무 많이 사용해서 중복저장을 없애기 위해 값과 인덱스를 같이 가지고 있는 Tower 클래스를 정의해서 사용했고, 결과로 메모리 사용량이 1/2 정도로 감소했다.

package hw;

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

public class SolutionHW {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	static class Tower {
		int value;
		int idx;
		public Tower(int value, int idx) {
			this.value = value;
			this.idx = idx;
		}
		
		int getIdx() {
			return this.idx;
		}
		
		int getValue() {
			return this.value;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());

		int[] result = new int[N];
		Stack<Tower> src = new Stack<>();
		Stack<Tower> ready = new Stack<>();
		
		String[] line = br.readLine().split(" ");
		for (int i = 0; i < line.length; i++) {
			int input = Integer.parseInt(line[i]);
			src.push(new Tower(input, i+1));
		}
		
		while(!src.isEmpty()) {
			Tower top = src.pop();
			int topIdx = top.getIdx();
			while(!ready.isEmpty()) {
				if (top.getValue() < ready.peek().getValue()) break;
				int idx = ready.pop().getIdx();
				result[idx-1] =  topIdx;
			}
			ready.push(top);
		}

		for (int i = 0; i < result.length; i++) {
			System.out.print(result[i] + " ");
		}
	}
}

 

위의 풀이들은 소요 시간이 대략 3000ms정도 소요되는데 다른 사람들의 결과는 800ms 정도여서 더 나은 로직이 있나 고민해봤는데, 출력의 차이였다... 출력은 StringBuilder를 통해 한 번에 출력하던가 아니면 BufferedWrtier를 통해 출력해야 2~3배 정도 빠른 수행시간을 갖는다.

BufferedWriter 사용 버전

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class SolutionHW {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	static class Tower {
		int value;
		int idx;
		public Tower(int value, int idx) {
			this.value = value;
			this.idx = idx;
		}
		
		int getIdx() {
			return this.idx;
		}
		
		int getValue() {
			return this.value;
		}
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());

		int[] result = new int[N];
		Stack<Tower> src = new Stack<>();
		Stack<Tower> ready = new Stack<>();
		
		String[] line = br.readLine().split(" ");
		for (int i = 0; i < line.length; i++) {
			int input = Integer.parseInt(line[i]);
			src.push(new Tower(input, i+1));
		}
		
		while(!src.isEmpty()) {
			Tower top = src.pop();
			int topIdx = top.getIdx();
			while(!ready.isEmpty()) {
				if (top.getValue() < ready.peek().getValue()) break;
				int idx = ready.pop().getIdx();
				result[idx-1] =  topIdx;
			}
			ready.push(top);
		}

		for (int i = 0; i < result.length; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
		bw.close();
	}
}