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

링크

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

프로그래머스

문제 설명

(자세한 내용은 링크에 있는 문제를 참고하세요. 저는 풀이에 필요한 설명만 다룹니다.)

아래와 같은 문자열이 주어진다고 가정하자.

[1, 2, 1, 3, 1, 4, 1, 2]

만약 절반을 자른다면 배열은 다음과 같이 두 배열로 나올 것이다.

a = [1, 2, 1, 3]

b = [1, 4, 1, 2]

a배열에 서로 다른 숫자는 1, 2, 3로 3개이며,

b배열에 서로 다른 숫자는 1, 2, 4로 3개이다

이렇게 각각의 배열에 서로 다른 숫자가 동일하다면 정답의 개수가 늘어나는 것이고,

처음 주어진 배열 기준 연속된 문자열로 잘랐을 때 최종적인 정답의 개수를 묻는 문제이다.

해법

맨 처음 주어진 배열에 첫번째 딕셔너리에 넣고, 나머지 값들을 다른 딕셔너리에 넣는다. 참고로 딕셔너리의 value는 값의 개수다

arr = [1, 2, 1, 3, 1, 4, 1, 2]를 처음 주어진 배열로 가정하자면,

a 딕셔너리는 초기에 a[1] = 1의 값을 가지고 있으며,

b 딕셔너리에 들어갈 key들은 [2, 1, 3, 1, 4, 1, 2]니까 1이 3개, 2가 2개, 3이 1개, 4가 1개이므로,

b 딕셔너리의 초기값은 {1: 3, 2: 2, 3: 1, 4: 1} 이다.

코드로 나타내면 다음과 같다.

a = dict()
    b = dict()
    a[topping[0]] = 1
    for i in range(1, len(topping)):
        if topping[i] not in b:
            b[topping[i]] = 1
        else:
            b[topping[i]] += 1

 

그다음에 arr 배열을 2번째(인덱스로는 1)부터 끝까지 순회하면서

현재 인덱스인 i를 a딕셔너리에는 더하고, b딕셔너리에는 뺀다.

그다음 a배열과 b배열의 크기가 같다면 정답의 개수를 1 늘린다.

이를 코드로 확인해보는게 더 이해하기 쉬울 것 같다.

for i in range(1, len(topping) - 1):
        if topping[i] not in a:
            a[topping[i]] = 1
        else:
            a[topping[i]] += 1

        b[topping[i]] -= 1
        if b[topping[i]] == 0:
            b.pop(topping[i])

        if len(a) == len(b):
            answer += 1

 

좀 더 정리하여 아래 문제 풀이 순서에서 확인해보면 좋을 것 같다.

문제 풀이 순서

1. 초기 주어진 배열을 2개의 딕셔너리로 분배한다.

 a : 첫번째 인덱스

 b : 두번째~마지막 인덱스

2. 배열 2번째 값부터 마지막 인덱스까지 다음의 작업을 반복한다.

 2-1. a 딕셔너리에 현재 값 추가

 2-2. b 딕셔너리에 현재 값 뺴기

 2-3. a와 b의 전체 길이를 비교해 같다면 answer++

3. answer 반환

전체 코드

def solution(topping):
    answer = 0
    a = dict()
    b = dict()
    
    # a와 b 딕셔너리 초기화
    a[topping[0]] = 1
    for i in range(1, len(topping)):
        if topping[i] not in b:
            b[topping[i]] = 1
        else:
            b[topping[i]] += 1

	# 배열을 순회하면서 현재 값을 a에서는 더하고 b에서는 빼기
    if len(a) == len(b):
        answer += 1
    for i in range(1, len(topping) - 1):
        if topping[i] not in a:
            a[topping[i]] = 1
        else:
            a[topping[i]] += 1

        b[topping[i]] -= 1
        if b[topping[i]] == 0:
            b.pop(topping[i])

        if len(a) == len(b):
            answer += 1

    return answer