[백준] 22942번 - 데이터 체커 (C++) 문제 및 풀이

문제) 백준 - 자료 구조 - 데이터 체커

https://www.acmicpc.net/problem/22942

22942번: 데이터 체커

 

N의 최댓값이 20만이기 때문에 완전 탐색 시 TLE로 틀려서, 한참 고민했습니다. 쉬운 방법이 도저히 안 떠올라 SegTree로 구현하려다 알고리즘 분류를 보니, 자료구조임을 보고 올바른 괄호 문제의 아이디어가 떠올라 그것을 활용해 해결했습니다. 원의 x좌표(val), 원의 오른쪽/왼쪽 판별(isOpen), 인덱스(idx)를 변수로 가지는 구조체를 활용하여 x좌표를 기준으로 정렬 후 스택을 이용해 원의 교점을 확인합니다. 

 

C++ 소스코드)