[백준/투 포인터] 1940번 : 주몽

- 문제 : https://www.acmicpc.net/problem/1940

 

 

정답 풀이 - 딕셔너리

배열에 주어진 수들 중에 두 원소의 합이 m인 경우의 수를 출력하는 문제다.

 

투 포인터 문제라고는 하는데, 투 포인터로는 어떻게 풀어야할지 생각이 안나서 딕셔너리로 {숫자 : 개수} 형태로 풀었다. 배열의 수와 m은 고정된 수이기 때문에 나머지 다른 값이 arr에 존재하는 경우만 세면 된다고 생각해서 그렇게 어렵지는 않았지만, 케이스 생각하느라 약간 헤맸다.

 

풀이 과정

1. 주어진 배열에 대해서 숫자의 개수를 numbers 딕셔너리{숫자 : 개수}에 저장한다. (Counter 라이브러리를 사용해도 된다)

 

2. arr[i] + target = m 이 되는 target(target = m - arr[i])의 존재여부에 따라 numbers[key]의 value를 하나씩 뺀다(중복 케이스 를 피하기 위함). 

이때 arr[i] == target인 경우와 arr[i] != target인 경우로 나누어서 진행해야 한다. 

 

    2-1. arr[i] == target 일 때, numbers[arr[i]] >= 2 이어야 하기 때문에 이것도 체크해줘야 한다. 왜냐하면 중복 케이스 제거를 위해 numbers[arr[i]]의 값을 하나씩 줄일텐데 이 경우에는 같은 숫자가 2개이므로 2를 감소시켜야 하기 때문이다. 

if arr[i] == target and numbers[target] >= 2:

 

    2-2. arr[i] != target 일 때, 먼저 target이 numbers 키에 존재해야하고 그 다음에 중복 케이스 제거를 위해 value를 -1 할 텐데, 이게 음수가 되면 안되기 때문에 numbers[target] > 0 이어야 한다. 

if arr[i] != target and target in numbers and numbers[target] > 0:

 

3. 2-1과 2-2에 해당하는 경우가 정답 케이스이므로, 각 케이스마다 answer += 1을 한다.

 

4. 그동안 센 정답 케이스인 answer를 출력한다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())

answer = 0
arr = sorted(list(map(int, input().split())))
numbers = {}
for i in range(n):
    if arr[i] in numbers:
        numbers[arr[i]] += 1
    else:
        numbers[arr[i]] = 1
    
for i in range(n):
    target = m - arr[i]
    if arr[i] == target and numbers[target] >= 2:
        numbers[target] -= 1
        numbers[arr[i]] -= 1
        answer += 1
    if arr[i] != target and target in numbers and numbers[target] > 0:
        numbers[target] -= 1
        numbers[arr[i]] -= 1
        answer += 1
  
print(answer)

 

 

정답 풀이 - 투 포인터 

투 포인터 문제이니 해당 풀이도 찾았는데, 로직이 이진 탐색과 비슷하다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
nums = list(map(int,input().split()))

nums.sort()
left, right = 0, len(nums) - 1
count = 0

while left < right:
    sum_num = nums[left] + nums[right]
    if sum_num < m:
        left += 1
    elif sum_num > m:
        right -= 1
    else:
        count += 1
        left += 1
        right -= 1

print(count)

 

 

Reference

투 포인터 풀이 블로그 : https://jminie.tistory.com/108