백준 1253 좋다 Python

🐸 문제 정보

1253번: 좋다

 

🤖 알고리즘

투포인터

 

⏱️ 풀이 시간

25.15m

 

📝 풀이

오름차순으로 정렬했음에도 0번 인덱스부터, 그리고 해당 인덱스를 제외하고 투포인터를 진행해야한다는 것을 놓쳤다. 아마 정답률이 낮은 것도 나같은 사람이 많아서지 않을까 싶다.

1. 입력 숫자 리스트 오름차순 정렬
2. 0번 인덱스부터 끝까지 순회
3. 특정 인덱스에 해당하는 숫자를 제외하고, 투포인터를 이용해서 해당 숫자를 만들어 낼 수 있는지 검사
   • start는 0부터, end는 해당 숫자를 제외한 리스트의 마지막 인덱스부터
   • 만약 start + end가 해당 숫자보다 작다면 start를 한 칸 뒤로
   • 반대로 크다면 end를 한 칸 앞으로

처음에 틀렸던 코드는 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = sorted(list(map(int, input().rstrip().split())))
res = 0

def find_sum(target, arr):
    s, e = 0, len(arr) - 1
    while s < e:
        tmp = arr[s] + arr[e]
        if tmp == target:
            return True
        elif tmp < target:
            s += 1
        else:
            e -= 1
    return False

for i in range(2, n):
    if find_sum(nums[i], nums[:i]):
        res += 1

print(res)

 

그리고 왜 틀렸는지 알게해준 반례는

4
0 0 0 0

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = sorted(list(map(int, input().rstrip().split())))
res = 0

def find_sum(target, arr):
    s, e = 0, len(arr) - 1
    while s < e:
        tmp = arr[s] + arr[e]
        if tmp == target:
            return True
        elif tmp < target:
            s += 1
        else:
            e -= 1
    return False

for i in range(n):
    if find_sum(nums[i], nums[:i] + nums[i+1:]):
        res += 1

print(res)