[백준] 1940번 주몽 - Python(1편)

 이번 글에서 알고리즘 설계 방법 중 하나인 투 포인터 기법을 활용하여 문제를 해결했습니다.

이 알고리즘은 이중 반복문을 피하고 시간 복잡도를 O(N)으로 줄여 효율성을 크게 높이는 방식으로, 불필요한 연산을 제거하고 주어진 조건을 효과적으로 활용했습니다.

 

아래는 백준 문제입니다. 사진을 클릭하면 해당 문제 페이지로 넘어갑니다.

백준 1940번 주몽 문제. 사진을 클릭하면 해당 링크로 넘어갑니다.

 

이 문제의 전체 코드를 확인해 보고, 자세히 분석해 보도록 하겠습니다.

import sys
input = sys.stdin.readline

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

def partial_sum(data, M):
    left, right = 0, len(data) - 1
    count = 0 
    while left < right:
        current_sum = data[left] + data[right]
        if current_sum == M:
            count += 1
            left += 1
        elif current_sum < M:
            left += 1
        else:
            right -= 1
    return count

result = partial_sum(data, M)
print(result)

1. 입력 처리

   import sys
   input = sys.stdin.readline
   
   N = int(input())
   M = int(input())
   data = list(map(int, input().split()))

    
   • sys.stdin.readline로 input() 함수를 재정의합니다. 이는 빠른 입력 처리를 위해 사용됩니다.
   • N은 재료의 개수로 리스트의 길이를 나타냅니다.
   • M은 두 재료 고유 번호의 합으로 만들어야 하는 목푯 값입니다.
   • data는 재료들의 고유 번호를 담을 리스트입니다.
2. 데이터 정렬

   data.sort()

   • 주어진 data 리스트를 오름차순 정렬합니다.
   • 투 포인터 알고리즘은 정렬된 배열에서만 사용 가능하기에 필수적입니다.
   • sort() 함수는 Timsort() 알고리즘을 사용하므로 시간 복잡도가 O(n log n)입니다.
3. 함수 정의

   def partial_sum(data, M):
       left, right = 0, len(data) - 1
       count = 0

   • left는 배열의 첫 번째 요소를 가리킵니다.
   • right는 배열의 마지막 요소를 가리킵니다.
   • count는 조건을 만족하는 쌍이 생길 경우 1씩 증가할 것입니다.
4. 반복문

   while left < right:
       current_sum = data[left] + data[right]

   • while 반복문을 통해 두 포인터가 겹치기 전까지 반복합니다.
   • current_sum은 현재 선택된 두 숫자의 합입니다.
   • 이 과정은 배열을 한 번 순회하는 것이므로, 시간 복잡도는 O(N)입니다.
5. 조건 분기 및 결과 반환

   if current_sum == M:
       count += 1
       left += 1
   elif current_sum < M:
       left += 1
   else:
       right -= 1

   • 만약 두 수의 합이 목표 M과 같다면
     
     • count를 1 증가시킵니다.
     • 더 작은 값을 가리키는 포인터인 left 오른쪽으로 이동시킵니다.
       1. 이는 data의 값들이 고유한 번호이므로 같은 값을 다시 사용할 필요가 없으며, 더 큰 값을 시도해야 하기 때문입니다.
       2. right를 -1을 통해 왼쪽으로 이동시켜도 상관없습니다.
   • 만약 두 수의 합이 목표 M보다 작다면
     • 더 큰 값을 만들기 위해 작은 값을 가리키는 포인터를 오른쪽으로 이동합니다. left += 1.
   • 두 수의 합이 목표 값 M보다 크다면
     • 더 작은 값을 만들기 위해 큰 값을 가리키는 포인터를 왼쪽으로 이동합니다. right -= 1.
   • 모든 조건 확인 후 만족하는 쌍의 총 개수를 반환합니다.
6. 함수 호출 및 출력

   result = partial_sum(data, M)
   print(result)

   • 정의한 함수를 호출여 결과를 계산하고 출력합니다.
   • 전체 시간 복잡도는 정렬 단계에서 O(n log n), 투 포인터 반복문에서 O(N)이므로 O(n log n)입니다

 

---

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.