[백준] 2493번 - 탑 (Java)

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

2493번: 탑

 

<분석>
레이저 신호는 탑의 왼쪽으로 쏘면, 그 탑보다 큰 탑에서만 수신할 수 있다.
각각의 탐에서 발사한 레이저 신호를 어느 탑에서 수신하는지 번호를 출력한다.

<풀이>
i번째 탑보다 왼쪽에 있는 탑이 크면 수신이 가능하다.
N의 범위가 <= 500,000이므로 이중 루프를 사용하면 시간복잡도가 O(N^2)이므로 스택을 사용해서 시간복잡도를 줄여야 한다.
스택에 있는 탑과 i번째 탑을 비교해서 같거나 작으면 스택에서 제거한다. 그리고 stack.peek()을 출력하면 된다.
수신하는 탑이 없으면 0을 출력한다.

 

<코드>

import java.util.Scanner;
import java.util.Stack;
import java.lang.StringBuilder;

//[백준] 2493번 - 탑수시 (Java)

public class Main {
	static int N;
    static int H[];

    public class Top {
        int index;
        int height;
        Top (int i, int h) {
            this.index = i;
            this.height = h;
        }
    }
	public void InputData()
	{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
        H = new int[N+1];
		for (int i = 1; i <=N; i++) // 건물번호를 1번 to N
		{
			H[i] = sc.nextInt();
		}
		sc.close();
	}
	
	public void Solve() {
        Stack<Top> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        // i번째 탑이 쏜 레이저를 수신하는 탑의 수 구하기 (높이가 더 높은 탐만 스택 삽입)
        for (int i=1; i<=N; i++) {
            // 스택에 있는 탑과 i번째 탑의 높이 비교
            while (!stack.isEmpty() && stack.peek().height <= H[i]) {
                // 스택의 탑이 i번째 탑과 높이가 같거나 작으면 삭제
                stack.pop(); // 제거 후 스택의 다른 탑도 비교
            }
            if (stack.isEmpty()) { // 수신할 탑이 없으면 0 출력
                sb.append("0"+" ");
            } else { // 수신한 탑이 있으면 탑의 번호 출력
                sb.append(stack.peek().index+" ");
            }
            stack.push(new Top(i, H[i])); // i번째 탑을 스택에 일단 삽입
        }
        System.out.println(sb.toString());
	}
    
	public static void main(String[] args) 
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<결과>

14분 만에 코딩까지 완료해서 제출했으나 메모리 초과가 발생함.

계속 메모리 초과를 수정하기 위해서 여기저기 수정해 봤으나 해결이 안됨.

어쩔 수 없이 백준 게시판을 검색해보다가 Scanner가 의외로 메모리를 많이 잡아먹으니 BufferedReader를 사용해서 입력값을 처리하라는 글을 보고 수정했더니 통과함. 코딩의 간편함 때문에 입력값 처리시에 Scanner를 사용했었는데 앞으로는 BufferedReader를 사용하도록 습관을 바꿔야겠음.

 

<코드 - BufferedReader 사용>

import java.util.Scanner;
import java.util.Stack;
import java.lang.StringBuilder;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

//[백준] 2493번 - 탑 (Java)

public class Main {
    static int N;
    static int H[];

	public void InputData() throws IOException
	{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        H = new int[N+1];
		for (int i = 1; i <=N; i++) // 건물번호를 1번 to N
		{
            H[i] = Integer.parseInt(st.nextToken());
		}
	}
	
	public void Solve() {
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        // i번째 탑이 쏜 레이저를 수신하는 탑의 수 구하기 (높이가 더 높은 탐만 스택 삽입)
        for (int i=1; i<=N; i++) {
            // 스택에 있는 탑과 i번째 탑의 높이 비교
            while (!stack.isEmpty() && H[stack.peek()] <= H[i]) {
                // 스택의 탑이 i번째 탑과 높이가 같거나 작으면 삭제
                stack.pop(); // 제거 후 스택의 다른 탑도 비교
            }
            if (stack.isEmpty()) { // 수신할 탑이 없으면 0 출력
                sb.append("0"+" ");
            } else { // 수신한 탑이 있으면 탑의 번호 출력
                sb.append(stack.peek()+" ");
            }
            stack.push(i); // i번째 탑의 번호를 스택에 일단 삽입
        }
        System.out.println(sb.toString());
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출>