[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 1253번 _ 좋다

https://www.acmicpc.net/problem/1253

1253번: 좋다

[문제]

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

[입력]

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

[출력]

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

[아이디어]

1) 단순 이중 포문은 시간초과가 날거라 생각했는데, N이 최대 2000에 제한시간이 2초라 그런지 그냥 통과되는 코드가 보였다.

2) 투포인터를 이용해야 더 효율적인 코드가 짜진다고 생각했는데.. 결과적으로 아니었다. 각 위치에 있는 수들을 일일히 확인하는게 아니라 특정 수가 몇 개 있는지로부터, 자기 자신을 활용하지 않고 좋은 수를 만들 수 있는지 여부를 확인할 수 있다.

3) 질문 게시판에 문제제기가 있는 것처럼, 자기 자신을 좋은 수 연산에 활용할 수 없다는 표현이 문제에는 모호하게 되어있다. 어떤 수가 '다른 수' 두 개의 합으로 나타내져야 한다. 0 0의 입력의 경우 자기 자신을 활용하지 않고 0을 만드는 경우는 없으므로 출력이 0이고, 0 0 0의 입력의 경우 각 수가 자기 자신을 제외한 나머지 두 개 0의 합으로 0을 만들 수 있어 출력이 3이다.

4) 결국 3번의 구현을 얼마나 효율적으로 할 수 있는가가 핵심

 

n=int(input())
a = sorted(list(map(int,input().split())))
d = dict()
for k,x in enumerate(a):
    for i in range(n-1):
        j = i + 1
        if (a[i] + a[j] == x) and (i-k)*(j-k):
            d[k] = 1
            break
        while (a[i] + a[j] <= x) and j<n-1:
            j += 1
            if (a[i] + a[j] == x) and (i-k)*(j-k):
                d[k] = 1
                break
        if (a[i] + a[j] == x) and (i-k)*(j-k):
            d[k] = 1
            break
print(sum(d.values()))

나는 첫 접근 차제가 꼬여버려서,, 더러운 코드가 완성돼 버렸다. 하고자 했던 것은 i번째 숫자와 조합해 합으로 x를 만들 수 있는 최대의 수에 대해 i의 위치를 변경해가며 탐색하는 것이었는데, 이후 3의 문제 의미를 뒤늦게 파악하고 수정하느라 좋지 못한 방법이 되었다. Pypy3로 제출해야 통과.

input()
D={}
for i in map(int,input().split()):
    D[i] = D.get(i,0) + 1
T={}
for i in D:
    for j in D:
        if i==j and D[i]==1:continue
        if i+j not in D:continue
        if D[i+j]<=(i==0)+(j==0):continue
        T[i+j]=D[i+j]
print(sum(T.values()))

이 방법이 가장 와닿아서 가져와봤다. 사전에 특정 숫자의 등장 횟수를 담아 관리하면, 그 횟수를 활용해 3의 경우의 수를 배제할 수 있다. 결국 자기 자신을 활용하는 경우는 더하는 수 혹은 자기 자신이 0인 경우 (X + 0 또는 0 + 0) 밖에 없는데, 이를 한 줄의 표현으로 구현한 것이 인상적이다. 간결한 코드가 아니라 이해하기 쉬운 코드,,,