💡 문제
![](https://velog.velcdn.com/images/longbright_choi/post/e1bd98a2-46ef-40b9-9090-c50902036569/image.png)
![](https://velog.velcdn.com/images/longbright_choi/post/4ef911e1-3eae-49b9-859b-f903cd25cce3/image.png)
💬 입출력 예시
![](https://velog.velcdn.com/images/longbright_choi/post/5af5925f-3c80-4a05-ba72-1bc39515fefd/image.png)
📌 풀이(소스코드)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List<Point> points = new ArrayList<>();
Stack<Point> stack = new Stack<>();
while (N-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
points.add(new Point(x - r, x, true));
points.add(new Point(x + r, x, false));
}
points.sort(Comparator.comparingInt(o -> o.x));
for (Point point : points) {
if (point.isLeft) {
stack.push(point);
continue;
}
if (stack.peek().c == point.c) {
stack.pop();
} else {
System.out.println("NO");
return;
}
}
System.out.println("YES");
}
static class Point {
int x;
int c;
boolean isLeft;
public Point(int x, int c, boolean isLeft) {
this.x = x;
this.c = c;
this.isLeft = isLeft;
}
}
}
📄 해설
접근
- 접근을 제대로 하지 못했다. 문제에서 힌트로 제공된 수식을 사용하는 풀이를 적용했을 때, 98% 에서 틀렸는데, 다른 사람의 풀이를 찾아봤더니 전혀 다른 풀이여서 아직 그 이유를 밝히지 못했다..
- 우선 위 풀이에서의 접근은, 각 원마다 왼쪽 끝점과 오른쪽 끝점을 구분해서 x 좌표, 중심 좌표, 왼쪽 여부에 대한 정보를 담는
Point
클래스 객체를 새로 생성하고, 리스트를 만든다.
- 해당 리스트를 x 좌표를 기준으로 정렬하고, 리스트를 순회하면서 왼쪽 끝점인지 오른쪽 끝점인지에 따라 처리를 하고, 겹치는 원이 있는지 없는지를 확인한다.
과정
Point
객체를 담을 리스트와 스택을 선언하고, N
개의 원의 정보를 입력 받는다.
- 입력 받은 정보에 따라 왼쪽 끝점과 오른쪽 끝점에 대한 객체들을 새롭게 생성하여 리스트에 추가한다.
- 입력이 끝나면 점의 x 좌표를 기준으로 해당 리스트를 정렬하고, 리스트를 순회화면서 아래 동작을 반복한다.
- 왼쪽 끝점일 경우, 스택에 추가한다.
- 오른쪽 끝점일 경우 스택의 탑과 중심 좌표가 같다면, 각 점은 같은 원을 구성하므로, 스택에서 뺀다.
- 스택의 탑과 중심 좌표가 같지 않다면, 둘은 다른 원이므로, 겹치는 원이 존재한다는 뜻이므로 NO 를 출력한다.
- 리스트 순회가 정상적으로 종료되었다면, 겹치는 원은 없었던 것이므로 YES 를 출력한다.