문제
https://school.programmers.co.kr/learn/courses/30/lessons/181188
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
미사일 최소 개수 구하기
#A(폭격)는 x축에 평행한 직선(s,e)
#B(요격)는 y축에 평행한 직선(x값, float)으로 A에 해당하는 것 모두 관통가능
## 단 s,e 점은 해당x
범위
targets=[1,500000]
s,e=[0,100000000]
풀이
1. 정의
구해야 하는 선의 개수 : lines
겹치는 구간 : overlaps
2. targets의 시작값이 낮은 순서대로 정렬
3. 겹치는 구간 정의
overlaps(e)는 targets의 한 구간의 시작점(s)보다 크면 overlaps를 새로 정의
s는 가장 큰 수, e는 가장 작은 수가 겹치게 됨
4. 겹치지 않는 구간 정의
새로운 s,e가 overlaps가 되면서 lines +1
def solution(targets):
lines, overlaps = 0, {'s':0, 'e':0}
target = sorted(targets)
for s, e in target:
#겹치는 부분
if s<overlaps['e']:
overlaps['s']=max(s, overlaps['s'])
overlaps['e']=min(e, overlaps['e'])
#안겹치는 부분
else:
overlaps['s']=s
overlaps['e']=e
lines+=1
return lines
'코딩 테스트' 카테고리의 다른 글
BFS 구현 방법 2가지 정리(visted, time) (0) | 2025.02.04 |
---|---|
[백준 1260번] DFS와 BFS 파이썬 (1) | 2023.04.15 |
[구름] 밀도 정렬 파이썬 (0) | 2023.04.14 |
[백준 1931번] 회의실 배정 파이썬 (0) | 2023.04.14 |
[백준 10989번] 수 정렬하기3 파이썬 python (0) | 2023.04.14 |
댓글