문제 조건에 N이 최대 20만이기 때문에 O(N^2)
풀이는 풀지 못한다는 것을 파악했다.
고민해보았지만 문제 풀이 방법이 생각나지 않아 다른 사람의 풀이를 참고했는데 스택 자료구조를 사용해서 풀면 되었다.
x축에 맞닿는 원 좌표기준으로 왼쪽을 괄호의 open 오른쪽을 괄호의 close라고 생각하고 stack에 담아 비교하면 된다.
본인은 입력에서 { x축에 닿는 좌표, open/close, 원의번호 }
라고 저장한 후, x축에 닿는 좌표를 기준으로 한 번 정렬해주고 stack에 집어넣고 close의 경우 pop해서 짝이 맞으면 continue, 틀리면 "NO"를 출력해주었다.
마지막에는 stack이 비어있는지 확인하고 결과를 리턴한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = Number(input[0]);
const points = input.slice(1).map((v) => v.split(' ').map(Number));
const solution = (N, points) => {
const arr = [];
points.forEach(([x, r], i) => {
arr.push([x - r, 'open', i]);
arr.push([x + r, 'close', i]);
});
arr.sort((a, b) => a[0] - b[0]);
const stack = [];
for (let i = 0; i < arr.length; i++) {
const [, state, id] = arr[i];
if (state === 'open') {
stack.push(id);
} else {
const top = stack[stack.length - 1];
if (top === id) stack.pop();
else return 'NO';
}
}
if (stack.length !== 0) return 'NO';
return 'YES';
};
console.log(solution(N, points));
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x;
string state;
int id;
};
bool compare(Point& a, Point& b) {
return a.x < b.x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<Point> V;
int N; cin >> N;
for (int i=0; i<N; i++) {
int x, r;
cin >> x >> r;
V.push_back({ x-r, "open", i });
V.push_back({ x+r, "close", i });
}
sort(V.begin(), V.end(), compare);
stack<int> S;
for(auto point : V) {
if (point.state == "open") S.push(point.id);
else {
if (S.top() != point.id) {
cout << "NO" << '\n';
return 0;
} else {
S.pop();
}
}
}
if (!S.empty()) cout << "NO" << '\n';
else cout << "YES" << '\n';
return 0;
}