[프로그래머스] 중앙값

📁 문제

길이가 N 인 수열 A1, A2, ⋯, AN 이 주어질 때, 수열의 중앙값을 구해보자. 길이가 N 인 수열 A 의 중앙값은 수열을 정렬했을 때 (N + 1) / 2 번째 위치의 원소를 의미한다. 수열의 가장 첫 원소는 1번째에 위치해있다.

 

 

📁 제한사항

• 1<= targets 길이 <= 500,000
• targets의 각 행은 [s, e]의 형태입니다.
• 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야합니다.
• 0 <= s < e <= 100,000,000

 

 

 

📁 입출력 예시

• [[4, 5], [4, 8], [10, 14], [11, 13], [5, 12], [3, 7], [1, 4]] => 3
• [[0, 4], [5, 10], [6, 8], [8, 9]] => 3
• [[0, 4], [1, 2], [1, 3], [3, 4]] => 2
• [[0, 4], [0, 1], [2, 3]] => 2
• [[3, 6], [2, 4], [5, 6], [1, 3]] => 2

첫번째 테스트케이스의 경우, 위 그림과 같이 세번의 요격 미사일 발사로 전부 방어할 수 있다.

 

 

 

📁 풀이

첫번째 풀이

def solution(targets):
    result = 0
    while targets :
        max_target = 0
        for a, b in targets :
            if max_target < b :
                max_target = b
        count_list = [0]  * (max_target+1)
        for a, b in targets :
            for j in range(a, b) :
                count_list[j] += 1
        max_count = count_list.index(max(count_list))
        new_targets = []
        for i in targets :
            a, b = i
            if not (a <= max_count and b > max_count) :
                new_targets.append(i)
        targets = new_targets
        result += 1
    return result

처음에는 새 리스트를 만들어서, 예를 들어 0-1 범위에 폭격되는 수를 0인덱스에 저장하는 식으로 폭격 수를 저장 후, 가장 수가 많은 구간의 경우를 targets에서 제거하는 식으로 진행했다.

3중 반복을 사용하였으므로 시간 초과가 발생할 것은 당연했는데, 3번 테스트케이스의 실패는 이유를 모르겠다 ㅠㅠ

 

두번째 풀이

def solution(targets):
    targets.sort(key=lambda x:x[1])
    s, e = 0, 0
    answer = 0
    for a, b in targets :
        if e <= a :
            e = b
            answer += 1
        
    return answer

구글 검색으로 힌트를 얻어 진행했다.