99클럽 코테 스터디 4일차 TIL - 타인의 풀이를 통해 배우기

문제 1 - 당구 연습 문제링크

프로그래머스

 

오늘 배운 점

타인의 배울 점을 배웁니다.
수학적 직관을 사용해야 할 때가 있습니다.
문제를 똑바로 읽습니다.
 

문제 설명

흰 공이 당구대에 원쿠션 해서 검은 공을 맞추는 경우 중 가장 이동 경로가 가장 짧은 경우의 경로 길이를 구하는 문제입니다.
점선이 바로 경로입니다.

그림 설명

 

입출력 예

입출력 예

 

m: 당구대의 가로 길이
n: 당구대의 세로 길이
startX: 흰 공의 x 좌표
startY: 흰 공의 y 좌표
balls: 검정 공들의 위치

 

접근 과정

우선 처음에는 당구대의 테두리를 순회하면서 해당 지점이 흰 공이 부딪치는 지점일 때, 검은 공을 만날 수 있는지를 따진 후, 만날 수 있다면 그 경로의 거리를 구해서 최솟값이면 갱신하는 방식으로 해결하고자 하였습니다.
 
단순히 시간복잡도를 구해보면, 검은 공의 개수 len(balls) * 각 면의 길이 합(2m + 2n) = O(len(balls) * (2m + 2n))입니다. balls, m, n <= 1000이므로 최대 연산 횟수가 백만 단위 정도 되기 때문에 답이 될 수 있다고 판단했습니다.
 
그리고 최적화를 위해 검은 공 기준으로 가로, 세로 수직선 두 개를 그은 후, 해당 수직선상에서 검은공과 예상 검은 공 사이의 거리를 기준으로 이분 탐색을 진행하여 테두리 순회를 O(n + m)로 구현하지 않고 O(logn + logm)로 구현하는 방식을 생각했습니다.
 
하지만 이 방법으로는 풀 수 없다는 걸 알게 되었습니다.
흰 공과 검은 공이 배치된 위치만 x, y 값이 둘 다 정수 값이지 흰 공이 당구대에 부딪힌 위치의 x, y 좌표가 모두 정수값이라는 보장이 없기 때문이었습니다. 따라서, 애초에 테두리 순회 방식은 정수 단위로 순회하기 때문에 답이 될 수 없는 방법이었습니다.
 
결국 풀지 못했고, 다른 분의 풀이 발표 시간 때 획기적인 정답을 알게 되었습니다.
검은 공을 당구대 모서리 기준으로 대칭 이동해서 흰 공과 대칭 이동된 검은 공과의 거리를 구하는 방법이었습니다. 삼각형의 닮음을 이용하여, 아래 식을 만족하게 됩니다.

 $ \overline{\textbf{AB}} + \overline{\textbf{BC}} = \overline{\textbf{AC}} $
(A: 흰 공, B: 흰 공이 부딪힌 지점, C: 대칭 이동한 검은 공)

 
대칭이동하는 방식은 O(len(balls))의 시간복잡도로 문제를 풀 수 있었습니다.
 
문제 풀이 방법 자체는 이렇게 되고, 코드를 작성할 때 4개의 모서리에 대해 서로 다른 함수를 적용해야 했습니다. 이때 발표자분은 배열과 람다를 사용하여 별도의 조건문 없이 깔끔한 코드를 작성하는 방식으로 푸셨습니다. 그래서 일단 이렇게 풀어보기 전에 일반적으로 제가 풀던 방식대로 풀어본 후 저 방법을 적용해보았습니다.

정답코드(개선 전)

def in_line(x1, y1, x2, y2, dir):
    if dir == 0:
        return x1 == x2 and y1 < y2
    elif dir == 1:
        return y1 == y2 and x1 < x2
    elif dir == 2:
        return x1 == x2 and y1 > y2
    return y1 == y2 and x2 < x1
            
def flip(x, y, dir, m, n):
    if dir == 0:
        return [x, 2*n - y]
    if dir == 1:
        return [2*m - x, y]
    if dir == 2:
        return [x, -y]
    return [-x, y]

def getDist(x1, y1, x2, y2, dir, m, n):
    x2, y2 = flip(x2, y2, dir, m, n)
    return (x1 - x2)**2 + (y1 - y2)**2
    

def solution(m, n, startX, startY, balls):
    answer = []
    
    for ball in balls:
        minDist = float('inf')
        for i in range(4):
            if not in_line(startX, startY, ball[0], ball[1], i):
                dist = getDist(startX, startY, ball[0], ball[1], i, m, n)
                if minDist > dist:
                    minDist = dist
        answer.append(minDist)
    return answer

 
상하좌우 중 어떤 모서리인지를 나타내는 dir 변수가 in_line과 flip에서 분리처리 용도로 사용되는 것을 확인할 수 있습니다. 보다시피 코드가 다소 지저분한 모습을 보입니다.
 

개선 후 정답코드

in_line = (
    lambda x1, y1, x2, y2 : x1 == x2 and y1 < y2,
    lambda x1, y1, x2, y2 : y1 == y2 and x1 < x2,
    lambda x1, y1, x2, y2 : x1 == x2 and y1 > y2,
    lambda x1, y1, x2, y2 : y1 == y2 and x1 > x2
)

flip = (
    lambda x, y, m, n : (x, (n<<1) - y),
    lambda x, y, m, n : ((m<<1) - x, y),
    lambda x, y, m, n : (x, -y),
    lambda x, y, m, n : (-x, y)
)

def getDistance(x1, y1, x2, y2):
    return (x1 - x2)**2 + (y1 - y2)**2

def solution(m, n, startX, startY, balls):
    answer = []
    
    for ball in balls:
        distances = (
            getDistance(startX, startY, *flip[i](ball[0], ball[1], m, n))
            for i in range(4)
            if not in_line[i](startX, startY, ball[0], ball[1])
        )
        answer.append(min(distances))
    return answer

 
변경점1 - flip과 in_line이 람다함수를 담는 튜플로 변경되었습니다.
기존에 dir로 처리하던 로직은 dir을 인덱스화함으로써 별도의 if else 문 없이 바로 람다함수에 접근할 수 있게 되었습니다. lambda x, y, m, n같이 중복해서 작성되는 부분이 있긴 하지만 코드가 훨씬 깔끔해졌습니다.
 
변경점2 - getDistance()는 flip 처리 없이 오직 두 점 사이의 거리만 반환합니다.
기존에는 flip() 처리가 getDistance() 내부에서 이루어졌기 때문에 범용성이 떨어지는 함수였습니다. flip()처리를 외부에서 해줌으로써 하나의 작업만 수행하도록 변경했습니다.
 
변경점3 - 4방향을 탐색할 때 파이썬 특유의 방식인 list comprehension 기법을 사용합니다.
여기서, list가 아니라 (), 즉 tuple로 거리 계산 값들을 감싸주었는데, 이렇게 하면 distances의 형태가 궁금해 출력해보았습니다.

generator object

알게된 점1 - distances는 제너레이터 타입임을 확인할 수 있었습니다.(참고자료)
제너레이터 타입이 뭔지, 그리고 왜 굳이 제너레이터로 만들어 사용하는지 의문이 들어 찾아본 결과, 제너레이터를 사용하면 메모리를 효율적으로 사용할 수 있게 된다고 합니다. 왜냐하면, 제너레이터 타입은 Lazy Evaluation을 지원해서 실제로 내부 원소들이 사용될 때가 돼서야 메모리에 해당 원소가 적재되기 때문입니다. 즉, 해당 코드에서 min(distances)를 하며 원소 각각에 접근하여 평가될 때 비로소 실제 값들이 메모리에 적재됩니다.
 
알게된 점2 - flip 앞에 *(asterisk)가 붙어 있고, 이를 unpacking이라고 합니다.(참고자료)
tuple 타입의 filp 반환 값을 풀어헤치는 역할을 합니다.
 

총평

아직 함수화하는 실력이 부족하다고 느꼈습니다.
먼저 전체 로직을 계획한 다음, 각 기능에 해당하는 함수 호출 코드를 작성하고 나중에 실제 구현을 진행하겠습니다.