python 1940 주몽

📌 문제 정보

• 문제 번호: 1940
• 문제: https://www.acmicpc.net/problem/1940
• 난이도: 실버 4

---

🧩 문제 요약

N개의 재료가 주어지고, 각 재료마다 고유한 번호(= 정수)가 있음.
M이라는 값이 주어졌을 때, 두 개의 서로 다른 재료 번호를 더해서 M이 되는 쌍의 개수를 구하는 문제.

---

🧪 예제 입력 / 출력

예제 입력

6 9 2 7 4 1 5 3

 

 

예제 출력

2

 

 

설명:

• 2 + 7 = 9
• 4 + 5 = 9
  => 총 2가지 쌍

---

💡 접근 방식

정렬된 리스트에서 두 수의 합이 특정 값을 만드는 쌍을 찾는 문제 → 투 포인터 알고리즘이 적절함.
리스트를 정렬한 뒤, 양쪽 끝에서 시작해서 합을 비교하며 포인터 이동.

---

⚙️ 알고리즘 설명

1. 입력값 N, M과 재료 리스트 입력
2. 리스트를 정렬함 (nums.sort())
3. 양 끝 포인터 i=0, j=N-1로 설정
4. 두 포인터가 가리키는 값의 합이 M보다 작으면 i 증가
5. 합이 크면 j 감소
6. 정확히 M이면 카운트 증가시키고 양쪽 포인터 모두 이동

이 방식은 중복 없이 정확히 한 번씩만 쌍을 셈.

---

🧑‍💻 코드 구현 (Python)

 

import sys

input = sys.stdin.readline

N = int(input())       # 재료의 개수
M = int(input())       # 갑옷을 만드는데 필요한 수
nums = list(map(int, input().split()))  # 재료 번호 리스트

nums.sort()  # 정렬

i = 0
j = N - 1
count = 0

while i < j:
    sum = nums[i] + nums[j]
    if sum < M:
        i += 1
    elif sum > M:
        j -= 1
    else:  # sum == M
        count += 1
        i += 1
        j -= 1

print(count)

---

🔁 다른 풀이 / 코드 개선 방향

• set()을 이용한 보완적 풀이 가능 (완전탐색 느낌으로)
• 하지만 이 문제는 입력값이 1만 이하이므로, 정렬 + 투 포인터 방식이 가장 효율적임
• 입력이 크면 collections.Counter를 활용하는 방식도 있음

---

⏱️ 시간복잡도 분석

• 시간 복잡도: O(N log N)
  • 정렬 O(N log N) + 투 포인터 O(N)
• 공간 복잡도: O(1) (추가 공간 없음)

---

📝 결론 및 팁

• 투 포인터는 정렬된 리스트 내에서 조건에 맞는 쌍을 찾는 데 매우 유용
• 중복되지 않도록 i < j 조건을 반드시 지킬 것
• 고정된 합을 만족하는 두 수 찾는 유형은 코테에서 자주 나옴

유사 문제 추천

• 3273번 두 수의 합: https://www.acmicpc.net/problem/3273
• 2003번 수들의 합 2: https://www.acmicpc.net/problem/2003