문제 설명
A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다.
A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다.
A 나라와 B 나라가 싸우고 있는 이 세계는 2 차원 공간으로 이루어져 있습니다. A 나라가 발사한 폭격 미사일은 x 축에 평행한 직선 형태의 모양이며 개구간을 나타내는 정수 쌍 (s, e) 형태로 표현됩니다. B 나라는 특정 x 좌표에서 y 축에 수평이 되도록 미사일을 발사하며, 발사된 미사일은 해당 x 좌표에 걸쳐있는 모든 폭격 미사일을 관통하여 한 번에 요격할 수 있습니다. 단, 개구간 (s, e)로 표현되는 폭격 미사일은 s와 e에서 발사하는 요격 미사일로는 요격할 수 없습니다. 요격 미사일은 실수인 x 좌표에서도 발사할 수 있습니다.
각 폭격 미사일의 x 좌표 범위 목록 targets이 매개변수로 주어질 때, 모든 폭격 미사일을 요격하기 위해 필요한 요격 미사일 수의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한 사항
1 ≤ targets의 길이 ≤ 500,000
targets의 각 행은 [s,e] 형태입니다.
이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
0 ≤ s < e ≤ 100,000,000
입출력 예
targets: [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]
result: 3
문제 풀이
실패한 풀이
targets 배열의 원소(구간 배열) 하나하나를 시작 좌표부터 끝 좌표까지 0.5씩 증가하면서 증가할때마다 겹치는 원소(구간 배열)이 있는지 다시 for 문으로 돌면서 해당 배열이 앞에서 이미 다른 배열과 겹친 배열인지, 아니면 처음 겹침을 당하는? 배열인지 검사해서 가장 많이 겹치는 좌표의 위치를 집합에 저장한다. 이렇게 되면 targets 배열의 원소 각각에서 가장 많이 겹치는 구간이 일치하는 좌표가 발생하게 되고, 집합에 해당 좌표를 넣으므로 중복이 제거된다. 결과적으로 중복이 제거된 집합의 원소 개수를 반환한다.
...라고 생각을 했다. 그러나 구현하기에 너무 복잡했고, 1차원적인 생각이었다. 전혀 효율적이지 않았다.
def solution(targets):
dict={}
for idx, t1 in enumerate(targets):# 해당 폭격 미사일에 겹치는 다른 폭격 미사일의 최대갯수인 x좌표를 앞에서부터 찾음
x_max = 0 # 해당 폭격 미사일에 가장 많이 다른 폭격 미사일이 겹칠때의 x좌표
max_c = 0
for x in range(t1[0], t1[1], 1):#해당 폭격 미사일 구간을 1씩 이동하며 최대 겹침 개수를 찾음
x_c=0 #좌표별 겹침 개수
for t2 in targets:#다른 폭격 미사일들의 구간을 검색하면서
if t1[0] <= t2[0] and t2[0] < t1[1]: #다른 폭격 미사일이 해당 폭격미사일에 x좌표일때 겹친다면
x_c+=1
print(t1[0],t1[1], "이 최대로 겹친 개수: ", x_c)
if x_c > max_c: #해당 좌표에서 겹치는 개수가 지금까지 가장 많이 겹치는 개수보다 큰 경우
max_c = x_c
x_max = x
dict[idx] = x_max # 앞에서 부터 시작해 가장 많이 다른 폭격 미사일과 겹치는 좌표를 해당 폭격 미사일의 인덱스에 맞춰 표기
print("t1", t1[0],",",t1[1],"이 최대로 겹치는 구간의 x좌표는 ",x_max+0.5,"이다.")
print(dict.values())
print(len(set(list(dict.values()))))
return 0다른 풀이(참고만하고 내가 다시 풀었음)
targets 배열을 원소(구간 배열)의 첫번째 값, 두번째 값 순서로 우선 순위를 두고 정렬을 수행한다.
=> 첫번째 값에 대해 오름차순이면서 첫번째 값이 중복되면 두번째 값에 대해 오름차순이게 됨
targets 배열을 앞에서부터 순회하면서 첫번째 원소일때는 해당 원소의 두번째 값을 기준으로 삼는다.
다음 원소의 첫번째 값이 두번째 값보다 작으면 겹친다는 의미이다. 그러면 기준을 변경하지 않고 그 다음 원소의 첫번째 값에 대해 동일한 비교 과정을 거친다.
*이때 모든 폭격미사일이 겹칠 조건은 다음 폭격미사일의 첫번째 원소가 지금까지 겹친 폭격미사일의 가장 작은 두번째값보다 작아야한다.
만약 기준값이 해당 원소의 첫번째 값보다 같거나 작다면 기준값을 해당 원소의 두번째 값으로 변경하고 요격 미사일 개수를 1증가시킨다.
def solution(targets):
answer=0
pivot=0
sp=0
targets.sort(key=lambda x: (x[0],x[1]))
for t in targets:
if sp <= t[0] or pivot <= t[0]:
answer+=1
pivot=t[1]
sp=t[1]
elif t[1] < sp:
sp = t[1]
return answer=> 이렇게 풀리긴 하지만, 아래 코드처럼 동일 기능을 하는 더 짧은 코드를 생각해낼 수 있다.
개선한 풀이
targets 이 x[0], x[1] 의 우선순위로 정렬되어 있으므로, 우리는 x[0] 이 pivot 보다 앞에 있는지만 검사하면 된다. pivot 보다 앞에 있으면 무조건 겹친다는 의미이다.
만약 겹쳐질 수 있다면, 겹쳐진 범위를 표현하기 위해 pivot을 방금 겹친 구간의 가장 끝값과 비교해 작은값으로 설정한다.
def solution(targets):
answer=0
pivot=0
targets.sort(key=lambda x: (x[0],x[1]))
for t in targets:
if pivot <= t[0]:
answer+=1
pivot=t[1]
else:
pivot=min(t[1], pivot)
return answer다시 개선한 풀이
targets 배열을 x[1] 을 기준으로만 정렬하면 됐었다. x[1] 보다 다음 구간의 x[0] 이 작은지 작지 않은지를 비교하고 작으면 무조건 겹치게 된다.
만약 겹친다면 기존 구간의 끝값(pivot)와 해당 구간의 x[1] 을 비교하여 더 작은 값을 pivot으로 설정하면 되는 문제였다. 그림을 그려보면 이해가 확실히 된다.
def solution(targets):
answer=0
pivot=0
targets.sort(key=lambda x: x[1])
for t in targets:
if pivot <= t[0]:
answer+=1
pivot=t[1]
else:
pivot=min(t[1], pivot)
return answer후기
level2 문제를 처음 풀었다. level1 처럼 단순 사고로 풀 수 있을 줄 알았는데 개인적으로 level1 의 카카오 기출 문제보다 어려웠다. 분발하자!
