코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다.
(지문 하단에 별도 저작권 표시 문제 제외)
코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.
문제 정보
- 프로그래머스
- python
- level 2
- 점수 : 12
- 문제 링크
문제
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 | result |
|---|---|
| [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]] | 3 |
풀이 코드
풀이 코드 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 전체 함수
# 정렬을 위한 함수
def sort_list(list):
return [list[1], list[0]]
def solution(targets):
# 앞서있는 target a라는 미사일과 그 뒤에 target b라는 미사일이 있을 때
# 이들을 한꺼번에 요걱하기 위해선 target b의 시작점이 target a의 사이
# 즉 target a의 끝지점 이전에 있어야 한다.
# 정렬하기
targets.sort(key=sort_list)
# 끝점에 따라 요격하고
# 다음 미사일의 시작점이 앞 미사일의 시작점 전이면 함께 요격되는 것으로 여긴다
count = 0
last_shoot_point = 0
for target in targets:
if target[0] >= last_shoot_point:
count += 1
last_shoot_point = target[1]
return count
풀이 코드 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 전체 코드
from itertools import combinations
def solution(targets):
# 변수 선언
all_target_coord = set()
shoot_point = []
shoot_counts = []
# target을 [시작점, 끝점] 에서 [시작점, 시작점 + 1 ... 끝점] 으로 변경
for i, target in enumerate(targets):
targets[i] = [x for x in range(target[0], target[1])]
# all_target_coord에 좌표를 추가
for point in targets[i]:
all_target_coord.add(point)
# 격추할 수 있는 미사일이 2개 이상인 슈팅포인트 리스팅
for i in all_target_coord:
count = 0
for target in targets:
if i in target:
count += 1
if count > 1:
shoot_point.append(i)
# 미사일을 i 개 발사하는 각 경우의 수에서 모든 미사일을 격추하기 위한 발사 횟수 리스팅
for i in range(len(shoot_point)):
for comb in combinations(shoot_point, i+1):
remove_set = set()
for shoot in comb:
for target in targets:
if shoot in target:
remove_set.add(frozenset(target))
shoot_counts.append(i + 1 + len(targets) - len(remove_set))
return min(shoot_counts)
풀이 코드 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 전체 함수
from itertools import combinations
def solution(targets):
# 교집합 구하기
# 한 번에 격추할 수 있는 경우는?
# target a와 target b가 있다고 할 때
# target b의 시작점이 target a의 시작점과 끝점 사이에 있으면 함께 격추할 수 있음
multikill_list = []
for i, target_a in enumerate(targets):
for target_b in targets:
if target_b[0] in range(target_a[0], target_a[1]):
try:
multikill_list[i].append(target_b)
except:
multikill_list.insert(i, [target_a])
# 미사일을 i 개 발사하는 각 경우의 수에서 모든 미사일을 격추하기 위한 발사 횟수 리스팅
shoot_counts = []
for i in range(len(multikill_list)):
for comb in combinations(multikill_list, i+1):
remove_set = set()
multikills = []
for c in comb:
multikills.extend(c)
for target in targets:
if target in multikills:
remove_set.add(frozenset(target))
shoot_counts.append(i + 1 + len(targets) - len(remove_set))
return min(shoot_counts)
리뷰
하루에 한 시간 이상씩 3일동안 문제를 풀었다..
시간 초과를 어떻게 해결해야하나 고민이 많았었는데,
결국 다른 사람의 풀이를 참고했다.
다음엔 어려운 문제는 풀기 전 자신만의 언어로 재구성하는 시간을 갖도록 하자.
Reference
https://wikidocs.net/16040
https://armontad-1202.tistory.com/entry/
https://wikidocs.net/16044
https://www.daleseo.com/python-range/
https://wikidocs.net/16041
https://velog.io/@mang0206/