[ 자료구조-1253 ] 좋다(Python)

---

접근법

다른 두 수의 합으로 특정 수를 나타내는지를 확인하기 위해서는 특정 수 보다 작은 두 수를 선택해야 하기에 정렬이 필요하다. 또한, 이중 for문으로 직접 접근하기에는 두 수를 찾기 위한 while문이 추가적으로 필요하여 $O(n^3)$ 시간복잡도가 발생한다. 따라서 $nlogn$의 알고리즘이 필요하기에 quick sort에서 활용한 방식처럼 pointer를 이용하여 접근하였으며, 0과 자기자신이 더해져 다른 위치의 자기자신을 나타내는 예외사항을 처리하도록 노력하였다.

 

---

정답

import sys

N = int(input())

arr = list(map(int,sys.stdin.readline().split(" ")))
arr.sort()

cnt = 0

for i in range(N):
    tmp = arr[i]
    start = 0
    end = N-1
    while(start<end):
        if arr[start]+arr[end] ==tmp:
            if start == i:
                start += 1
            elif end == i:
                end -= 1
            else:
                cnt +=1
                break
        elif arr[start]+arr[end] > tmp:
            end -= 1
        else:
            start += 1
print(cnt)

 

배열의 처음과 끝의 index를 나타내는 start와 end를 선언하고 두 index가 엇갈리기 전까지 반복해서 진행한다.

이때, 자기자신과 0의 합으로 자기자신을 나타내는 예외사항을 처리하기 위해

        if arr[start]+arr[end] ==tmp:
            if start == i:
                start += 1
            elif end == i:
                end -= 1
            else:
                cnt +=1
                break

 

다음과 같이 두 수의 합이 tmp와 같을 때 i와 start,end를 비교하였고, 그 외의 경우는 특정 수가 서로다른 두 수에 의해 표현되는 상황이므로 cnt를 증가시키고 break문으로 탈출하였다.

        elif arr[start]+arr[end] > tmp:
            end -= 1
        else:
            start += 1

 

같지 않을 경우 두 수의 합이 더 크면 end의 index를 줄여 더 작은 값을, 더 작으면 start의 index를 증가시켜 더 큰 값으로 이동하여 표현 가능한지 확인한다.