[프로그래머스] 롤케이크 자르기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 롤케이크를 잘랐을 때, 두 조각의 토핑의 종류 개수가 동일한지 판단해야 하는 문제이다.

인덱싱을 사용하여 계속적으로 슬라이싱 한 결과를 set로 바꾸어 토핑 종료의 개수를 판단해 보았지만 시간초과를 해결할 수 없었다.

하여 한 번에 set로 저장하는 방법을 생각해 보았다.

한 명은 처음에 케이크의 전체를 가지고 시작하며 나머지 한 명에게 하나씩 토핑을 주며 두 케이크의 조각 위 토핑의 종류 개수를 비교하고 일치하는 개수를 세어주는 방식으로 시간초과를 해결하였다.

 

1. 한 명이 가지고 있는 토핑의 종류별 개수를 저장해 줄 딕셔너리를 생성한다. person1 = {}
2. 모든 토핑을 하나씩 불러오며 for i in topping
3. 이미 저장되어 있는 토핑이라면 개수만 증가해 주고 if (i in person1): person1[i] += 1
4. 반면에 처음 나온 토핑이라면 새로 저장한다. else: person1[i] = 1
5. 나머지 한 명이 가지고 있는 토핑의 종류를 저장해 줄 세트를 생성한다. person2 = set()
6. 다시 한번 모든 토핑을 하나씩 불러오며 for i in topping
7. 첫 번째 사람에서는 해당 토핑의 개수를 빼준다. person1[i] -= 1
8. 만약 빼준 뒤, 해당 토핑의 개수가 없으면 해당 토핑 종류를 제거해 준다. if (person1[i] == 0): del person1[i]
9. 두 번째 사람에는 해당 토핑의 종류를 더해준다. person2.add(i)
10. 만약 두 사람이 가지고 있는 토핑의 종류 개수가 동일하면 if (len(person1) == len(person2))
11. 일치하는 횟수를 증가시켜 준다. answer += 1

반응형

3. 소스코드

def solution(topping):
    answer = 0

    person1 = {}
    for i in topping:
        if (i in person1):
            person1[i] += 1
        else:
            person1[i] = 1

    person2 = set()

    for i in topping:
        person1[i] -= 1
        if (person1[i] == 0):
            del person1[i]
        person2.add(i)

        if (len(person1) == len(person2)):
            answer += 1

    return answer