[프로그래머스] Lv2. 요격 시스템

📝 문제

뭐야 이거 왜 맞아요

풀이

⏰ 아이디어

1️⃣ 먼저 target을 (s, e) 순서대로 정렬
2️⃣ 가장 처음 타겟을 요격 가능한 위치(s1, e1)로 설정
3️⃣ 타겟들을 비교하면서 요격 가능한 위치와 겹치는 부분이 있다면 요격 가능 위치를 업데이트하고,
4️⃣ 겹치는 부분이 없다면 answer +1하고,
5️⃣ 요격 가능한 위치를 업데이트

def solution(targets):
    answer = 1

    targets.sort()
    s1, e1 = targets[0]

    for s2, e2 in targets[1:]:
        if s2 < e1 and s1 < e2:
            s1, e1 = s2, min(e1, e2)
        else:
            answer += 1
            s1, e1 = s2, e2
    return answer

⭕️ 효율적인 풀이

공격이 끝나는 시간이 빠른 것부터 정렬

타겟을 돌면서 타겟의 시작 시간이 현재 정해져 있는 요격이 끝나는 시간보다 늦다면 현재 정해져 있는 요격으로는 요격할 수 없으므로 answer+1

타겟의 끝나는 시간이 빠른 것부터 순서대로 정렬되어 있으므로 뒤에 오는 타겟들의 끝나는 시간이 이전의 타겟들보다 더 빠를 수는 없음!

def solution(targets):
    answer = 0
    
    targets.sort(key=lambda x: x[1])
    end = -1
    
    for s, e in targets:
        if s >= end: # 현재 정해져 있는 요격으로는 방어할 수 없음
            answer += 1
            end = e # 요격 끝나는 시간 변경
            
    return answer