📙 Algorithm Solving/Java
📙[Algo] 24.08.30 알고리즘
혜덕hyeduck
2024. 8. 30. 18:06
알고리즘 문제) BOJ 3015. 오아시스 재결합
문제 요약
- N명이 한 줄로 서서 기다리고 있다
- 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다
- 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성
시간 제한
- 1초
입력
- 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
- 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다
- 모두 2^31보다 작다
- 사람들이 서 있는 순서대로 입력이 주어진다.
출력
- 서로 볼 수 있는 쌍의 수를 출력한다.
접근법
- N이 50만 까지 가능하므로 O(N)안에 연산을 마쳐야 한다.
- 두 건물이 서로 볼 수 있으려면, 두 건물 사이에 min(건물1 높이, 건물2높이)보다 큰 건물이 있으면 안된다.
- 즉, 이전 건물에 현재 건물보다 큰 건물이 있다면 해당 건물 기준으로 앞에 있는 건물들은 전부 볼 수 없다.
- 이 점을 고려해본다면, 빌딩을 N번 순회하면서
- 스택에는 이전 빌딩 정보를 담아둔다.
- 이때, 스택에서 peek한 빌딩의 높이가 현재 빌딩보다 작다면 해당 빌딩들은 모두 pop한다. ⇒ 현재 건물 다음 건물들은 이 건물을 볼 수 없기 때문에 비교할 필요가 없다.
- 여기서 주의할 점은 같을 경우이다.
- 두 건물 사이에 존재하는 건물들이 두 건물의 높이와 같아도 볼 수 있기때문에, 같은 높이를 갖는 건물 개수를 따로 기록해 둬야 한다.
- 따라서, 높이와 같은 건물 개수를 저장하는 객체를 하나 생성했다.
- 만약, stack에서 peek한 건물의 높이가 현재 건물과 같다면, peek한 건물의 같은 건물 개수(sameCnt)를 누적해서 현재 건물에 더해주고, 또한 정답 변수를 카운트 할 때도 sameCnt만큼 더해줘야한다. ⇒ 따라서 따로 같은 건물 개수를 저장할 cnt변수를 추가했다.
- 정리하자면, 스택의 원소는 내림차순 형태가 유지되도록 해준다(LIFO시 오름차순 형태)
- 스택에서 peek한 건물의 높이가
- 현재 건물보다 큰 건물이라면
- 정답 변수 + 1
- 현재 건물보다 작은 건물이라면
- 정답 변수 + 이전 건물의 sameCnt
- 이전 건물 pop
- 현재 건물과 같은 건물이라면
- cnt(현재 건물과 높이가 같은 이전 건물 개수) + 이전 건물의 sameCnt
- 정답 변수 + 이전 건물의 sameCnt
- 이전 건물 pop
- 현재 건물보다 큰 건물이라면
- 마지막으로 stack에는 현재 건물 객체를 push한다.
- 스택에서 peek한 건물의 높이가
코드
import java.io.*;
import java.util.*;
public class Main {
static class Node {
int height;
long sameCnt;
Node(int height, long sameCnt) {
this.height = height;
this.sameCnt = sameCnt;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// 내림차순 형태로 유지(LIFO시 오름차순 형태로 출력)
Stack<Node> stack = new Stack<>();
// 동일한 거 담을 임시 stack
Stack<Integer> tmp = new Stack<>();
// 정답변수
long ans = 0, cnt;
for (int i = 0; i < N; i++) {
cnt = 1;
if (!stack.isEmpty()) {
// 동일한 높이를 만나 거나 낮은 높이를 만난 경우
while (!stack.isEmpty() && (stack.peek().height <= arr[i])) {
// 같은 높이를 만났다면, 같은 높이 만큼 cnt에 더해주기
if (stack.peek().height == arr[i]) cnt += stack.peek().sameCnt;
// 이전에 동일한 크기만큼 정답 변수에 더해주기
ans += stack.peek().sameCnt;
stack.pop();
}
// 더 높은 높이를 만난 경우
if (!stack.isEmpty() && stack.peek().height > arr[i]) {
ans++;
}
}
stack.push(new Node(arr[i], cnt));
}
System.out.println(ans);
}
}
알고리즘 문제) BOJ 1027. 고층 건물
문제 요약
- N개의 빌딩이 존재
- 빌딩 A에서 다른 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩이 지나거나 접하면 안 된다.
- 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 그때 보이는 빌딩의 수를 출력해라
시간 제한
- 2초
입력
- 빌딩의 수 N
- 1 ≤ N ≤ 50
- 각 빌딩의 높이가 N개 주어진다.
- 1 ≤ 높이 ≤ 10억
출력
- 정답 출력
접근법
- 두 빌딩이 서로 보이기 위해서, 두 빌딩 사이에 지붕을 잇는 선분에 겹치거나 지나면 안되므로, 두 빌딩을 이어주는 직선 그래프를 구했다.
- 기울기와 절편을 구한 뒤, 각 빌딩의 높이 좌표(i, arr[i])의 x좌표를 해당 그래프에 대입했을 때 결과값이 arr[i]보다 큰 경우만 있는 경우 서로 빌딩이 보인다 판단해서 카운트 + 1 했다.
- 이때 N이 50까지이므로 O(N^3)까지 가능하므로 완전탐색으로 진행했다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int ansCnt = 0, cnt, x1, x2, y1, y2, x3, y3;
double a, b;
boolean flag;
for (int i = 1; i <= N; i++) {
x1 = i;
y1 = arr[i];
cnt = 0;
for (int j = 1; j <= N; j++) {
if (i == j) continue;
flag = true;
x2 = j;
y2 = arr[j];
// 기울기
a = (double) (y1 - y2) / (x1 - x2);
// 절편
b = -a * x1 + y1;
for (int k = Math.min(i, j) + 1; k < Math.max(i, j); k++) {
x3 = k;
y3 = arr[k];
if (a*x3 + b <= y3) flag = false;
}
if (flag) cnt++;
}
ansCnt = Math.max(ansCnt, cnt);
}
System.out.println(ansCnt);
}
}