[Python/프로그래머스] 요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

세달 전만해도 라인 스위핑의 개념을 모를 때는 어떤 노력을 해도 풀 수가 없었던 문제였다. 하지만 라인스위핑이라는 간단한 컴퓨터적 사고를 이용하면 14줄에 풀 수 있다. 기분이 너무 좋았다.

여기서 중요한 것은 정렬을 어떤 기준으로 하느냐 이다.
뒤쪽 요소를 기준으로 정렬을 하면 되는데, 그 이유를 찾기 위해서는 천천히 생각해봐야 한다.

(내가 Trial and Error 방식으로 정답을 찾고 난 후에야 발견한 것이지만)
정렬을 뒤쪽으로 하는 이유는 언제나 길이가 짧은 것들이 요격을 하는 대상이 되는 것이기 때문이다. 처음에는 정렬을 두 키key = lambda x: (x[0], x[1])) 로 했는데 그렇게 했을 때 문제는 길이는 긴데 시작 값이 먼저 도래하는 것이 기준이 되어서 길이가 긴 요소가 중간에 짧은 요소들을 포함하게 된다는 것이었다. [5,10],[6,8],[8,9] 처럼 정렬이 되면 [5,10]이 line을 10으로 밀어버려서 [6,8],[8,9] 을 skip 시켜버리게 된다. (그러면 실제 2발인데 1발만 사용한 것으로 된다)
반대로 key = lambda x: (x[1]) 하나로 정렬했을 때는 [6,8],[8,9],[5,10] 로 정렬이되고 이때는 line 이 8로 변경 되면서 그다음에 다가오는 연결되지 않은 [8,9] 를 정상적으로 count(요격)할 수 있게 된다.
이런 문제들은 많은 연습을 통해서 감을 익혀두는게 맞겠다. (그런데 이런 단순 기술적인 문제들은 경력직 MLE 코테는 잘 안나오는 거 같다...)

def solution(targets):
    # line sweeping 문제로 풀자.
    target = sorted(targets, key = lambda  x: (x[1]))

    line = 0
    cnt = 0
    for t in target:
        if line < t[1] and line <= t[0]:
            line = t[1] #  line 뒤쪽으로 맞추기
            cnt += 1
        else:
            if t[0] < line: # line 앞쪽에서 시작하는 target들은 skip 한다.
                continue
    return cnt