문제
알고리즘 분류
- 스택
- 스위핑 알고리즘
접근과정
처음 문제를 읽었을 때는 어떻게 풀어야할지 감도 잡히지 않아서 30분 동안 문제만 쳐다봤다. 그러다 모든 원의 중심이 x축 위에 있고, 모든 원이 서로 겹치지 않는다는 것에서 착안하여 [원의 왼쪽 좌표, 원의 오른쪽 좌표]로 저장하게 되었다. 원을 "x축 위에서의 영역"으로 바꿔 생각하면 바로 라인 스위핑 알고리즘 문제로 치환가능하다. 영역 간 끝점이 서로 접해있는지를 체크하면 된다. 여기서부터는 구현의 문제이다.
문제 자체의 솔루션은 간단하다. 원 내부를 원 여러개가 분단하고 있으면 영역이 +2개가 되는거고, 그렇지 않으면 원의 개수만큼 영역이 +1개가 된다.
이번 문제는 구현이 너무 귀찮아서 이중 for문을 한번 구현해보고 실패해서 그냥 바로 솔루션을 보았다. 구현 문제는 너무 머리가 아프다...
나의 풀이: 이중 for문(실패)
첫 풀이는 단순 이중 for문이다. 시간제한 1초에 이중 for문이라 당연히 시간초과가 뜬다..
전체 코드
import sys
input = sys.stdin.readline
n = int(input())
circles = [list(map(int, input().split())) for _ in range(n)]
area = [[0, 0]] * (2*n)
for i in range(n):
area[i] = [circles[i][0]-circles[i][1], circles[i][0]+circles[i][1]]
k = 0
for i in range(n):
for j in range(i+1, n):
if area[i][1] == area[j][0]:
area[n+k] = [area[i][0], area[j][1]]
k += 1
elif area[i][0] == area[j][1]:
area[n+k] = [area[j][0], area[i][1]]
k += 1
answer = n+1
for item in area[n:]:
if item in area[:n]:
answer += 1
print(answer)솔루션 1: 스택 + 스위핑 알고리즘
메모리: 12550 KB
시간: 1012 ms
일반적인 풀이 방법이다. 찾아보니 거의 대부분의 사람들이 이 방식으로 풀이하였다.
- x축에 접하는 원의 좌표와 모양에 맞는 괄호를 함께 저장한다.
for i in range(n):
x, r = map(int, input().split())
circles.append((x-r, '('))
circles.append((x+r, ')'))- 좌표 리스트를 오름차순이 되도록 정렬하고, 같은 좌표라면 ')' 괄호가 있는 좌표값을 앞으로 오게 한다. 같은 좌표라면 괄호가 닫히는 걸 먼저 확인해야 작은 원이 먼저 만들어진다.
circles = sorted(circles, key= lambda x:(x[0], -ord(x[1])))- 좌표 리스트를 순회하면서 스택에 쌓는다. 스택에는 좌표값(position), 괄호모양(bracker), 연결 상태(status) 값을 저장한다.
좌표 리스트는 좌표값을 기준으로 정렬되어 있으므로, 가장 왼쪽부터 시작한다.
열린괄호 '('가 들어오면, 이전에 들어온 좌표값과 좌표가 같으면 두 원이 '접해있다'는 뜻이 된다. 이때 이전 괄호의 status를 1로 바꾼다. status == 1은 왼쪽 좌표가 맞닿아있다는 의미이다.
닫힌괄호 ')'가 들어오면, 스택의 마지막 괄호의 status를 확인하고 0이면 영역이 분단되지 않았으므로 answer += 1, 1이면 영역이 분단되므로 answer += 2 한다. 그리고 스택을 pop() 한다.
이때 다음 들어오는 괄호의 좌표가 접하였는지 안했는지 확인하여 접하였다면, 넘어가고 접하지 않았다면 밖의 원의 괄호 status 값을 0으로 변경한다.
전체 코드
import sys
input = sys.stdin.readline
n = int(input())
circles = []
for i in range(n):
x, r = map(int, input().split())
circles.append((x-r, '('))
circles.append((x+r, ')'))
circles = sorted(circles, key=lambda x: (x[0], -ord(x[1])))
stack = []
answer = 1
for i in range(2*n):
position, bracket = circles[i]
if len(stack) == 0:
stack.append({'pos': position, 'bracket': bracket, 'status': 0})
continue
if bracket == ')':
if stack[-1]['status'] == 0:
answer += 1
elif stack[-1]['status'] == 1:
answer += 2
stack.pop()
if i != n*2-1:
if circles[i+1][0] != position:
stack[-1]['status'] = 0
else:
if stack[-1]['pos'] == position:
stack[-1]['status'] = 1
stack.append({'pos': position, 'bracket': bracket, 'status': 0})
else:
stack.append({'pos': position, 'bracket': bracket, 'status': 0})
print(answer)솔루션 2: 재귀
메모리: 92776 KB
시간: 648 ms
스택을 이용한 풀이보다 훨씬 빠르고 효율적이다. 원의 양끝점을 이용하는 것은 동일하다.
- 원의 양끝점을 저장하고, 왼쪽 좌표를 오름차순으로, 왼쪽 좌표가 같다면 오른쪽 좌표를 기준으로 내림차순 정렬한다.
for i in range(n):
x,r = map(int,input().split())
circles.append((x-r,x+r))
circles.sort(key=lambda x:(x[0],-x[1]))- 좌표 리스트에 대해 순회한다. 이때 현재 원과 다음 원의 왼쪽 좌표가 같다면, 오른쪽 좌표가 같은(오른쪽에서 접한) 원을 재귀로 찾는다.
정말 심플한 풀이방법이다. 스택보다 훨씬 간단하고 빠르다. 좌표 리스트에서 오른쪽 좌표값을 가지는 원을 찾기 위해서는 bisect 묘듈의 bisect_left() 함수를 사용하였다.
전체 코드
import sys
from bisect import bisect_left
input = sys.stdin.readline
sys.setrecursionlimit(400000)
def next_circle(cur_c,next_c):
global cnt
if circles[cur_c][1] == circles[next_c][1]:
cnt += 1
return
tmp = bisect_left(circles,(circles[next_c][1],))
if tmp == len(circles):
return
if circles[tmp][0]==circles[next_c][1]:
next_circle(cur_c,tmp)
n = int(input())
circles = []
for i in range(n):
x,r = map(int,input().split())
circles.append((x-r,x+r))
circles.sort(key=lambda x:(x[0],-x[1]))
cnt = 0
for i in range(n-1):
if circles[i][0] == circles[i+1][0]:
next_circle(i,i+1)
print(n+cnt+1)참고
