백준 1253 좋다 with Python

알고리즘

자료 구조
정렬
이분 탐색
해시를 사용한 집합과 맵
두 포인터

Tip

dictionary를 사용할 때 Python의 내장 자료구조인 defaultdict을 활용하면 코드를 더 간편하게 짤 수 있다.

nums = [1, 2, 3, 4, 5]

원래 코드: key가 존재하는지 확인 후 value 추가

num_combi = {} # key - 숫자, value - key를 만든 조합들 [(i, j)]

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        key = nums[i] + nums[j]
        if key in num_combi:
            num_combi[key].append((i, j))
        else:
            num_combi[key] = [(i, j)]

defaultdict 사용: dictionary의 기본값 설정

from collections import defaultdict

num_combi = defaultdict(list) # 기본값을 빈 리스트로 설정 (인자로 int를 넣으면 기본값이 0으로 설정된다)

for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        key = nums[i] + nums[j]
        num_combi[key].append((i, j))

풀이 과정

첫번째 시도

입력받은 모든 숫자의 조합을 set 자료구조에 넣은 다음 set에 들어있는 숫자의 개수를 구하면 되는 간단한 문제라고 생각했다.

N = int(input())

nums = list(map(int, input().split()))
s = set()

for i in range(N):
    for j in range(i + 1, N):
        s.add(nums[i] + nums[j]) # 모든 숫자의 조합을 set에 add

cnt = 0

for num in nums:
    if num in s:
        cnt += 1

print(cnt) # 정답 출력

하지만 문제에서 말하는 '좋은 수'의 조건은 다음과 같다.

어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 '좋다(GOOD)'고 한다.

만약 A와 B를 더했을 때 나온 결과 C가 A,B 둘 중 하나와 같다면 C는 '좋은 수'가 아니다.
입력으로 0이 들어온다면 위와 같은 예외가 발생할 수 있기 때문에 처음의 코드는 오답이었다.

두번째 시도

입력으로 들어온 0의 개수에 따라 case를 나눠서 푸는 방법을 생각했지만 결국 실패했다.

마지막 시도

갑자기 문득 좋은 풀이 방법이 생각이 나서 문제를 해결할 수 있었다.

첫번째 시도가 실패한 이유는, 입력받은 숫자가 set에 존재하는지에 대해서만 고려했기 때문이다.
하지만 숫자를 만든 두개의 원소와 입력받은 숫자가 서로 겹치진 않는지에 대해서도 고려해야 한다.

모든 숫자를 각각 한번씩 조합한 합계를 dictionary의 key로 설정하고, 조합한 원소 a,b를 튜플로 감싼 리스트를 value로 설정한다.
ex:

num_combi = {
    7: [(1,6), (0,7)], # 7을 만든 조합 (1,6), (0,7) -> 7은 1과 6의 조합으로 만들 수 있으므로 '좋은 수'이다.
    5: [(0,5)] # 5는 다른 두 숫자의 합으로 나타낼 수 없으므로 '좋은 수'가 아니다.
}

defaultdict을 선언한 다음 이중 for문으로 위의 dictionary를 만든다
다만 두 숫자의 합이 입력받은 숫자들 중의 최댓값을 초과하지 않는 값에 대해서만 작업을 수행한다. (최적화)

from collections import defaultdict

N = int(input())

nums = list(map(int, input().split()))
num_combi = defaultdict(list)

max_num = max(nums) # 입력받은 숫자들 중 최댓값

for i in range(N):
    for j in range(i + 1, N):
        if nums[i] + nums[j] <= max_num:  # 최적화
            num_combi[nums[i] + nums[j]].append((i, j))

입력받은 숫자들을 순회한다.
a. 두 숫자를 합해서 해당 숫자가 나오고
b. 조합 중에 해당 숫자가 포함되지 않은 조합이 하나라도 있다면 '좋은 수'이므로 count += 1

count = 0

for i in range(N):
    if len(num_combi[nums[i]]) == 0: # a.
        continue
    for combi in num_combi[nums[i]]: # b.
        if i not in combi:
            count += 1
            break

print(count) # 결과 출력

전체 코드

from collections import defaultdict

N = int(input())

nums = list(map(int, input().split()))
num_combi = defaultdict(list)

max_num = max(nums)

for i in range(N):
    for j in range(i + 1, N):
        if nums[i] + nums[j] <= max_num:
            num_combi[nums[i] + nums[j]].append((i, j))

count = 0

for i in range(N):
    if len(num_combi[nums[i]]) == 0:
        continue
    for combi in num_combi[nums[i]]:
        if i not in combi:
            count += 1
            break

print(count)

알고리즘 문제 풀이