프로그래머스 / 해시 / 롤케이크 자르기

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

문제에서 단순히 2개로 나누어서 종류만 따져봤을 때 갯수가 동일하면 된다고 나와있다.

 

같은 종류는 동일한 갯수로 세기 때문에 맵을 이용한 풀이가 깔끔하다고 생각했다.

 

배열이 주어졌을 때 정확히 2등분을 해야 되기 때문에 다음과 같이 자를 수 있다.

 

0 | 1..N - 1

0..1 | 2..N - 1

...

0..N-2 | N - 1

 

이렇게 자를 수 있으니 각 자른 배열에 들어가 있는 종류만 비교하면 된다.

 

이것을 구현하기 위해 map을 떠올렸고 다음과 같은 로직을 생각했다.

1. front, back을 나누어서 map을 선언한다.

2. back에 모든 토핑을 일단 넣는다.

3. front에 하나씩 토핑을 추가하면서 back에서는 front에 넣은 것들을 하나씩 빼준다.

4. len(front) 와 len(back)을 했을 시 동일하다면 현재 front와 back에 들어가 있는 종류가 같은 것으로 answer를 증가한다.

 

 

정답코드

---

'''
'25. 09. 21.(일)

1. 2조각으로만 나눠야 한다.
2. 결국에는 종류에만 관점을 둔다.
3. dict을 이용해서 갯수로 len == len을 하면 될 것 같다.


'''
def solution(topping):
    answer = 0
    front = {}
    back = {}
    for value in topping:
        back[value] = back.get(value, 0) + 1
        
    #하나씩 빼서 절반씩 한 것처럼 보이게 하기
    for value in topping:
        front[value] = front.get(value, 0) + 1
        
        back[value] -= 1#갯수 하나씩 줄이기
        if back[value] == 0:
            del back[value]#key 값 없애기
        
        #현재 갖고 있는 종류가 같으므로 괜찮음
        if len(front) == len(back):
            answer += 1
    return answer

 

깃허브 : https://buly.kr/ja2AZJ

유튜브 : https://youtu.be/pqN1uMLHb2Q