백준 1253번: 좋다 [python]

난이도 : 골드 4
유형 : 투포인터
https://www.acmicpc.net/problem/1253

문제 접근

N개의 수를 입력받고
그 중 어떤 수가 서로 다른 수 두 개의 합으로 나타낼 수 있다면, 그 개수를 출력하는 문제.

1,2,3,4,5,6,7,8,9,10 의 경우
1과 2는 서로다른 두 수의 합으로 나타낼 수 없기에 제외되고 나머지가 가능하기에 8이 출력된다.

숫자 1,2 빼고는 모든 숫자가 서로 다른 두 수의 합으로 나타낼 수 있잖아? 라고 생각하고 문제를 다시 봤더니 입력받은 배열 안에 수로 그 수를 표현할 수 있어야 한다.

즉
[1,2,3,6] 배열이라면 답은 1이 된다.
6의 경우 1+5나 2+4 가 필요하지만 4,5가 없기 때문에 카운팅이 안된다.

그래서 [1,2,3,4,5] 배열이 주어졌고 만약 요소 4이 가능한지 볼려면,
0번째 인덱스를 left
요소 4보다 바로 이전 인덱스를 right 로 놓고,
4와의 크기를 비교해가며 가능한지 while문을 돌면 되겠다.

풀이 및 오답

import sys

input = sys.stdin.readline

N = int(input())
N_nums = list(map(int,input().split()))
N_nums.sort() 

answer = 0 

for i in range(N):  # 요소의 수만큼 반복할거야. 
    target = N_nums[i] # 목표 숫자는 i번째의 요소 값
    left = 0 # 맨 왼쪽
    right = i - 1 # 자기 자신보다 왼쪽까지만 본다
    
    while left < right:
        total = N_nums[left] + N_nums[right]

        if total == target:
            answer += 1 
            break
        
        elif total < target:
            left += 1

        else:
            right -= 1
    
print(answer)

로 풀었는데 틀렸다고 나온다.

이유는 같은 값이라도 서로 다른 인덱스에 있으면 “서로 다른 수” 취급해야하는데 그러지 못하고 있다
ex) 1 2 2 2 3 넣으면 답이 3이 나와야하지만 1로 나온다.

그래서 자신의 요소보다 왼쪽만 보게 설정한 right = i-1을 하면 안되고 전체를 다 보아야 한다.

그리고 자기 자신은 인덱스로 제외해주면 된다.

해답 및 풀이

import sys

input = sys.stdin.readline

N = int(input())
N_nums = list(map(int, input().split()))
N_nums.sort()

answer = 0

for i in range(N):  # 요소의 수만큼 반복할거야. 
    target = N_nums[i]  # 목표 숫자는 i번째의 요소 값
    left = 0
    right = N - 1  # 전체 범위에서 투 포인터 시작

    while left < right:
        if left == i:  # 자기 자신은 제외
            left += 1
            continue
        if right == i:
            right -= 1
            continue

        total = N_nums[left] + N_nums[right]

        if total == target:
            answer += 1
            break  # 한 번이라도 가능하면 그 숫자는 좋은 수

        elif total < target:
            left += 1
        else:
            right -= 1

print(answer)