프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 51분

def lower_bound(topping,start,end):
        
    while start<end:

        mid = (start+end)//2
        # print("--------------")
        # print("start :",start, "end : ",end,"mid : ",mid)

        old = len(set(topping[:mid]))
        young = len(set(topping[mid:]))

        if old>=young:
            end = mid
            
        elif old<young:
            start = mid+1
            
    return start

def upper_bound(topping,start,end):
    
    while start<end:

        mid = (start+end)//2
        # print("--------------")
        # print("start :",start, "end : ",end,"mid : ",mid)

        old = len(set(topping[:mid]))
        young = len(set(topping[mid:]))

        if old<=young:
            start = mid+1
            
        elif old>young:
            end = mid
            
    return end

def solution(topping):
    answer = 0
    
    start = 0
    end = len(topping)
    
    left = lower_bound(topping,start,end)
    right = upper_bound(topping,start,end)
    
    answer = right-left
    return answer

롤케이크에 일렬로 배치되는 종류별 토핑들(topping)이 주어지고 이를 반으로 잘랐을 때, 두 조각의 토핑 종류가 같을 경우의 수를 구하는 문제입니다.🐕🐕🐕

일차원 배열에서의 탐색 문제로 바로 이진 탐색을 활용한 방식을 떠올렸습니다.

이때 일반적으로 start~end 사이의 mid 값을 구하는 것이 아닌 lower bound, upper bound를 구해야하는 문제인데 이를 오랜만에 구현하다보니 약간 시간이 걸렸습니다.

[다른 사람의 풀이1]

from collections import Counter

def solution(topping):
    
    answer = 0
    dic = Counter(topping)
    set_dic = set()
    answer = 0

    for i in topping:
        dic[i] -= 1
        set_dic.add(i)
        if dic[i] == 0:
            dic.pop(i)
        if len(dic) == len(set_dic):
            answer += 1

    return answer

이분 탐색 대신 요소별 갯수를 구하는 Counter와 set() 구조를 활용하여 구현한 풀이입니다.🐣🐣🐣

토핑 종류별 갯수(dic)을 선언하고 topping 배열을 순서대로 돌며 앞에서 부터 한개의 토핑씩 추가함과 동시에 앞쪽의 토핑 종류수(set_dic)과 뒷쪽의 토핑 종류수(dic)을 비교하며 경우의 수를 구한 방식입니다.

괜찮은 아이디어로 접근한 풀이로 인상깊었습니다.

[다른 사람의 풀이2]

def solution(topping):
    answer = 0
    # 철수 케이크
    bro1 = {}
    for t in topping:
        if t in bro1:
            bro1[t] += 1
        else:
            bro1[t] = 1

    #동생 케이크
    bro2 = {}
    for t in topping:
        # 둘의 딕셔너리 크기가 같다면 동일한 크기로 나눈거
        if len(bro2) == len(bro1):
            answer += 1
        # 동생 케이크에 해당 토핑이 없다면 토핑 추가
        if t not in bro2:
            bro2[t] = 1
        
        # 철수 토핑에는 하나 빼주기
        bro1[t] -= 1
        # 만약 철수가 해당 토핑을 아예 가지고 있지 않다면 제거
        if bro1[t] == 0:
            del bro1[t]
        
    return answer

'다른 사람의 풀이1'과 같이 토핑 종류별 갯수를 정의하고 topping 리스트에 대해 for문을 돌린 구조이되 접근 방법이 달랐습니다.🐇🐇🐇

철수(bro1)가 모든 토핑을 가지고 있다고 가정하고 순서대로 철수의 토핑을 동생에게 한개씩 주며 비교하여 계산한 관점이였습니다.

감사합니다.