[골드5] 2493. 탑 (Java)

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

2493번: 탑

TOP!

---

※  문제를 요약하면 아래와 같습니다.

▶ 일직선 위에 N개의 탑이 각각의 높이 값을 갖고 존재

▶ 각 탑에서 레이저를 쏘았을 때 왼쪽으로 레이저가 이동되며 해당 높이 이상의 탑에 부딪혔을 때 통신됨.

▶ 레이저를 쏘았을 때 통신에 성공한 탑 번호를 출력, 통신 실패 시 0 출력

▶  Input : 첫째 줄에 탑의 갯수 N, 다음 줄에 빈칸을 구분으로 각 탑의 높이가 주어짐

▶  Output : 각 탑별로 통신에 성공한 탑 번호를 출력, 통신 실패 시 0 출력

---

◈ Input - 1

5
6 9 5 7 4

◈ Output - 1

0 0 2 2 4

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 투 포인터 탐색 시도 했다가 바로 시간초과...

▶ 각 타워의 높이 및 타워 번호를 클래스 형태로 정의

▶ 각 타워의 정보를 Tower 클래스로 입력 받아 Stack 형태로 저장

▶ 스택 안의 가장 마지막 값이 입력 값보다 크거나 같을 때 까지 pop

      ( 레이저가 부딪히려면 반드시 높이가 같거나 커야한다. )

▶ 스택 안이 비어있으면 0 출력, 값이 존재할 경우 타워의 번호 출력

---

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

class Tower {
	int m_nHeight = 0;
	int m_nNumber = 0;
	
	public Tower() {}
	
	public Tower(int m_nHeight, int m_nNumber) {
		this.m_nHeight = m_nHeight;
		this.m_nNumber = m_nNumber;
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream(Main.class.getResource("input.txt").getPath()));

		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(bReader.readLine());

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

		
		Stack<Tower> stTowers = new Stack<>();
		// 어차피 처음엔 쌓인다.
		stTowers.push(new Tower(Integer.parseInt(st.nextToken()), 1));
		bWriter.write("0 ");

		for (int i = 1; i < N; i++) {
			int nTower = Integer.parseInt(st.nextToken());
			// 스택 맨 윗부분의 수보다 크거나 비어있으면
			while(!stTowers.isEmpty() && stTowers.peek().m_nHeight < nTower) {
				stTowers.pop();
			}
			
			// 비어있다는건? 현재 타워 높이가 가장 높다는 것
			if(stTowers.isEmpty()) {
				bWriter.write("0 ");
			} else {
				// 안비어있다는건 ?
				// 현재 타워보다 높은게 있다는 거
				bWriter.write(stTowers.peek().m_nNumber + " ");
			}
			stTowers.push(new Tower(nTower, i+1));
		}


		bWriter.flush();
		bWriter.close();
	}

}

으헝 주말인데 술도 못먹구,,,

Good Luck! (피드백 감사합니다!)