[홀로 하는 코딩 공부] 롤케이크 자르기(Python)

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

 

---

▶ 처음에 본 문제를 보고 자르는 위치에 따라 왼쪽 오른쪽의 고유값 개수가 같으면 +1 씩하는 것이니, 위치를 인덱스로 보아서 처음부터 끝까지 완전 탐색해보려하였다. 하지만 문제 조건에서 topping의 길이가 1,000,000인것을 보고 완전탐색을 하게되면 시간초과가 날 것이라고 생각되어 이분탐색을 생각하였고, 아래와 같이 코드를 작성하였다.

def solution(topping):
    answer = []
    right, left = 0, len(topping) - 1

    while right < left:
        mid = (right + left) // 2
        rt = set(topping[:mid])
        lt = set(topping[mid:])

        if len(rt) == len(lt):
            if mid in answer:
                break
            else:
                answer.append(mid)
                if mid > len(topping)//2:
                    left = mid
                else:
                    right = mid + 1
        elif len(rt) < len(lt):
            right = mid + 1
        else:
            left = mid
            
    return len(answer)

 

 

▶ 2개의 기본 테스트 케이스는 통과이지만 제출하면 결과가 처참하다.

▶ 단순하게 생각해보기로했다. 자르는 위치가 1번째 일때, 1번을 기준으로 왼쪽 set의 개수와, 오른쪽 set의 개수를 저장하고 그다음 2번째 일때 똑같은 방식으로 하여 왼쪽 set의 개수가 담긴 배열과 오른쪽 set의 개수가 담긴 배열을 만들어놓는다. 그리고 왼쪽 set의 개수가 담긴 배열과 오른쪽 set의 개수가 담긴 배열에서 배열의 첫번째 값부터 같게 하면 되지 않을까해서 아래와 같이 작성하였다.

def solution(topping):
    right_num, left_num = [], []

    for idx, top in enumerate(topping):
        right_num.append(len(set(topping[:idx])))
        left_num.append(len(set(topping[idx:])))

    answer = [i for i in range(len(right_num)) if right_num[i] == left_num[i]]

    return len(answer)

 

 

▶ 이것 또한 처참한 결과이다. 그래도 틀린게 아니라 "시간 초과"로 실패다. 그러면 시간 소요를 줄이는 방향으로 코드를 수정해본다. 코드를 살펴보면, 아마 topping배열에서 idx를 기준으로 왼쪽 전체값을 가져오는 부분이 시간소요가 컸을 거라고 예상이 된다. 그래서 그부분을 변경해본다. right_set에 값을 하나씩 추가한다. 그렇게 되면 left_set에는 거꾸로 값이 추가되어야하니 topping길이에서 idx를 빼고 1을 뺀 값을 추가한다. 그리고 right_num과 left_num이 같을 때가 고유 값의 개수가 같을 때이다. 하지만 left_num에는 거꾸로 추가한 값의 길이가 들어가있으므로 right_num의 값은 처음부터 비교해주고 left_num의 값은 뒤에서 두번째 값부터 왼쪽으로 비교해주면 된다.

def solution(topping):
    right_num, left_num = [], []
    right_set, left_set = set(), set()

    for idx, top in enumerate(topping):
        right_set.add(top)
        right_num.append(len(right_set))

        left_set.add(topping[len(topping) - idx - 1])
        left_num.append(len(left_set))

    len_left = len(left_num)
    answer = [i for i in range(len(right_num) - 1) if right_num[i] == left_num[len_left - i - 2]]

    return len(answer)

 

 

▶ 정답이다!! 그런데 중간중간 시간이 많이 소요되는 테스트 케이스가 있다. 시간 소요를 단축시켜보기 위해 몇 가지 시도를 해본다. left_set에 값을 넣는 방식을 right_set 처럼 값을 넣기 위해 for문을 분리한다. for문을 두 개 사용하는게 걸리긴 하지만 topping배열에서 특정 값을 찾아서 넣는 것이 더 오래걸릴 수도 있다고 생각되어 시도해본다.

def solution(topping):
    right_num, left_num = [], []
    right_set, left_set = set(), set()

    for top in topping:
        right_set.add(top)
        right_num.append(len(right_set))

    for top in topping[::-1]:
        left_set.add(top)
        left_num.append(len(left_set))

    len_left = len(left_num)
    answer = [i for i in range(len(right_num) - 1) if right_num[i] == left_num[len_left - i - 2]]

    return len(answer)

 

▶ 답을 성공이고, 시간 소요는 후반부 테스트 케이스에 대해서 많이 줄어들었다. 배열에서 특정 값을 찾는 것보다 for문이 시간이 덜 소요된다는 것을 알게 되었다.

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.