코딩테스트 요격 시스템 (프로그래머스) 파이썬
코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다.
(지문 하단에 별도 저작권 표시 문제 제외)
코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.
문제 정보
- 프로그래머스
- 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/
댓글 남기기