[백준BOJ] 2493번 탑.java

 

백준 저지에서 탑을 자바를 통해 풀어 보았다. 

 

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

2493번: 탑

2493번 탑.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1259번 팰린드롬수

문제

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라. 

설명

스택을 통해 풀었다. 문제가 스택과 관련된 문제라는 것을 알았기에 스택을 활용할 생각을 했지만 만약 몰랐다면 꽤 시간이 걸렸을 듯 싶다.

 

스택에는 타워가 순서대로 접근한다. 스택에 접근하려는 타워와 스택에 있는 타워들을 비교하여 타워 입장에서 스택의 top이 수신할 수 있는지 여부가 중요하다.

 

만약 스택의 top이 현재 타워보다 크다면 현재 타워 입장에서 top은 수신 가능한 타워이다. 

 

만약 스택의 top이 현재 타워보다 작다면 현재 타워 입장에서 top은 의미 없는 타워이다. 바로 pop을 수행한다. 그리고 현재 타워의 신호를 수신할 수 있는 타워가 나올 때까지 계속 pop을 진행한다. 만약 현재 타워보다 큰 top이 나온다면 그 top이 수신 가능한 타워이다. 만약 스택이 빌 때까지 진행되면 현재 타워의 신호를 수신할 수 있는 타워가 없다는 의미이므로 0을 저장한다.

 

스택에 접근할 때부터 스택이 비어있다면 0을 저장한다.

 

코드

//2493번 탑.java
package com.ssafy.boj;

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

public class 탑_2493 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] top = new int[N+1];
		int[] signal = new int[N+1];
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line," ");
		Stack<Integer> stack = new Stack<Integer>();
		
		for(int i=1;i<=N;i++) {
			top[i]=Integer.parseInt(st.nextToken());
			if(stack.isEmpty()) {
				stack.push(i);
				signal[i]=0;
			}
			else {
				if(top[stack.peek()]<top[i]) {
					while(true) {
						if(stack.isEmpty())break;
						if(top[stack.peek()]>=top[i])break;
						if(top[stack.peek()]<top[i]) {
							stack.pop();
						}
					}
					if(stack.isEmpty()) {
						signal[i]=0;
						stack.push(i);
					}
					else {
						signal[i]=stack.peek();
						stack.push(i);
					}
				}
				else {
					signal[i]=stack.peek();
					stack.push(i);
				}
			}
			sb.append(signal[i]).append(" ");
		}
		System.out.println(sb.toString());
		
	}
}