1. 문제
일직선으로 다양한 높이의 건물이 총 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)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.
만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.
제한
백준 2493 탑
https://www.acmicpc.net/problem/2493#include #include #include using namespace std;vector> arr;vector ans;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; arr.resize(n); ans.resize(n, 0); for (int i = 0; i > temp; a
runawayfromlazy.tistory.com
해당 문제와 비슷한 문제이다. 다만 좌우를 모두 고려해야 하므로 좌측으로 볼 수 있는 탑의 개수 및 탑, 우측으로 볼 수 있는 탑의 개수 및 탑을 각각 계산해주어야 한다.
//현재 타워에서 왼쪽으로 보이는 타워 개수 계산
Stack<Tower> st = new Stack<>();
leftTower = new int[n][2];
for (int i = 0; i < n; i++) {
leftTower[i][1] = -1;
}
st.push(new Tower(0, l[0]));
leftTower[0][0] = 0;
leftTower[0][1] = -1;
for (int i = 1; i < n; i++) {
Tower cur = new Tower(i, l[i]);
while (!st.isEmpty() && cur.h >= st.peek().h) {
st.pop();
}
leftTower[i][0] = st.size();
if (!st.isEmpty()) {
leftTower[i][1] = st.peek().cur;
}
st.push(cur);
}왼쪽으로 보이는 탑의 개수를 계산하는 코드이다. leftTower[i][0, 1]에는 각각 i번째 탑에서 왼쪽으로 볼 수 있는 탑의 개수와 현재 위치에서 가장 가까운 탑을 저장해 줄 것이다.
타워의 번호와 높이를 저장하는 스택을 하나 선언하고, 맨 왼쪽 탑은 왼쪽을 볼 수 없으므로 기본값으로 초기화해준다. 그 다음의 각 탑에 대해 스택의 top에 있는 탑의 높이가 현재 탑의 높이보다 높아질 때 까지 pop한다. 이게 끝나면 스택의 크기, 즉 현재 위치에서 볼 수 있는 탑의 개수를 저장하고, 스택이 있다면 top에 있는 탑이 현재 탑과 가장 가까우므로 그 번호를 저장해준다.
//현재 타워에서 오른쪽으로 보이는 타워 개수 계산
st = new Stack<>();
rightTower = new int[n][2];
for (int i = 0; i < n; i++) {
rightTower[i][1] = -1;
}
st.push(new Tower(n - 1, l[n - 1]));
rightTower[n - 1][0] = 0;
rightTower[n - 1][1] = -1;
for (int i = n - 2; i >= 0; i--) {
Tower cur = new Tower(i, l[i]);
while (!st.isEmpty() && cur.h >= st.peek().h) {
st.pop();
}
rightTower[i][0] = st.size();
if (!st.isEmpty()) {
rightTower[i][1] = st.peek().cur;
}
st.push(cur);
}
오른쪽의 경우도 같은 방식으로 오른쪽부터 계산해준다.
//보이는 건물 개수 계산 //출력할 건물 번호 계산
for (int i = 0; i < n; i++) {
if (leftTower[i][0] + rightTower[i][0] == 0) {
continue;
}
ans[i][0] = leftTower[i][0] + rightTower[i][0];
if (leftTower[i][1] == -1) {
ans[i][1] = rightTower[i][1]+1;
} else if (rightTower[i][1] == -1) {
ans[i][1] = leftTower[i][1]+1;
} else {
if (i - leftTower[i][1] > rightTower[i][1] - i) {
ans[i][1] = rightTower[i][1] + 1;
} else {
ans[i][1] = leftTower[i][1] + 1;
}
}
}이제 정답을 계산해야 한다. 현재 탑에서 보이는 총 탑의 개수는 (왼쪽으로 보이는 탑의 개수)+(오른쪽으로 보이는 탑의 개수) 이므로 둘을 계산해준다. 합쳐서 0일 경우 그 다음 값인 가장 가까운 탑을 계산할 수 없으므로 다음 탑으로 넘어간다.
이제 현재 위치에서 볼 수 있는 탑의 개수는 적어도 하나 존재하는 상태이다. 탑의 왼쪽과 오른쪽에 대해 왼쪽(오른쪽)으로 볼 수 있는 탑이 없다면 반대쪽에 있는 가장 가까운 탑을 두 번째 값으로 출력할 수 있다. 여태 0-indexed로 계산했으므로 +1을 해준다.
양쪽에 모두 볼 수 있는 탑이 있다면 왼쪽이 더 멀 경우 오른쪽의 탑을, 반대의 경우 더 작은 탑 번호를 적어야 하므로 왼쪽의 탑을 적어준다.
//출력
for (int i = 0; i < n; i++) {
if (ans[i][0] == 0) {
System.out.println(0);
} else {
System.out.println(ans[i][0] + " " + ans[i][1]);
}
}위에서 계산한 결과를 출력해준다. 다만 현재 위치에서 볼 수 있는 탑이 없을 경우 두 번째 값을 출력하지 않는다.
3. 코드 전문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static int n;
static int[] l;
//보이는 타워 개수, 가장 가까운 타워 번호
static int[][] leftTower;
static int[][] rightTower;
static int[][] ans;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer;
n = Integer.parseInt(reader.readLine());
l = new int[n];
ans = new int[n][2];
tokenizer = new StringTokenizer(reader.readLine());
for (int i = 0; i < n; i++) {
l[i] = Integer.parseInt(tokenizer.nextToken());
}
//현재 타워에서 왼쪽으로 보이는 타워 개수 계산
Stack<Tower> st = new Stack<>();
leftTower = new int[n][2];
for (int i = 0; i < n; i++) {
leftTower[i][1] = -1;
}
st.push(new Tower(0, l[0]));
leftTower[0][0] = 0;
leftTower[0][1] = -1;
for (int i = 1; i < n; i++) {
Tower cur = new Tower(i, l[i]);
while (!st.isEmpty() && cur.h >= st.peek().h) {
st.pop();
}
leftTower[i][0] = st.size();
if (!st.isEmpty()) {
leftTower[i][1] = st.peek().cur;
}
st.push(cur);
}
//현재 타워에서 오른쪽으로 보이는 타워 개수 계산
st = new Stack<>();
rightTower = new int[n][2];
for (int i = 0; i < n; i++) {
rightTower[i][1] = -1;
}
st.push(new Tower(n - 1, l[n - 1]));
rightTower[n - 1][0] = 0;
rightTower[n - 1][1] = -1;
for (int i = n - 2; i >= 0; i--) {
Tower cur = new Tower(i, l[i]);
while (!st.isEmpty() && cur.h >= st.peek().h) {
st.pop();
}
rightTower[i][0] = st.size();
if (!st.isEmpty()) {
rightTower[i][1] = st.peek().cur;
}
st.push(cur);
}
//보이는 건물 개수 계산 //출력할 건물 번호 계산
for (int i = 0; i < n; i++) {
if (leftTower[i][0] + rightTower[i][0] == 0) {
continue;
}
ans[i][0] = leftTower[i][0] + rightTower[i][0];
if (leftTower[i][1] == -1) {
ans[i][1] = rightTower[i][1]+1;
} else if (rightTower[i][1] == -1) {
ans[i][1] = leftTower[i][1]+1;
} else {
if (i - leftTower[i][1] > rightTower[i][1] - i) {
ans[i][1] = rightTower[i][1] + 1;
} else {
ans[i][1] = leftTower[i][1] + 1;
}
}
}
//출력
for (int i = 0; i < n; i++) {
if (ans[i][0] == 0) {
System.out.println(0);
} else {
System.out.println(ans[i][0] + " " + ans[i][1]);
}
}
}
}
class Tower {
int cur;
int h;
public Tower(int cur, int h) {
this.cur = cur;
this.h = h;
}
}'Coding Test' 카테고리의 다른 글
| 백준 1943 동전 분배 (Java) (0) | 2025.01.07 |
|---|---|
| 백준 2138 전구와 스위치 (Java) (0) | 2025.01.04 |
| 백준 14658 하늘에서 별똥별이 빗발친다 (Java) (1) | 2024.12.23 |
| 백준 1238 파티 (Java) (1) | 2024.12.22 |
| 백준 4179 불! (Java) (1) | 2024.12.20 |
