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

정말 오랜만에 포스팅합니다. 그동안 일하느라 바쁘기도 했고, 알고리즘 공부도,  CS 공부도 조금 소홀하긴 했습니다. 아무튼 오늘 풀어본 문제는 프로그래머스의 요격시스템이라는 문제입니다. 이 문제는 파이썬으로 해결하였습니다. 참고로 코드만 올려놓으면 가끔씩 제가 푼 문제를 제가 봐도 이해가 안 되는 경우가 있어서, 쉽게 설명을 해볼까 합니다. 

 

참고로 해당 문제는 문제 바로가기 링크를 눌러서 확인하실 수 있습니다.

 

문제 설명

요격시스템 문제설명

위 사진은 해설을 쉽게 이해하기 위해서 캡쳐해온 문제 설명입니다. 자세한 내용은 프로그래머스 홈페이지에서 확인해 보시기 바랍니다. 아래 사진은 제한사항과 입출력 예입니다. 

제한사항과 입출력 예

문제 해결 아이디어

링크에서 입출력 예에 있는 사진을 보고 아이디어를 얻었습니다. 입출력 예 설명의 사진을 보면 1번과 5번 근처와 11번과 12번 사이에서 한번 더 발사해서 총 3번 발사했습니다. 4에서 발사를 하면 총 4개의 미사일을 한 번에 요격할 수 있을 것 같은데, 굳이 1.5번(?)과 4.5번(?)에서 발사한 데는 이유가 있겠죠. 제가 여기서 얻은 아이디어는 마지막 부분이 4일 때, 4에서 발사하면 요격하지 못한다는 것입니다.

 

즉, target = [s, e]일 때, e에서는 요격이 불가능하니, s <= target < e라고 생각할 수 있습니다. 그렇다면, e를 기준으로 오름차순 정렬을 한 이후, 다음 요소의 s가 현재 요소의 e보다 같거나 크면 미사일을 하나 추가해야 하는 것이고, 다음 요소의 s가 현재 요소의 e보다 작으면 한 개의 미사일로 두 개의 타깃을 모두 요격시킬 수 있는 것이죠.

 

위의 아이디어를 문제 예시를 통해 시뮬레이션 해보도록 하겠습니다. 먼저 문제에서 targets를 e를 기준으로 오름차순 정렬을 진행하면 아래와 같이 정렬됩니다.

 

1: [1, 4]

2: [4. 5]

3: [3, 7]

4: [4, 8]

5: [5, 12]

6: [11, 13]

7: [10, 14]

 

3에서 요격미사일을 발사하면 1번과 7번을 요격시킬 수 있습니다. 그럼 남는 미사일은 아래와 같습니다.

 

2: [4. 5]

4: [4, 8]

5: [5, 12]

6: [11, 13]

7: [10, 14]

 

4에서 미사일을 발사하면 남는 미사일은 다음과 같습니다.

 

5: [5, 12]

6: [11, 13]

7: [10, 14]

 

그리고 마지막으로 11에서 미사일을 발사하면, 모든 미사일이 요격되는 것입니다. 이걸 파이썬으로 코딩해 보도록 하겠습니다.

 

파이썬 코딩

def solution(targets):
    answer, end = 0, 0

    for s, e in sorted(targets, key = lambda x : x[1]):
        if s >= end:
            end = e
            answer += 1
    return answer

 

 

코드 설명

2번째 요소를 기준으로 정렬된  targets를 기준으로 for문을 돌립니다. 문제 해결 아이디어처럼 다음 요소의 s가 e보다 크거나 같으면, 미사일을 하나 더 발사합니다. 그런데 여기서 end라는 변수를 하나 더 놓은 이유는 요격미사일 한 번 발사로 여러 개의 미사일을 요격하기 때문입니다. 즉, 다음 요소들의 s가 end보다 작은 미사일들은 모두 요격되기 때문에, 요격되지 않은 미사일 중 첫 번째 미사일의 e가 end 되는 것입니다.

 

마치며

코드자체는 굉장히 쉬운편에 속하지만 설명이 이해되지 않으실 수도 있다고 생각합니다. 그래도 최대한 쉽게 설명한다고 설명했는데, 이해가 되셨으면 좋겠습니다.