[백준] 2493 - 탑

 교수님이 어렵다고 하셔서 쫄아있었는데 정말 어렵다 ,, ^^!; 

 

 야구 문제가 여러 알고리즘들이 섞이고, 야구의 룰에 따라 값들을 관리해줘서 어렵다면 이 문제는 나오는 자료구조는 스택 하나 뿐인데 그 스택을 단순한 LIFO + 다른 기능을 추가적으로 생각해봐야한다. 사실 스택문제라는 걸 알기 전까진 이 문제가 스택으로 풀릴 수 있을 거란 생각조차 못했고, 브루트포스인가 하고 생각했었다. 하지만 완전탐색이라고 하기엔 입력 범위가 너무 컸으며, 완전탐색으로 코드를 짰더니 백준에선 틀렸다고 하고, 정올에선 시간초과 에러가 났다.. 이때부터 ㄹㅇ 멘붕 시작ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

 한시간 가량 짠 코드가 아까웠지만... 이럴 땐 과감히 버려야 한다는 교수님의 말씀이 기억나서 과감히 버리고 스택으로 접근을 시도해보았다. 각 탑이 보낸 전기 신호는 탑의 왼쪽에 있고, 해당 탑보다 높이가 큰 탑만 받을 수 있다...

 

 전기 신호를 고정된 방향으로 보내고 있으며, 층수를 확인해야 하니 pop으로 층수를 확인해봐야할 것 같다는 생각이 들었다. 스택 하나로 풀려고 하니, 층수가 가지각색 뒤죽박죽인 탑들을 어떻게 처리 해야할지.. 배열을 하나 더 만들어서 관리 해야하나 .. 복잡한 생각이 들었지만 그럴수록 뭔가 더 아닌 것 같았다ㅋㅋㅋㅋㅋㅋ

 

 그러다 문득 스택을 두 개 사용해서 브라우저의 이동을 관리한 것이 생각나, 스택을 하나 더 그려보았고, 오른쪽이 위에 오도록 자리한 본래 탑 층수가 저장된 첫번째 스택(전기 신호가 왼 쪽으로 가고 있고 한 탑만 그 신호를 받을 수 있으니, 왼쪽 방향에서 가장 근접한 탑을 찾아야 하기 때문에 오른쪽탑 -> 왼쪽 탑 순서 층수를 헤아려가며 따져준다.)을 하나 씩 오른쪽 스택에 옮겨담아보았다. (뭔가 그래야 할 것 같았다... 과학실험이 생각나서..) 

 

 그렇게 옮겨 담다 보니 문득 후위연산식을 표현하기 위해 스택을 사용하던 머나먼 옛날 자료구조 수업시간이 생각났고, 스택에 값을 넣을 때 그 값을 검사하여 스택의 상태를 변경하던 것이 생각났다. 비슷한 방식으로 탑을 오른쪽탑부터 두번째 스택으로 옮겨 담은 다음에 두번째 스택에 막 입성하려고 하는 탑이 현재 두번째 스택의 peek 값보다 층수가 높다며, 현재 두번째 스택의 top 자리에 있는 탑의 신호를 받을 수 있을 것이라는 생각이 들었다. 그런 식으로 두번째 스택의 top 자리에 있는 스택은 신호 전송에 성공한 하여 최초 송신자를 이제 막 스택에 입성하려고 하는 나보다 큰 층수를 가진 탑의 인덱스로 설정하고 pop() 으로 나가준다.

 막 첫번째 스택에서 두번째 스택으로 옮겨갔거나(peek 값이 본인보다 크든 작든 본인의 신호는 왼쪽으로 만 가기 때문에 두번째 스택 안에 이미 있는 값들은 그 신호를 받지 못해 일단 자신의 왼쪽 탑이 오기를 스택에 상주하며 무작정 기다려야 함), 아직 본인 층수보다 높은 탑을 만나지 못한 탑은 pop() 되지 못하고 두번째 스택에 남아있다. 그런 식으로 가다보면 두번째 스택은 무조건 큰 층수가 아래, 작은 층수가 위에 있도록 세팅이 되며, 아직 신호 송신에 성공하지 못한 탑들이 남아있을 것이다. 

 첫번째 스택을 모두 옮겨 담은 후 두번째 스택엔 나보다 높은, 이제 막 스택에 입성하려고 하는 탑을 만나 pop() 에 성공한 탑 이외에 스택에 남아있는, 신호 전송에 실패한 탑들이 남아있을 것이며 이 탑들의 최초 송신자 값은 모두 0으로 세팅해주면 된다.

 

자바의 스택 클래스를 사용하면 간단하게 풀 수 있지만, 스택 클래스는 무척이나 크기 때문에 배열로 직접 스택을 구현하는 편이 시간 상으로 훨씬 이득이었다. 그래서 스택 클래스를 사용한 버전, 배열을 사용해 스택을 구현한 버전 두 가지를 다 작성해보았다.

 

소스코드 (스택 클래스 사용ver)

package com.ssafy.exhaustive;

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

public class Main {
	static int[] towers;
	static int N;
	static int[] firstReceiver;
	//key: 층수, value: 인덱스에 유의!
	static HashMap<Integer, Integer> map = new HashMap<>();

	// 인덱스는 +1, for문 후 stack에 남은거 0으로 처리하는거, 인덱스랑 층수 멥으로 관리하는거 잊지 마!
	public static void findFirstReceiver() {
		Stack<Integer> waiting = new Stack<>();
		
		for(int i = N-1; i >=0; i--) { //오른쪽부터 넣는 것임에도 유의...
			//waiting에서 기다리고 있던 작은 애들 tower 설정하면서 pop 시켜줌.
			while(!waiting.empty() && waiting.peek() < towers[i]) {
				firstReceiver[map.get(waiting.pop())] = i + 1;
			}
			
			waiting.push(towers[i]);
		}
		while(!waiting.empty()) {
			firstReceiver[map.get(waiting.pop())] = 0;
		}
	}

	public static void printReceivers() {
		StringBuilder Result = new StringBuilder("");
		for (int i = 0; i < N; i++) {
			Result.append(firstReceiver[i]).append(" ");
		}
		System.out.println(Result);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		towers = new int[N];
		firstReceiver = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			towers[i] = Integer.parseInt(st.nextToken());
			map.put(towers[i],i); // 층수(직접적인 비교대상) - 인덱스 메핑.
		}

		// 최초 수신탑 찾고 저장하기
		findFirstReceiver();

		// 최초 수신 탑 출력하기
		printReceivers();

	}
}

 

 

 

소스코드 (배열 사용 ver)

package com.ssafy.exhaustive;

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

public class Main {
	static int[] towers;
	static int N;
	static int[] firstReceiver;
	//key: 층수, value: 인덱스에 유의!
	static HashMap<Integer, Integer> map = new HashMap<>();
	static int[] waiting;
	static int top = -1;
	
	public static int peek() {
		return waiting[top];
	}
	
	public static int pop() {
		return waiting[top--];
	}
	
	public static void push(int num) {
		waiting[++top] = num;
	}
	
	// 인덱스는 +1, for문 후 stack에 남은거 0으로 처리하는거, 인덱스랑 층수 멥으로 관리하는거 잊지 마!
	public static void findFirstReceiver() {
		
		for(int i = N-1; i >=0; i--) { //오른쪽부터 넣는 것임에도 유의...
			//waiting에서 기다리고 있던 작은 애들 tower 설정하면서 pop 시켜줌.
			while(top != -1 && peek() < towers[i]) {
				firstReceiver[map.get(pop())] = i + 1;
			}
			
			push(towers[i]);
		}
		while(top != -1) { //top을 기준으로 해야 함 - length는 할당된 원소 수라서 0으로 채워져있으므로 정확X
			firstReceiver[map.get(pop())] = 0;
		}
	}

	public static void printReceivers() {
		StringBuilder Result = new StringBuilder("");
		for (int i = 0; i < N; i++) {
			Result.append(firstReceiver[i]).append(" ");
		}
		System.out.println(Result);
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		towers = new int[N];
		firstReceiver = new int[N];
		waiting = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++) {
			towers[i] = Integer.parseInt(st.nextToken());
			map.put(towers[i],i); // 층수(직접적인 비교대상) - 인덱스 메핑.
		}

		// 최초 수신탑 찾고 저장하기
		findFirstReceiver();

		// 최초 수신 탑 출력하기
		printReceivers();

	}
}

 

 설명할 땐 옮겨담는 것의 시각화를 위해 왼쪽부터 오른쪽까지 탑의 층수가 순서대로 저장된 배열을 첫번째 스택이라고 했지만, 실제론 인풋에서 입력받은 배열을 역순회 하는 방식으로 구현하였다. 또한 스택에 층수를 저장하여 이를 pop, peek으로 직접 비교하는 것과 동시에 그 층수를 가진 탑들의 첫번째 수신 탑을 배열에 저장해야 하기 때문에 그 층수를 이용하여 해당 탑들이 몇번째 탑인지 인덱스를 구하기 위해 HashMap 자료구조를 사용했다. 이 때 키는 층수이고 탑의 인덱스가 value이다. 인덱스를 0부터 시작하도록 했지만 문제에선 1번 부터 탑이 시작하므로 이 또한 고려해주어야 한다.

 또한 + 연산이 아닌 StringBuilder 클래스의 append 메소드를 사용해 실행시간과 메모리 사용을 줄였다. +를 사용하면 문자열을 두개씩 합치고, 이를 또 다른 메모리의 공간에 저장하지만 StringBuilder의 append 메소드를 사용하면 append 뒤에 붙은 문자열들을 한 공간에 한 번에 합치기 때문에 실행시간과 메모리 부하가 적다.

 

 

실제로 스택클래스를 사용할 때보다 배열을 사용하는 편이 다섯배 가량 더 빠르다는 것을 볼 수 있었다..

 

위가 배열, 아래가 스택 사용시