프로그래머스 [요격 시스템] 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

처음 문제를 접했을 때, 많이 겹치는 것을 요격하는 그리디와 x 좌표를 기준으로 파라메트릭 서치 중 어떤 것을 사용해야하나 고민을 했고, 워낙 그리디적인 부분이 강하기도 했고, 파라메트릭 서치로 접근하는 방식도 문제와 적합하지 않아서 전자의 방식을 택했다.

 

그리디로 총 3가지 시도를 하였는데, 초기 접근이 잘못되어 많은 시간을 소모했다.

1. 가장 짧은 길이의 공격을 우선적으로 순회하며 겹치는 공격을 요격하면서 숫자를 센다.
2. 많이 겹치는 부분을 찾아서 해당 부분과 관련된 공격을 요격하면서 숫자를 센다.
3. 각 공격의 마지막 지점 위치가 작은순(좌표상 왼쪽)으로 우선 탐색해서 
   이후 공격 중 겹치는 공격이 있다면 같이 요격하고, 겹치는 부분이 없다면 새로운 요격을 준비한다.

 

예제처럼 공격하는 것이 합리적이라는 판단을 했고, 1, 2번 중 하나로 문제를 풀 수 있겠다고 생각을 했고 어떻게든 그 안에서 정답을 찾으려고 노력했다. 자료구조 선택, 겹치는 부분에 대한 알고리즘 처리에 대한 고민을 많이 했는데 결국 정답을 구할 수는 없었다.

다른 방법을 찾으려고 풀이를 엎고 다른 그리디 방식을 찾으려고 노력했다. 최종적으로 찾은 방안은 위의 방안 중 3번이며, 해당 그리디 방식을 선택하기 위한 과정은 아래와 같다. 

 

정답 접근 방법

이전 1, 2번의 경우 예제를 통해 접근했는데, 뭔가 놓지고 있어서 기본적인 예시를 직접 그려가며 어떻게 요격을 하는 것이 합리적인가를 고민했고, 아래 그림을 활용하여 접근 방법을 찾을 수 있었다.

1. 부분적으로 겹치는 경우
2. 한 공격이 다른 공격에 포함되는 경우
3. 겹치지 않는 경우

 

 

1. 부분적으로 겹치는 경우

 

한 공격의 시작점과 다른 한 공격의 종료지점 사이를 요격하면 동시에 요격할 수 있다.

 

---

 

 

2. 한 공격이 다른 공격에 포함되는 경우

겹치는 부분 중 짧은 부분의 시작지점과 종료지점 사이의 한 곳을 요격하면 동시에 요격할 수 있다.

 

 

---

 

 

3. 겹치지 않는 경우

겹치는 부분이 없기 때문에 하나씩 요격을 해야한다.

 

---

 

 

모든 공격은 위의 3가지로 분류할 수 있다.  3번의 경우는 관통을 할 수 없지만, 1,2번의 경우 관통을 통해 미사일의 수를 줄일 수 있기 때문에 1,2번 경우의 겹치는 부분을 분석할 필요가 있다.

그리디로 접근하기 위한 일정한 기준을 찾기 위해 두 공격의 공통점을 찾으려고 했다. 2번의 경우, 긴 공격에 속하는 짧은 공격은 항상 긴 공격보다 빨리 끝나게 되기 때문에 기존에 [짧은 공격 시작지점, 짧은 공격 끝지점] -> [먼저 끝나는 공격의 시작지점, 먼저 끝나는 공격의 끝 지점] 으로 치환해도 상관없다. 이렇게 치환하면, 1번과 2번 공격의 공통점을 찾을 수 있다. 둘 다 [먼저 끝나는 공격의 마지막 지점]을 가지고 있다는 것이며, 해당 지점을 위주로 요격을 하면 공통된 공격들을 같이 요격할 수 있다. 

 

위의 설명으로 [먼저 끝나는 공격] 의 [마지막 지점] 이 핵심이라는 것을 알 수 있었다. [먼저 끝나는 공격]을 우선적으로 볼 필요가 있으며 [각 지점의 마지막 지점]을 우선적으로 확인해가며 다음 공격이 겹친다면 같이 요격을 하고 그렇지 않은 경우에는 다음 미사일 발사를 준비한다.

 

만약 아래 그럼처럼 현재 공격과 다음 공격이 겹치지 않는데, 현재 공격과 다다음번(혹은 그 이후) 공격이 겹치게 되면 어떻게 될까? 현재 공격을 요격할 때 다다음번 공격은 요격되지 않지만, 이후 다음 공격을 요격할 때 다다음번 공격이 같이 요격되기 때문에 정상적으로 요격이 수행된다.

 

결론

생각을 하게 된 과정을 설명하느라 글이 길어졌다. 답을 도출하기 위한 처리과정은 아래와 같다.

1. 마지막 지점을 기준으로 오름차순 정렬한다.(우선순위 큐 활용)
2. 큐를 순회하면서 가장 빨리 끝나는 공격을 선택하고, 이후 겹치는 공격이 있다면 같이 요격한다(큐에서 pop한다)
	2.1. 겹치는 공격이 없다면 다음 공격으로 넘어간다.

 

 

시간 복잡도

우선순위 큐를 사용하여 탐색하기 때문에 O(NlogN)의 시간이 걸리며, N의 최댓값이 51e5이므로 시간 내에 동작한다.

 

 

코드

import heapq

def solution(targets):
    pq=[]
    
    # 우선순위 큐에 마지막 지점을 기준으로 오름차순 정렬되도록 삽입한다.
    for start,end in targets: 
        heapq.heappush(pq,[end,start])
    
    # attack_point= 요격할 지점을 설정한다.
    attack_point=heapq.heappop(pq)[0]
    answer=1
    
    while pq:
        end,start=heapq.heappop(pq)   
        if start<attack_point: # 다음 공격의 시작위치가 요격 위치보다 왼쪽에 있다면 같이 요격한다(큐에서 pop 되도록 continue)
            continue
        
        # 요격할 위치보다 오른쪽에 있다면 요격위치를 갱신하고, 요격 개수를 1 증가시킨다.
        attack_point=end
        answer+=1
    
    return answer

 

 

회고

평행한 가로 선을 최소한의 세로선으로 제거하는 방법
>> 끝 지점을 오름차순하여 현재 가로선 기준으로 다음 겹치는 가로선을 관통시키고, 
   다음 선이 겹치지 않는다면 새로운 새로선을 추가한다.