[연습문제 / 프로그래머스] 132265번 : 롤케이크 자르기

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

 

Lv2 문제다!

순차적으로 topping을 탐색하면서 특정 위치를 기준으로 왼쪽과 왼쪽의 원소 종류가 같은 경우의 수를 찾는 문제다

topping의 길이가 최대 100만이어서 시간 복잡도를 무조건 생각하고 코드를 작성해햐 했는데, 단순 구현 말고는 생각이 안 나서 

구글링 했다 

 

찾아보니 그렇게 어려운 문제가 아니었다. 시간 복잡도를 생각하면 dictionary를 이용해야 할 것 같기는 했는데,

왼쪽에 있는 수들은 종류만 따지면 되므로 set으로 처리하고 add만 하면 되고

오른쪽에 있는 수들은 각 갯수를 고려해야하므로 dictionary를 이용한다. 

반성하자!

 

풀이 로직

• 기존의 topping을 Counter로 각 숫자의 갯수를 딕셔너리로 만든다.
• set_dic은 split 했을 때 왼쪽에 해당하는 숫자를 담은 set이고, dic은 그 나머지 숫자에 대한 갯수를 담고 있다 
• 탐색을 진행하면서 만나는 원소를 set_dic에 넣고, dic에서는 해당 숫자의 갯수를 -1 한다
  • 이때 dic에서 해당 숫자가 더이상 남지 않은 경우(갯수가 0인 경우) 해당 키를 dic에서 pop한다 
• 만약 두 딕셔너리의 원소 갯수가 같다면 res += 1 한다
• res를 반환한다 

 

 - 정답 풀이 :

 

참고한 블로그

 

from collections import Counter

def solution(topping):
    dic = Counter(topping)
    set_dic = set()
    res = 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):
            res += 1
    return res

 

- 시간초과 풀이 :

 

• topping의 왼쪽부터 하나씩 이동하면서 오른쪽 배열 set2에서 0 인덱스 값을 pop한 뒤
• 왼쪽의 set1에 원소를 추가한다.
• set1의 원소 종류 갯수와 set2의 원소 종류 갯수가 동일하다면 answer += 1을 해준다 

 

def solution(topping):
    
    answer = 0
    set1, set2 = set([topping[0]]), topping[1:]
    
    for i in range(1, len(topping)):
        if len(set1) == len(set(set2)):
            answer += 1
        set1.add(topping[i])
        set2.pop(0)
        
    return answer