[백준] 데이터 체커 #22942

설명

문제 조건에 N이 최대 20만이기 때문에 O(N^2)풀이는 풀지 못한다는 것을 파악했다.
고민해보았지만 문제 풀이 방법이 생각나지 않아 다른 사람의 풀이를 참고했는데 스택 자료구조를 사용해서 풀면 되었다.

x축에 맞닿는 원 좌표기준으로 왼쪽을 괄호의 open 오른쪽을 괄호의 close라고 생각하고 stack에 담아 비교하면 된다.
본인은 입력에서 { x축에 닿는 좌표, open/close, 원의번호 }라고 저장한 후, x축에 닿는 좌표를 기준으로 한 번 정렬해주고 stack에 집어넣고 close의 경우 pop해서 짝이 맞으면 continue, 틀리면 "NO"를 출력해주었다.
마지막에는 stack이 비어있는지 확인하고 결과를 리턴한다.

Node.js 풀이

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));

C++ 풀이

#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;
}