[Algorithm] 백준 #1940 주몽 #30804 과일탕후루 (with python)

투포인터 알고리즘을 사용하는 2문제를 풀어보았습니다~!

🏹1940 주몽

이 문제의 핵심은 input 받은 재료의 번호들을 sort 해 주는 것이었습니다!

N = int(input())
M = int(input())
numbers = list(map(int, input().split()))


def count_amor(N, M, numbers):
    numbers.sort()
    count = 0
    current_sum = 0
    start = 0
    end = len(numbers) -1

    while start < end:
        current_sum = numbers[start] + numbers[end]
        if current_sum == M:
            count += 1
            start += 1
            end -= 1 
        elif current_sum < M:
            start += 1
        else:
            end -= 1
    return count

result = count_amor(N, M, numbers)
print(result)

---

🍡30804 과일탕후루

주몽 문제보다는 난이도가 조금 더 높은 문제 입니다..
약간의 사고가 더 필요했는데요!!

1. 과일 종류가 2개를 초과하면, start 포인터를 오른쪽으로 이동시켜 구간을 조정한다.
2. 현재 유효한 구간의 길이와 지금까지의 최대 길이를 비교하여 갱신해준다.

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

def max_count_fruit(N, fruits):
    count_fruit = {}
    start = 0
    max_count = 0
    kinds_fruit = 0

    for end in range(N):
        if fruits[end] not in count_fruit:
            count_fruit[fruits[end]] = 0
            kinds_fruit += 1
        count_fruit[fruits[end]] += 1

        while kinds_fruit > 2:
            count_fruit[fruits[start]] -= 1
            if count_fruit[fruits[start]] == 0:
                kinds_fruit -= 1
                del count_fruit[fruits[start]]
            start += 1

        max_count = max(max_count, end - start + 1)

    return max_count

print(max_count_fruit(N, fruits))

알고리즘 문제들을 풀 때 문제를 해결해내는 시간보다 문제를 이해하는데 소요되는 시간이 더 긴 건 저 뿐일까요..?

문제를 많이 읽고 해석하는 연습도 필요할 것 같습니다.. 정말 갈 길이 멀다^^

글로벌소프트웨어캠퍼스와 교보DTS가 함께 진행하는 챌린지입니다.
#내맘대로TIL챌린지 #교보DTS #클라우드교육 #글로벌소프트웨어캠퍼스 #GSC신촌