1/29 Coding Test

✅ Coding Test

🎈 1253 좋다

n개의 수 중에서 어떤 수가 다른 수 2개의 합으로 나타낼 수 있다면 그 수를 GOOD이라고 한다.
N개의 수가 주어지고 그 중에서 좋은 수의 개수는 몇개 인지 출력하는 문제.
수의 위치가 다르면 값이 같아도 다른 수이다.

import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int, input().split()))
li.sort()

answer = 0
for i in range(n):
    start, end = 0, len(li)-2
    tmp = li[:i] + li[i + 1:]
    while start < end:
        target = tmp[start] + tmp[end]
        if target == li[i]:
            answer += 1
            break
        elif target > li[i]:
            end -= 1
        elif target < li[i]:
            start += 1
print(answer)

< 해설 >

중요한 것은 2가지다.
계산 시 자기 자신을 빼고 계산해줄 것.
n-loop를 돌며 모든 조건 계산할 것.
이 2가지 과정을 기반으로 한 로직은 다음과 같다.
1. 입력값들을 전부 저장하고 정렬한다.
2. n-loop를 돌며 start, end와 해당 숫자를 제외한 n개의 리스트를 만들어 준다. (end의 경우 자기자신을 빼고 계산해야 하므로 리스트 끝 인덱스 - 1을 해주어야 하기에 n-2 처리)
3. binary-search를 진행하며 찾아야 하는 li[i]와 같으면 break를 걸고, 만일 li[i]보다 값이 크다면 end를 줄이고, 반대의 경우엔 start를 늘려준다.