백준 30804 과일탕후루 실버2 (투포인터, defaultdict)

문제 설명

• N개의 과일이 꽂혀 있는 과일 탕후루
• 과일은 1번부터 9번까지 번호가 있음
• 한 꼬치에 과일을 두 종류 이하로 사용해야함
• 앞에서 a개 뒤에서 b개를 빼서 N-(a+b)의 최댓값은?

입력값

1. N (1<=N<=200,000)
2. 탕후루에 꽂힌 N개의 과일 번호

출력값

• 과일의 개수가 가장 많은 탕후루의 과일 개수

 

 

처음 생각한 풀이 코드

# 반례발견! 오답
# 반례 : 1 1 3 7 8 9 9 9

import sys
sys.stdin = open('백준/test.txt')

# 앞에서 제거
def front(lst) :
    lst.pop(0)
    return lst

# 뒤에서 제거
def back(lst) :
    lst.pop()
    return lst


N = int(input())
tang = list(map(int,input().split()))



# 탕후루 과일 종류 개수 확인
set_tang = set(tang)

# 과일 종류 개수가 2개 이하일 때 종료
while len(set_tang) > 2 :
    if tang[0]  == tang[1] :        # 0번과 1번이 같으면 뒤에서 빼기
        back(tang)
        # print('back',tang)
    else :
        front(tang)
        # print('front',tang)

    set_tang = set(tang)

print(len(tang))

 

• 과일 종류가 2개 이하가 될 때까지 앞, 뒤에거 제거
• 앞의 2개가 같으면 뒤에거 제거하는 방식
• 뒤에거가 3개 연달아 같은게 있을 경우 앞을 제거하는게 더 이득 =>반례

 

 

정답 코드 : 투포인터 방법 사용

# 36952KB, 180ms(Python3)
# 투포인트 방법

from collections import defaultdict     # 딕셔너리 기본값 관리


N = int(input())
tang = list(map(int,input().split()))

def max_fruit_length(tang) :
    l, r = 0,0
    max_length = 0
    fruit_type = defaultdict(int)


    while r < len(tang) :
        fruit_type[tang[r]] += 1    # 현재 과일 추가

        while len(fruit_type) > 2 :
            fruit_type[tang[l]] -= 1		# 과일 하나 제거
            if fruit_type[tang[l]] == 0 :	# 과일이 0이면 과일 종류 리스트에서 제거
                del fruit_type[tang[l]]
            l += 1


        max_length = max(max_length, r-l+1)
        r += 1

    return max_length


ans = max_fruit_length(tang)
print(ans)

 

 

• 위와 같이 과일 번호를 저장하는 딕셔너리를 만들고, L,R(투포인터)를 두고 구간을 조정하며 최대 길이를 구하는 방법
• 즉, 과일의 종류가 2개인 최대 구간을 구하는 방법

 

 

 

예시 2

10
1 2 3 2 2 1 3 1 2 1

 

 

• 이런식으로 최대 길이를 찾을 수 있음

 

 

 

줄마다 주석으로 설명한 코드

from collections import defaultdict  # 딕셔너리 기본값 관리

# 입력 받기
sys.stdin = open('백준/test.txt')  # 테스트를 위해 입력 파일 사용
N = int(input())  # 과일 개수
tang = list(map(int, input().split()))  # 과일 종류 리스트

# 투 포인터를 사용한 최대 구간 길이 계산 함수
def max_fruit_length(tang):
    left, right = 0, 0  # 두 포인터 초기화: 구간의 시작(left), 끝(right)
    fruit_count = defaultdict(int)  # 현재 구간에 포함된 과일 개수를 저장
    max_length = 0  # 최대 구간 길이를 저장할 변수

    # 오른쪽 포인터를 한 칸씩 이동하며 탐색 시작
    while right < len(tang):
        fruit_count[tang[right]] += 1  # 현재 과일을 추가 (right 포인터가 가리키는 과일)

        # 과일 종류가 2개를 초과하면, left 포인터를 이동시켜 구간 줄이기
        while len(fruit_count) > 2:
            fruit_count[tang[left]] -= 1  # left 포인터가 가리키는 과일 개수 감소
            if fruit_count[tang[left]] == 0:
                del fruit_count[tang[left]]  # 개수가 0이 되면 딕셔너리에서 제거
            left += 1  # 구간의 시작점 이동

        # 현재 구간 길이를 계산하고 최대값 갱신
        max_length = max(max_length, right - left + 1)
        right += 1  # 구간의 끝점을 한 칸 늘림

    return max_length  # 최대 구간 길이 반환

# 결과 출력
print(max_fruit_length(tang))  # 구한 최대 구간 길이 출력

 

 

from collections import defaultdict

• 딕셔너리의 기본값을 자동으로 설정해주는 라이브러리
• 일반 딕셔너리는 키를 명시적으로 추가해야하지만(dict[key]=val)
• defaultdict는 키가 없을 경우 기본값을 자동으로 추가한다(키가 없는 상태에서도 dict[key] +=1 가능)
• defaultdict(기본값)
• int : 0 / list : [] / str : '' / lambda:42 : 42

# 일반 딕셔너리

d = {}
d['key']  # KeyError 발생!


# defaultdict

from collections import defaultdict

d = defaultdict(int)  # 기본값으로 0을 설정
print(d['key'])  # 0 출력 (KeyError 발생하지 않음)


# 예시
d = defaultdict(list)
d['key'].append(1)  # 'key'의 기본값이 []로 초기화되고 1 추가
print(d)  # {'key': [1]}

 

 

활용1 : 문자 빈도 계산

from collections import defaultdict

s = "hello world"
freq = defaultdict(int)

for char in s:
    freq[char] += 1

print(freq)  # {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

 

활용2 : 과일 종류별 개수 카운트

from collections import defaultdict

tang = [1, 2, 3, 2, 2, 1, 3, 1, 2, 1]
fruit_count = defaultdict(int)

for fruit in tang:
    fruit_count[fruit] += 1

print(fruit_count)  # {1: 4, 2: 4, 3: 2}