백준 3273 두 수의 합 파이썬

import sys
N = int(input())
nlist = list(map(int, sys.stdin.readline().split()))
X = int(input())

b = {}
for n in nlist:
    b[n] = False

a = []
cnt = 0
for n in nlist:
    if X - n == n:
        a.append(n)
        continue
    try:
        c = b[X-n]
    except KeyError:
        continue
    if c is False:
        b[X-n] = True
        b[n] = True
        cnt += 1
print(cnt)

💥 딕셔너리 활용하기 좋은 문제였다.

시도 1
처음에는 배열의 모든 값을 확인하는 코드를 사용했다. (list)

import sys
N = int(input())
nlist = list(map(int, sys.stdin.readline().split()))
X = int(input())
a = []
cnt = 0
for n in nlist:
    if X - n in nlist and n not in a:
        a.append(n)
        a.append(X-n)
        cnt += 1
print(cnt)

그러나 시간초과..!

왜냐하면 수열의 크기인 n의 범위가 1 ≤ n ≤ 100000 이기 때문이다.

시도 2 :
for 문에서 시간을 줄이기 위해 pypy3으로 제출했지만 이번에는 틀렸습니다. 가 출력되었다.

반례
input :
1
2
4

answer:
1

output:
0

시도 3 :
그래서 X == n * 2일 때의 조건도 고려해주었다.

import sys
N = int(input())
nlist = list(map(int, sys.stdin.readline().split()))
X = int(input())

a = []
cnt = 0
for n in nlist:
    if X == n * 2:
        a.append(n)
        continue
    if X - n in nlist and n not in a:
        a.append(n)
        a.append(X-n)
        cnt += 1
print(cnt)

하지만 역시 시간초과!

그렇다면 단순히 배열에 해당 원소가 있는지 확인하여 문제를 풀기 어려울 것이다.

그래서 딕셔너리를 활용하여 해당 원소가 있는지 더욱 빨리 확인할 수 있는 방법을 생각했다.

💡 인덱스로 접근하는 것은 O(1)이기 때문에 딕셔너리의 key 값으로 접근하는 방법이 어떨까 해서 코드를 작성했다.

import sys
N = int(input())
nlist = list(map(int, sys.stdin.readline().split()))
X = int(input())

b = {}
for n in nlist:
    b[n] = False

a = []
cnt = 0
for n in nlist:
    if X - n == n:
        a.append(n)
        continue
    try:
        c = b[X-n]
    except KeyError:
        continue
    if c is False:
        b[X-n] = True
        b[n] = True
        cnt += 1
print(cnt)

중간 과정이 생략되었지만 이 글을 쓰게된 이유는 딕셔너리 key error의 예외 처리 때문이다.

딕셔너리에 접근하는 key 값에 대한 value가 존재하지 않을 경우 key error가 발생하는데

이 에러를 해결하는 방법에는 두 가지가 있다.

1) if 문
: 딕셔너리 내에 key가 존재하는지 확인하는 방법

if key in dictionary

2) try - exception
: 에러가 발생하면 해당 에러를 처리하는 exception 문을 통해 처리하는 방법

try:
	a = dic[key]
exception KeyError:
	break

나는 2번 방법을 사용하였다.

1번 방법은 O(n)만큼의 시간복잡도이기 때문이다.

그래서 에러가 발생했을 때 바로 다음 반복을 실행하기 위해 예외 처리를 하는 방법을 사용했다.

참고
https://korbillgates.tistory.com/95