[Gold III] 탑 보기 - 22866
성능 요약
메모리: 41472 KB, 시간: 420 ms
분류
자료 구조, 스택
제출 일자
2024년 6월 14일 21:56:59
문제 설명
일직선으로 다양한 높이의 건물이 총 N
개가 존재한다. 각 건물 옥상에서 양 옆에 존재하는 건물의 옆을 몇 개 볼 수 있는지 궁금해졌다.i번째 건물 기준으로 i−1 i−2, ..., 1번째 건물은 왼쪽에, i+1 i+2, ..., N번째 건물은 오른쪽에 있다. 각 건물 사이의 거리는 다 동일하다.
현재 있는 건물의 높이가 L이라고 가정하면 높이가 L보다 큰 곳의 건물만 볼 수 있다.
바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다.
번호 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
높이 | 3 | 7 | 1 | 6 | 3 | 5 | 1 | 7 |
보이는 건물 번호 | 2 | x | 2, 4, 8 | 2, 8 | 2,4,6,8 | 2,4,8 | 2,4,6,8 | x |
각 건물에서 볼 수 있는 건물들이 어떤것이 있는지 구해보자.
입력
첫번째 줄에 건물의 개수 N이 주어진다.
두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.
출력
i(1≤i≤N) i번째 건물에서 볼 수 있는 건물의 개수를 출력한다.
만약 볼 수 있는 건물의 개수가 1개 이상이라면 i째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.
접근 방법
1. N이 최대 100,000임으로 시간복잡도는 선형인 O(N)으로 해결해야한다.
2. 스택이 적합하다고 판단
3. 스택 자료구조를 클래스로 만들어주고 각 인덱스와 높이를 저장하는 빌딩 클래스를 만들어놓는다.
4. 왼쪽과 오른쪽 스택을 다르게 생각하여 계산해주면 간단하게 구현 가능하다.
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 문제 : BOJ_22866_G3_탑보기
* 메모리: 43856KB
* 시간: 420ms
* 접근 방법
* 1. N이 최대 100,000임으로 시간복잡도는 선형인 O(N)으로 해결해야한다.
* 2. 스택이 적합하다고 판단
* 3. 스택 자료구조를 클래스로 만들어주고 각 인덱스와 높이를 저장하는 빌딩 클래스를 만들어놓는다.
* 4. 왼쪽과 오른쪽 스택을 다르게 생각하여 계산해주면 간단하게 구현 가능하다.
*/
public class Main {
// 스택
static class Stack {
Building[] element;
int top;
int size;
public Stack(int size) {
this.size = size;
element = new Building[size];
this.top = -1;
}
public void push(Building b) {
if (top == size - 1) {
return;
}
element[++top] = b;
}
public Building peek() {
return element[top];
}
public Building pop() {
return element[top--];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
}
// 각 인덱스와 높이를 가지는 빌딩 클래스
static class Building {
int idx;
int height;
public Building(int idx, int height) {
this.idx = idx;
this.height = height;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// Input
int[] count = new int[N]; // 개수
int[] mem = new int[N]; // 가까운 빌딩의 인덱스
Building[] buildings = new Building[N]; // 각 높이를 빌딩에 저장하여 메모리를 절약
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
buildings[i] = new Building(i, Integer.parseInt(st.nextToken()));
mem[i] = -1;
}// Input End
Stack left = new Stack(N);
Stack right = new Stack(N);
for (int i = 0; i < N; i++) {
// 현재 왼쪽에 있는 건물 중 i번째 건물보다 낮다면 제거
removeHeight(left, buildings, count, i);
// 비어있지않다면 가장 가까운 건물 설정
if (!left.isEmpty()) {
setIdx(mem, i, left.peek().idx);
}
left.push(buildings[i]);
// 오른쪽에서 i번째 있는 건물보다 작은 오른쪽 건물들 제거
removeHeight(right, buildings, count, N - i - 1);
if (!right.isEmpty()) {
setIdx(mem, N - i - 1, right.peek().idx);
}
right.push(buildings[N - i - 1]);
}
// 연산 종료 후 남은 건물들의 높이 계산
while (!left.isEmpty()) {
Building b = left.pop();
count[b.idx] += left.size();
}
while (!right.isEmpty()) {
Building b = right.pop();
count[b.idx] += right.size();
}
// OutPut
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
sb.append(count[i]);
if (count[i] != 0) {
sb.append(' ').append(mem[i] + 1);
}
sb.append('\n');
}
System.out.println(sb);
// OutPutEnd
}
// idx보다 작은 건물을 스택에서 제거
private static void removeHeight(Stack stack, Building[] buildings, int[] count, int idx) {
while (!stack.isEmpty() && stack.peek().height <= buildings[idx].height) {
Building b = stack.pop();
count[b.idx] = count[b.idx] + stack.size();
}
}
private static void setIdx(int[] mem, int i, int idx) {
if (mem[i] == -1) mem[i] = idx;
int originDist = Math.abs(i - mem[i]);
int newDist = Math.abs(i - idx);
if (originDist > newDist || (originDist == newDist && idx < mem[i])) {
mem[i] = idx;
}
}
}
'알고리즘 - Baekjoon > Gold' 카테고리의 다른 글
[백준] 2229번 : 조 짜기 Gold5(골드5) - JAVA[자바] (1) | 2024.06.16 |
---|---|
[백준] 20208번 : 진우의 민트초코우유 Gold5(골드5) - JAVA[자바] (0) | 2024.06.15 |
[백준] 1082번 : 방 번호 Gold3(골드3) - JAVA[자바] (1) | 2024.06.13 |
[백준] 1113번 : 수영장 만들기 Gold1(골드1) - JAVA[자바] (0) | 2024.06.11 |
[백준] 5549번 : 행성 탐사 Gold5(골드5) - JAVA[자바] (2) | 2024.06.08 |