23.05.04 페어프로그래밍: 롤케이크 자르기

문제 설명:

롤 케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

리스트가 입력으로 주어진다. 우리는 이 리스트를 앞/뒤 둘로 나누었을 때, 양쪽의 원소 종류 갯수가 같은 경우의 수를 구해야한다.

 

시도 1. 브루트 포스 1 - set 이용하기

for문을 이용해 1개/n-1개, 2개/n-2개, ... , n-1개/1개인 케이스를 모두 확인한다.

이때 set 를 이용해 양 측의 토핑의 중복을 제거하여 종류 갯수를 구하고, 같으면 경우의 수를 증가시킨다.

def solution(toppings):
    count = 0
    for i in range(1,len(toppings)):
        a=set(toppings[:i])
        b=set(toppings[i:])
        if len(a) == len(b):
            count += 1
    return count

그러나 이와 같은 풀이는 시간초과로 인해 통과되지 못했다.

시간초과가 뜬 이유를 알아본 결과 set 에 원소를 추가하는것은 O(1)의 시간복잡도를 가지고, list를 set으로 변환하는 것은 O(n)의 시간복잡도를 가진다. 즉, 위 코드는 적어도 O(2*n^2)의 시간복잡도를 가진 코드이다.

 

시도 2. 브루트 포스 2 - Counter 사용하기

collections 모듈의 Counter 클래스를 사용해 보기로 하였다. Counter는 반복가능한 객체로 부터 각 값의 갯수를 세어 딕셔너리 형태로 만들어준다. 이 Counter를 이용하여 키 갯수를 비교하면 될 것이라 생각하였다.

from collections import Counter

def solution(toppings):
    count = 0
    a = []
    b = toppings[:]
    for i in toppings:
        a_=Counter(a.append(i))
        b_=Counter(b.pop(0))
        if len(a_) == len(b_):
            count += 1
    return count

그러나 모듈을 사용하는 것은 문제를 해결해 주지 않았다. 기대와 달리 Counter 모듈의 시간복잡도는 그냥 O(n) 이고 C++ 등 더 빠른 언어로 작성된것도 아니었다. 사실 Counter는 dict의 서브 클래스 이기 때문이다.

여기서 근본적인 문제는 n 개짜리 리스트를 반복문 안에서 계속 형변환 하려고 하니 시간복잡도가 O(N^2)이 된 것임을 알게 되었다.

 

해결:  브루트 포스 3 - dict 이용 하기, 미리 선언 후 원소 넣고 빼기

set을 쓰는 대신 대신 dictionary를 사용하고, 반복문 안에서 변수를 초기화하지 않고, for문 밖에서 초기화 한뒤 반복문 안에서는 원소를 넣고 빼는 작업만 하면 시간복잡도O(n)으로 해결가능할 것으로 보였다.

from collections import Counter

def solution3(toppings):
    b = Counter(toppings) # 뒤쪽
    a = dict() # 앞쪽
    count = 0
    for t in toppings:
        a[t] = 1 # 앞쪽에 하나 추가
        b[t] -= 1 # 뒤쪽에서 하나 제거
        if b[t] == 0: # 해당 토핑이 더이상 없으면
            del b[t] # 아예 제거

        if len(a) == len(b): # 키 갯수 비교
            count += 1
    return count

딕셔너리에서 추가/제거 하는것은 O(1)이고, set와 달리 갯수 정보를 저장할 수 있어 더 용이하게 사용이 가능하다. 위 코드를 제출하니 시간안에 통과하였다.

 

흥미로운 답안: 이진탐색

시간복잡도를 최대한 줄였다고 생각했을 때 다음과 같은 흥미로운 정답 코드를 발견하였다.

def solution(topping):
    answer = 0

    l, r = 0, len(topping)
    idx1 = 0
    while l <= r:
        m = (l + r) // 2
        left = len(set(topping[:m]))
        right = len(set(topping[m:]))
        if left < right:
            l = m + 1
        elif left >= right:
            idx1 = m
            r = m - 1

    l, r = 0, len(topping)
    idx2 = 0
    while l <= r:
        m = (l + r) // 2
        left = len(set(topping[:m]))
        right = len(set(topping[m:]))
        if left <= right:
            idx2 = m
            l = m + 1
        elif left > right:
            r = m - 1

    answer = max(idx2 - idx1 + 1, 0)

    return answer

코드 분석:

먼저 주어진 문제의 조건으로부터 유도가능한 사실이 한가지 있다.

롤케익을 자르는 위치를 왼쪽부터 이동 시킬 때, 왼쪽 롤케익의 토핑종류 수는 반드시 오름차순이 되고, 오른쪽 롤케익의 토핑종류 수는 반드시 내림차순이 된다. 즉 (오른쪽 토핑종류수) - (왼쪽 토핑종류수)는 오름차순으로 되어 있고 우리는 그 값이 0인 구간의 시작점과 끝 점을 찾을 수 있다. 이러한 문제는 이진 탐색으로 접근하여 O(logN)의 시간복잡도로 해결할 수 있다.

이 코드는 두번의 이진탐색 알고리즘으로 이루어져 있는데, 첫번째 이진탐색은 왼쪽 롤케익의 토핑 종류 수가 오른쪽 롤케익의 토핑종류 수 보다 크거나 같아지는 첫번째 index를 찾고, 두번째 이진탐색은 왼쪽 롤케익이 오른쪽 롤 케잌 보다 토핑 종류수가 같거나 작은 마지막 index를 찾는다.

 

이렇게 이진탐색으로 찾으니 시간복잡도가 O(2logN)으로 크게 개선될 줄 알았으나, 실제로는 그렇지 않았다. 왜냐하면 실제 코드에서는 각 롤케이크 조각의 토핑 종류 수를 set를 이용해 구했기 때문이다. 즉 실제 구현된 코드의 시간복잡도는 O(2NlogN)이다.

 

이를 해결하기 위해서는 반복문 밖에서 따로 토핑 종류수를 미리 구해 두고, 그 결과에서 이진탐색을 진행할 수 있는데, 이미 토핑 종류수를 미리 구해뒀다면 그 반복문 안에서 정답을 도출할 수 있다.

따라서 가장 시간복잡도가 낮은 풀이는 앞서 dict를 사용한 풀이지만 문제로부터 자명한 사실을 도출하여 이를 이용해 이진탐색을 통한 풀이를 한 점이 인상적이었다.