Lv2. 롤케이크 자르기

문제 보기 :  롤케이크 자르기

프로그래머스

 

---

문제

• 정답률 : 60%

---

작성 코드

def solution(topping):
    answer = 0
    me = {}
    for i in range(len(topping)):
        me[topping[i]] = 1
        me_eat = len(me)
        sis = len(set(topping[i+1:]))
        if me_eat == sis:
            answer += 1
    return answer

처음에는 아 너무 쉽지! 하면서 바로 써내려갔는데 으응.. 바로 시간초과가 나버렸다.

10점 실화냐!!!! 20문제 중에 2개 통과...

def solution(topping):
    answer = 0
    tall = { }
    for i in (topping):
        if i in tall:
            tall[i]+=1
        else:
            tall[i] = 1
            
    me = [] ; me_eat = 0; i = 0 ; sis = len(tall)

    while me_eat <= sis:
        tall[topping[i]] -= 1
        if tall[topping[i]] == 0:
            del tall[topping[i]]
        
        if topping[i] not in me:
            me.append(topping[i])
            me_eat += 1
            
        sis = len(tall)
        if me_eat == sis:
            answer += 1
        if me_eat > sis:
            break
        i += 1
    return answer

2차 시도에서는 딕셔너리로 먼저 토핑 종류별로 갯수를 쫙 깔아놓고 하나씩 삭제하는 걸로 수정했다.

그리고 동생이 먹는 tall 속 토핑 수가 내가 먹는 토핑 수 보다 많아지면  while문을 종료한다.

이 코드는 전보다 나아지긴 했지만 20개 중 15개 통과....

def solution(topping):
    answer = 0
    tall = { }
    for i in (topping):
        if i in tall:
            tall[i]+=1
        else:
            tall[i] = 1
            
    me = {} ; me_eat = 0; i = 0 ; sis = len(tall)

    while me_eat <= sis:
        tall[topping[i]] -= 1
        if tall[topping[i]] == 0:
            # del tall[topping[i]]
            sis -= 1
        
        if topping[i] not in me:
            me[topping[i]] = 1
            me_eat += 1
            
        # sis = len(tall)
        if me_eat == sis:
            answer += 1
        if me_eat > sis:
            break
        i += 1
    return answer

me를 리스트가 아닌 딕셔너리로 수정하고, tall[topping[i]]==0일 때도 topping[i]를 지우지 말고 단순히 sis -= 1로 간단화했다.

문제에서 키포인트는 리스트나 셋처럼 딕셔너리보다 비교적 무거운 자료를 이용하지 않는다는 것이다.

그리고 sis = len(tall)처럼 다시 계산하는 방식이 아니라, sis -=1 처럼 단순히 1을 빼는 방식으로 시간을 줄이는 것이 키 포인트로 보인다.