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

문제 링크

풀이

토핑의 종류에 따라 방문 체크를 한다.

앞에서 나오지 않았던 토핑의 종류였다면 앞에서 나온 종류의 개수를 +1 을 해준다.

앞에서 부터 체크를 해주고 뒤에서 부터 체크를 한번 더 해주고 arr[i] == arr2[i+1] 일경우 answer+1 을 해준다

 

제한사항

• 1 ≤ topping의 길이 ≤ 1,000,000
  • 1 ≤ topping의 원소 ≤ 10,000

 

정답 코드

def solution(topping):
    answer = 0
    visited = [0 for i in range(10001)]
    n = len(topping)
    arr = [0 for i in range(n)]
    arr2 = [0 for i in range(n)]
    cur_cnt = 0
    for i in range(n):
        if visited[topping[i]] == 0:
            cur_cnt+=1
            visited[topping[i]] = 1
            arr[i] = cur_cnt
        else:
            arr[i] = cur_cnt
    visited = [0 for i in range(10001)]
    cur_cnt = 0
    for i in range(n-1,-1,-1):
        if visited[topping[i]] == 0:
            cur_cnt+=1
            visited[topping[i]] = 1
            arr2[i] = cur_cnt
        else:
            arr2[i] = cur_cnt
    for i in range(n-2):
        if arr[i] == arr2[i+1]:
            answer+=1
    return answer

 

풀이 설명

visited 배열은 앞에서 해당 토핑의 종류가 나왔는지 체크하기 위한 배열

arr 배열은 케이크를 잘랐을때 왼쪽의 토핑 종류의 개수를 저장하기 위한 배열

arr2 배열은 케이크를 잘랐을때 오른쪽의 토핑 종류의 개수를 저장하기 위한 배열

앞에서부터 topping 배열을 순회하면서 방문체크가 되지 않은 토핑이 나왔을경우 해당 기준으로 잘랐을때 토핑의 종류에 +1 을 해준다.

뒤에서부터도 위와 같은 행동을 반복한다.

arr[i] == arr2[i+1] 일 경우에는 i,i+1 사이로 잘랐을때 오른쪽 왼쪽 토핑의 개수가 같음을 의미한다.

 

예외처리 고려사항

반례로 배열의 크기가 2일때 토핑원소 1,2 일경우에는 답이 0으로 나온다.

테스트 케이스에서는 이러한 테스트 케이스가 존재하지 않는것 같다...