[Google Kick Start] 2021 구글 킥스타트 Round D Cutting Intervals 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b933#problem

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

보통 이런 문제는 그리디 방식으로 풀면 되고, 시간복잡도를 고려하면 중간의 range가 아닌 각 구간의 양 끝단에만 집중하면 된다.

(1,3), (2,4), (1,4)가 input으로 주어지고 C가 3인 경우를 가정해보자(문제에서 주어진 sample case) 몇 가지 관찰이 필요한 문제이다.

1. 각 구간의 양 끝단은 cut하여도 전체 interval 갯수에 변화가 없다.

2. 해당 지점을 cut하였을 때 새로 생기는 interval의 갯수는 해당 지점에 영향을 받는 interval의 갯수이다.

3. a~b 사이에 가능한 possible_cut은 b-a만큼 존재한다.

각 구간의 (시작점+1)엔 1을 더해주고 (끝점)엔 -1을 더해준다. 위의 예시로 구해보면 [(2,2), (3,0), (4,-2)]가 된다. 각 순서쌍에서 첫번째 수가 해당 position을 나타낸다. 1에서 시작하는 구간이 2개니까 (2,2) 2에서 시작하는 구간이 1개, 3에서 끝나는 구간이 1개니까 (3,0) 4에서 끝나는 구간이 2개니까 (4,-2)가 된다.

이를 해석해보면 2~3까지는 영향을 받는 line이 2개이고, 해당 구간에서 가능한 cut의 갯수는 3-2=1개이다.

이를 토대로 각 지점 사이마다 몇 개의 interval이 영향을 받는지를 알 수 있고 위에서 서술한 관찰 2를 통해 해당 구간에서 가능한 cut에 따른 새로 생성되는 interval을 계산할 수 있다.

문제의 조건은 가장 많은 interval을 만들어내는 것이므로 영향을 받는 interval의 갯수에 따라 내림차순으로 정렬하여 탐색해 나가면 된다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b933

from collections import Counter

def cuttingIntervals():
    N, C = map(int, input().split())
    intervals = []
    for _ in range(N):
        s, e = map(int, input().split())
        intervals.append((s,e))

    pos_lines = {}
    for s, e in intervals:
        if s+1 not in pos_lines:
            pos_lines[s+1] = 0
        pos_lines[s+1] += 1
        if e not in pos_lines:
            pos_lines[e] = 0
        pos_lines[e] -= 1
    pos_lines = sorted(pos_lines.items())
    # print(pos_lines)

    cuts_lines = []
    affected_lines = 0
    for i in range(len(pos_lines)-1):
        affected_lines += pos_lines[i][1]
        possible_cuts = pos_lines[i+1][0] - pos_lines[i][0]
        cuts_lines.append((affected_lines, possible_cuts))
    cuts_lines = sorted(cuts_lines, reverse=True)
    
    ans = N
    for lines, cuts in cuts_lines:
        if cuts<=C:
            ans += lines * cuts
            C -= cuts
        else:
            ans += lines * C
            break
    return ans


for t in range(int(input())):
    print(f"Case #{t+1}: " + str(cuttingIntervals()))