[BOJ/Python] 백준 1253번 - 좋다

백준 #1253 좋다

1253번: 좋다

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))

nums.sort()

def good_number(temp, k):
  left = 0
  right = n - 2
  while left < right:
    if temp[left] + temp[right] == k:
      return True
    elif temp[left] + temp[right] < k:
      left += 1
    else:
      right -= 1
  return False

cnt = 0
for i in range(n):
  if good_number(nums[:i]+nums[i+1:], nums[i]):
    cnt += 1

print(cnt)

 

수를 입력 받은 리스트(nums)를 오름차순 정렬하여 투포인터 방식으로 풀었다.

nums[left] + nums[right] < k 일 경우, left를 하나 올리고,

 

nums[left] + nums[right] > k 일 경우, right를 하나 내리는 방식이다.

만약 nums[left] + nums[right] == k 일 경우, True를 리턴하여 good number의 개수를 + 1 해준다. 

(left, right : 인덱스, k : good number인지 알아보려는 수)

 

이때 good number를 구하는 두 수에 good number는 포함되지 않도록 해야 하는데, 처음에 포함해서 구하는 로직을 짜서 오답이 나왔다. 그래서 good number는 두 수에 포함되지 않게 함수를 호출할 때 원본 리스트를 슬라이싱하여 good number를 제외한 리스트를 전달하도록 했다.