Notice
Recent Posts
Link
- Today
- Total
hye-log
[백준]2493번 탑(JAVA) 본문
0. 문제 링크
https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
1. 문제 설명
1) 탑들의 개수 N과 탑들의 높이가 주어짐
2) 탑 순서의 반대 방향(왼쪽 방향)으로 레이저 신호를 발사할 때, 레이저 신호를 수신한 탑들의 번호 출력하기
2. 입출력
// input
5
6 9 5 7 4
// output
0 0 2 2 4
3. 코드
import java.io.*;
import java.util.*;
class Tower{
int height;
int idx;
public Tower(int height, int idx) {
this.height = height;
this.idx = idx;
}
}
public class b2493 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine()); // 탑의 수
int[] arr = new int[N]; // 탑의 높이
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] ans = new int[N]; // 수신한 탑의 번호
Stack<Tower> s = new Stack(); // 스택 생성
for(int i = N-1; i >= 0; i--) {
Tower tmp = new Tower(arr[i], i+1); // 타워 신호, 인덱스 번호 저장
if(s.isEmpty()) { // 비어 있으면
s.push(tmp); // 넣기
} else { // 비어 있지 않으면
while(!s.isEmpty()) { // 비어 있지 않을 때까지 반복
int peekIdx = s.peek().idx; // 제일 위에 있는 idx
int peekHeight = s.peek().height; // 제일 위에 있는 height
if(peekHeight < tmp.height) { // 넣을 거보다 작으면
s.pop(); // 꺼내기
ans[peekIdx-1] = i+1; // 수신한 타워 저장
} else {
break;
}
}
s.push(tmp); // 넣기
}
}
for(int i = 0; i < ans.length; i++) {
System.out.print(ans[i] + " ");
}
}
}
실행 결과
4. 회고
1) 인덱스와 탑의 높이를 저장하기 위해 Tower class 생성
2) stack을 이용하여 가장 마지막에 넣은 탑이 신호를 받을 수 있는지 판별
- 가장 마지막에 넣은 탑이 현재 넣을 탑의 높이보다 작으면, 신호를 받으므로 꺼내고, 수신한 탑의 인덱스 저장
- 가장 마지막에 넣은 탑이 현재 넣을 탑의 높이보다 크면, 신호를 받을 수 없음
- 두 작업을 진행한 후에 현재 탑은 반드시 stack에 push
5. Github
https://github.com/iihye/Algorithm/blob/main/Baekjoon/b2493.java
728x90
'CodingTest > Baekjoon' 카테고리의 다른 글
[백준]10163번 색종이(JAVA) (0) | 2023.08.07 |
---|---|
[백준]13300번 방 배정(JAVA) (0) | 2023.08.07 |
[백준]2164번 카드2(JAVA) (0) | 2023.08.07 |
[백준]2023번 신기한 소수(JAVA) (0) | 2023.08.06 |
[백준]12891번 DNA 비밀번호(JAVA) + 슬라이딩 윈도우 GIF (0) | 2023.08.06 |
Comments