문제
들어가며
5시간 넘게 쳐다봤던 것 같다..
그럼에도 못 풀었다.
아직 플레는 멀었다..
화이팅
코드
package m03.d24;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
public class 원의영역_10000_3 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayList<Position> positions = new ArrayList<>();
for (int i = 0; i < n; i++) {
int[] circle = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
int center = circle[0];
int r = circle[1];
positions.add(new Position(center - r, '('));
positions.add(new Position(center + r, ')'));
}
Collections.sort(positions);
int result = 1;
Stack<Position> stack = new Stack<>();
for (int i = 0; i < positions.size(); i++) {
Position current = positions.get(i);
if (current.type == '(') { // 시작점
if (!stack.isEmpty() && stack.peek().x == current.x) {
stack.peek().isConnected = true; // 접촉 여부 설정
}
stack.push(current);
continue;
}
Position prev = stack.peek();
if (prev.isConnected){
result += 2;
} else {
result ++;
}
stack.pop();
if (!stack.isEmpty() && i + 1 < positions.size()) {
Position next = positions.get(i + 1);
if (next.x != current.x) {
stack.peek().isConnected = false;
}
}
}
System.out.println(result);
}
private static class Position implements Comparable<Position> {
int x;
char type;
boolean isConnected = false;
public Position(int x, char type) {
this.x = x;
this.type = type;
}
@Override
public int compareTo(Position o) {
int compare = Integer.compare(this.x, o.x);
if (compare == 0) {
return -Character.compare(this.type, o.type);
}
return compare;
}
}
}
풀이
이 문제는 스택으로 풀 수 있다.
백준의 VPS 문제와 접근 방법이 유사하다. 하지만 좀 다르다.
(참고 : 9012번: 괄호)
먼저, 그림을 보자.
입력
4
7 5
-9 11
11 9
0 20
원을 보면 좀 접근하기가 어려울 수 있다.
이를 추상화를 할 수 있는데, 결국 구간 문제이기 때문이다.
원은 겹치지 않는다. 그리고 우린 각각의 원의 중심 좌표와 반지름을 알고 있다.
이 말은 곧 원의 시작점과 끝점을 알 수 있다.
(-20, 20)
(-20, 2)
(2, 12)
(2, 20)위와 같이 원을 구간으로 볼 수가 있게 되는 것이다.
그러면 이 정보들로 문제에서 요구하는 원의 영역은 어떻게 구할 수 있을까??
원의 영역을 어떻게 증가하는지를 파악하면 알게 된다.
1. 원 내부에 원이 생겼을 때
2. 원 시작점과 끝점으로 원이 모두 이어져 있을 때
1번의 경우엔 단지 원 내부라는 영역이 하나 증가할 뿐이므로 +1를 해주면 그만이다.
2번이 조금 골 때리는데, 대표적인 예시가 그림 4라고 말할 수 있다.
보면 원의 영역이 위 아래로 영역이 2개가 생기는 걸 볼 수 있다.
그러므로 +2를 해줘야 한다.
이 문제는 이 부분이 가장 맹점이다.
어떻게 구간들의 정보들로 이를 구할 수 있을까??
(-20, 20)
(-20, 2)
(2, 12)
(2, 20)여기엔 좌표가 겹치는 부분에 힌트가 있다.
결국은 원이 쭉 이어진다는 건, 어떤 원의 시작점과 끝점이 같은 두 좌표를 가지고 있다는 뜻이다.
위 입력에선 -20 과 20이 두 번 반복이 되는 걸 알 수 있다.
이것만 찾으면 된다. 그러면 충분히 원의 영역을 구할 수 있다!
이걸 찾기 위해 이제부터 데이터를 가공할 것이다.
구간은 시작점과 끝점이 존재한다. 이를 각각 '(', ')'로 표시할 것이다.
그걸 이제 좌표랑 붙인다. 또한 연결된 부분임을 파악하기 위해서 isConnected라는 boolean도 사용할 것이다.
private static class Position implements Comparable<Position> {
int x;
char type;
boolean isConnected = false;
public Position(int x, char type) {
this.x = x;
this.type = type;
}
@Override
public int compareTo(Position o) {
int compare = Integer.compare(this.x, o.x);
if (compare == 0) {
return -Character.compare(this.type, o.type);
}
return compare;
}
}
그 클래스가 바로 Position이다. x는 좌표, type 은 '(' , ')' 이고, isConnected는 겹치는 점이 있는지 파악하기 위함이다.
위 입력에선 Position의 리스트가 다음과 같이 만들어질 수 있다.
-20, (
-20, (
2, )
2, (
2, (
12, )
20, )위에선 이미 정렬이 된 모습을 표시하지만, 실제로는 원의 데이터는 임의로 들어오기 위해 정렬하는 작업을 거쳐야 한다.
그렇기 때문에, Position 클래스에 compareTo를 만들어 비교를 한다. 이때, x가 오름차순으로, type 의 경우 ) 가 먼저 오도록 해야한다. 그렇게 해야 정상적으로 원을 표시할 수 있다.
for (int i = 0; i < n; i++) {
int[] circle = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
int center = circle[0];
int r = circle[1];
positions.add(new Position(center - r, '('));
positions.add(new Position(center + r, ')'));
}
Collections.sort(positions);위 부분은 compareTo로 정의된 리스트를 정렬한다.
이렇게 되면 데이터 가공은 끝났고 이제 원의 영역을 세어야 한다.
여기선 백준 VPS 문제처럼 스택을 이용하여 () 짝을 맞춰준다.
int result = 1;
Stack<Position> stack = new Stack<>();
for (int i = 0; i < positions.size(); i++) {
Position current = positions.get(i);
if (current.type == '(') { // 시작점
if (!stack.isEmpty() && stack.peek().x == current.x) {
stack.peek().isConnected = true; // 접촉 여부 설정
}
stack.push(current);
continue;
}
Position prev = stack.peek();
if (prev.isConnected){
result += 2;
} else {
result ++;
}
stack.pop();
if (!stack.isEmpty() && i + 1 < positions.size()) {
Position next = positions.get(i + 1);
if (next.x != current.x) {
stack.peek().isConnected = false;
}
}
}
( 를 입력했을 경우부터 보자.
(를 입력했다는 것은 이제 구간을 연다는 것을 의미한다.
그 이전에 (가 있는지를 파악한다. 만약 있다면, 이전의 (에 isConnected = true로 표시한다.
그리고 스택에 넣어준다.
)를 입력했을 땐 조금 이야기가 다르다,.
)를 입력했다는 것은 이미 스택의 peek엔 (가 존재한다는 것을 의미한다.
위에서 설명했다싶이 (( )) 이 짝이 맞춰지면 자연스럽게 내부 원이 쭉 이어진 원이라고 말할 수 있다.
그러므로 peek의 ( 가 isConnected인지 확인한다.
isConnected이면, 내부 원이 이어져서 원의 영역이 2개로 만들어지는 상태이므로 +2를 해준다.
아니라면 +1를 해준다.
그리고 peek을 pop 한다.
여기서 끝나지 않았는데 현재 내가 쥐고 있던 ) 가 다음에 가져올 것과 포지션이 같은지를 알아야 한다.
) 뒤에 ( 가 오던 ) 가 오던 원이 계속 이어지고 있는 상황일 수도 있기 때문이다.
만약 아니라면 false를 설정하여 갱신해준다.
이렇게 모든 구간 시작점과 끝점을 돌게 되면 결과가 도출된다.
result가 1부터 시작하는 이유는 원을 그리기 전에도 무조건 영역은 하나로 시작하기 때문이다.
도화지에 원을 그린다고 생각했을 때, 도화지도 영역이기 때문이다.
쉽게 말해 제일 바깥의 원 외부 영역이다.
'Algorithm > 백준' 카테고리의 다른 글
| [백준] 3190- 뱀 문제 풀이(자바,Java) (0) | 2025.03.26 |
|---|---|
| [백준] 1655- 가운데를 말해요 문제 풀이(자바,Java) (0) | 2025.03.25 |
| [백준] 2439 - 탑 문제 풀이(파이썬,Python) (0) | 2025.03.24 |
| [백준] 6549 - 히스토그램에서 가장 큰 직사각형 문제 풀이(파이썬,Python) (0) | 2025.03.22 |
| [백준]11053- 가장 긴 증가하는 부분 수열 문제 풀이(파이썬,Python) (2) | 2025.03.21 |