[python] 백준 1253번 좋다

백준 1253번 좋다

https://www.acmicpc.net/problem/1253

문제

풀이

n = int(input())
nlist = sorted(list(map(int, input().split())))

def two_pointers(start, end, target, exclude_index):
    while start < end:
        if start == exclude_index:
            start += 1
            continue
        if end == exclude_index:
            end -= 1
            continue
        
        interval_sum = nlist[start] + nlist[end]
        if interval_sum == target:
            return True
        elif interval_sum < target:
            start += 1
        else:
            end -= 1
    return False

count = 0
for i in range(len(nlist)):
    # nlist에서 i번째 요소를 제외한 부분을 탐색해야 한다. 
    if two_pointers(0, n-1, nlist[i], i):
        count += 1

print(count)

📌 주의

• 1. 두 수의 합은 투포인터지, 이분탐색이 아니다. 이분탐색으로 풀었다 우연찮게 테스트케이스가 맞아서 틀린 문제.
• 2. i 번째 요소를 제외해야 한다. 이것 때문에 애를 먹었는데, 무슨 말이냐 하니... [0,1] 이 주어졌고, 자기 자신이 아닌 수 중에 두 수 를 골라 1을 만들어야 한다. -> 불가능함. 정답: 0
     하지만 처음에 내가 짠 코드는 본인을 포함시켰다는 거...그래서 정답이 1이 나왔다.
     이걸 하다 보니 if interval_sum == target and start != exclude_index and end != exclude_index: 로 처음에 짰는데, 에러가 나더라. (지금 생각해보면 당연함)
     생각해낸 가장 좋은 방법은 continue 쓰기.