방의 갯수
계속 시간초과가 뜨길래 list말고 dictionary를 쓰니 허무하게 바로 통과되었습니다. 정적인 자료구조는 list를 쓰고 동적인 자료구조는 dictionary를 쓰는것이 훨씬 이득인것 같습니다.
코드
from collections import defaultdict
def add(x, y) :
return [(x[0]+y[0]/2, x[1]+y[1]/2), (x[0]+y[0], x[1]+y[1])]
def check(point, next_, arrow) :
return next_ in points and arrow not in points[point] and (arrow+4)%8 not in points[next_]
def solution(arrows):
global points
answer = 0
move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
points = defaultdict(set)
point = (0, 0)
for arrow in arrows :
for next_ in add(point, move[arrow]) :
answer += 1 if check(point, next_, arrow) else 0
points[point].add(arrow)
point = next_
return answer
벡터형태
point: 현재점 - 좌표(h, w)
arrow: 벡터 - 방향d
next_: 다음점 - 좌표(h+dh, w+dw)
현재 point 에서 앞으로 나아갈 방향 arrow에 다른 point 또는 arrow 가 있으면 벽이 생깁니다.
시작점 (0, 0) 에서 arrow 방향으로 point 이동하면서 바로 이 두가지 경우가 나오나 나오지 않는지만 체크해주면 됩니다.
point : arrow 사전 만들기
우선 첫 point 부터 arrow 순서를 따라 만든 dictionary를 만들어 봅시다.
from collections import defaultdict
def add(x, y) :
return (x[0]+y[0], x[1]+y[1])
def solution(arrows):
global points
answer = 0
move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] # arrow의 (dh, dw) 배열
points = defaultdict(set)
point = (0, 0)
for arrow in arrows :
points[point].add(arrow)
point = add(point, move[arrow])
return answer
만약 arrows = [2, 7, 2, 5, 0] 라면
{(0, 0): {0, 2},
(0, 1): {7},
(-1, 0): {2},
(-1, 1): {5}}
이런 dictionary가 생기고
이런 방들이 생깁니다.
point를 dictionary에 추가하기전에 point의 arrow가 기존 points와 충돌이 있나없나를 확인해 주면 됩니다.
from collections import defaultdict
def add(x, y) :
return (x[0]+y[0], x[1]+y[1])
def solution(arrows):
global points
answer = 0
move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] # arrow의 (dh, dw) 배열
points = defaultdict(set)
point = (0, 0)
for arrow in arrows :
#----------------------
# 방이 생기는지 검사를할 부분
#----------------------
points[point].add(arrow)
point = add(point, move[arrow])
return answer
주석처리 한부분에 방이 생기는지 체크를 해야합니다.
check room
방이 생기나 안생기나 검사를 해야합니다.
우선 간단하게 생각해보면
- 다음
point, 즉next_가 기존 벽과 충돌하는지.
points의key들 중에next_가 있는지?arrow끼리 크로스가되는지.
이 두가지 조건을 충족시키면 방이 생겼다고 판단하면 되는데, 큰 문제가 있습니다.
우선 1번 조건부터 봅시다. next_가 기존벽과 출돌하면 방이 생기므로
def check(point, next_, arrow) :
return next_ in points
이렇게 만들어주면 됩니다. 하지만 이러한 경우를 한번 생각해 봅시다.
마지막 arrow는 next_ in points를 충족합니다. 하지만 방은 생기지 않았습니다. 바로 중복 때문인데 이 중복을 걸러내야합니다.
중복이 생기는 경우
- 현재
point : arrow가 이미points에 들어있는 경우next_ : -arrow가 이미points에 들어있는 경우
이 경우의 수들이 안생기는 조건을 고려해주어야 겠죠.
첫번째 경우는 그냥 그대로 조건을 반대로 추가해주시면 됩니다.
def check(point, next_, arrow) :
return next_ in points and arrow not in points[point]
두번째 조건의 반대는 -arrow not in points[next_] 입니다. 하지만 이 -arrow라는 arrow의 역방향을 구해야하는데 모듈러연산을 이용하면 아주 쉽습니다.
각 arrow는 역방향과 차이가 4만큼 납니다. 그리고 모든 arrow는 0~7 까지 8진수로 볼 수 있습니다. 시간을 15시는 3시로 보는 것 처럼 arrow가 12라는 것은 arrow = 4 로 생각해 주면됩니다. 따라서 arrow의 역방향은 (arrow + 4)%8 을해주면 간단하게 구할 수 있습니다.
def check(point, next_, arrow) :
return next_ in points and arrow not in points[point] and (arrow+4)%8 not in points[next_]
from collections import defaultdict
def add(x, y) :
return (x[0]+y[0], x[1]+y[1])
def solution(arrows):
global points
answer = 0
move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] # arrow의 (dh, dw) 배열
points = defaultdict(set)
point = (0, 0)
for arrow in arrows :
#----------------------
# 방이 생기는지 검사를할 부분
next_ = add(point, move[arrow])
answer += 1 if check(point, next_, arrow) else 0
#----------------------
points[point].add(arrow)
point = next_
return answer
반쪽짜리 check 입니다.
arrow 의 크로스
저는 이 조건을 조금 다른시각으로 봤습니다. 만약 point들의 움직임이 1칸씩 움직이는게 아니라 0.5칸씩 움직인다면 굳이 크로스되는 경우를 생각할 필요가 없다! 입니다. 반칸씩 움직이면 굳이 크로스되는 조건을 생각할 필요 없이 반칸씩만 움직이게 만들면 됩니다. 바로
def add(x, y) :
return [(x[0]+y[0]/2, x[1]+y[1]/2), (x[0]+y[0], x[1]+y[1])]
좌표끼리 더하는 add 함수를 반칸씩 움직이는 좌표를 추가로 return 하게 한뒤 반복문을 써줬습니다.
from collections import defaultdict
def add(x, y) :
return [(x[0]+y[0]/2, x[1]+y[1]/2), (x[0]+y[0], x[1]+y[1])]
def check(point, next_, arrow) :
return next_ in points and arrow not in points[point] and (arrow+4)%8 not in points[next_]
def solution(arrows):
global points
answer = 0
move = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
points = defaultdict(set)
point = (0, 0)
for arrow in arrows :
for next_ in add(point, move[arrow]) :
answer += 1 if check(point, next_, arrow) else 0
points[point].add(arrow)
point = next_
return answer
주의 해야할 점은 points를 dictionary를 쓰지않고 list로 쓰면 시간초과가 뜹니다. 그 이유를 찾아보니 자료구조에서 search하는데 들어가는 시간이 dictionary가 유의미하게 훨씬 빠르기 때문에 그렇다고 합니다.