[프로그래머스] 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=python3

프로그래머스

 

접근

---

• 포인터가 이동될 때마다(반복문을 수행하면서) 경계를 기준으로 왼쪽과 오른쪽에 속한 원소들의 종류와 각각에 대한 개수를 파악해야 한다. 즉, 종류와 각 종류에 대한 개수를 함께 저장할 수 있으며 종류의 삭제 또는 개수의 변경이 빠르게 진행될 수 있는 자료구조를 선택해야 한다.
  → 딕셔너리

 

로직

 

---

• topping A와 B 딕셔너리를 생성한다
  • key는 토핑 종류이며, value는 토핑 개수를 나타낸다
• toppingB에 전체 토핑에 대한 정보를 담는다
• topping에 대해 반복문을 수행하며, toppingB의 토핑을 A로 옮긴다
• toppingB에서 특정 토핑의 개수가 0이 되면, 해당 토핑에 대한 key와 value 쌍을 제거한다
• toppingA로 옮긴 후, 딕셔너리의 크기가 A와 B가 동일하다면 가능한 방법이므로, answer 값을 1 더한다

 

코드

---

1. Python 풀이

---

def solution(topping):
    
    topping_a = {}
    topping_b = {}
    for i in topping:
        if i not in topping_b:
            topping_b[i] = 0
        topping_b[i] += 1
    
    answer = 0
    for i in topping:
        if i not in topping_a:
            topping_a[i] = 0
        topping_a[i] += 1
        
        if topping_b[i] == 1:
            del topping_b[i]
        else:
            topping_b[i] -= 1
            
        if len(topping_a) == len(topping_b):
            answer += 1
        
    return answer

 

 

2. Swift 풀이

---

import Foundation

func solution(_ topping:[Int]) -> Int {
    
    var toppingA = [Int:Int]()
    var toppingB = [Int:Int]()
    
    for i in topping {
        if toppingB[i] == nil {
            toppingB[i] = 0
        }
        toppingB[i]! += 1
    }
    
    var answer = 0
    for i in topping {
        
        if toppingA[i] == nil {
            toppingA[i] = 0
        }
        toppingA[i]! += 1
        
        if toppingB[i] == 1 {
            toppingB.removeValue(forKey: i)
        }
        else {
            toppingB[i]! -= 1
        }
        
        if toppingA.count == toppingB.count {
            answer += 1
        }
    }
    
    return answer
}