[백준] 좋다

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

 

백준 1253번: 좋다

 

 

풀었던 방법

→ 두 숫자를 더해서 하나의 숫자를 찾는거니까 투포인터를 썼습니다.

 

숫자를 크기 순서대로 정렬하고

3번째 숫자부터 마지막 숫자까지 하나씩 확인을 합니다

• 포인터를 배열의 가장 처음에 하나, 마지막에 하나를 두고 각 합이 확인중인 숫자랑 같은지를 확인합니다
• 확인중인 숫자 > 합이라면 처음 포인터를 뒤로 밀고,
• 확인중인 숫자 < 합이라면 마지막 포인터를 앞으로 땡기면서 찾았습니다.

 

생겼던 문제

• 처음에는 숫자들이 모두 자연수인줄알고 투포인터를 이용해서 찾을때 탐색하는 범위를 탐색중인 숫자의 앞 배열만을 사용했습니다.

1, 2, 3, 4, 5, 6, 7

예를 들어, 이 방법일 때 5를 확인중이라면

p1 = 1로 두고, p2 = 4로 둬서 확인을 했습니다.

하지만 배열이 모두 자연수가 아니므로 음수의 경우도 고려해야했습니다.

-2, 0, 2, 4

이런 경우에는 2를 탐색할때 앞에 있는 배열만 사용한다면

p1 = -2, p2 = 0이 되므로 찾을 수가 없는 문제가 발생했습니다..

→ 그래서 초기 포인터 설정을 매번 전체 배열의 처음, 끝으로 둬서 개선했습니다.

 

 

제출 코드

# 백준 1253 좋다
# 투포인터

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

nums.sort()

result = 0

for i in range(N):
    target = nums[i]

    left, right = 0, N - 1   
    
    while left < right:
        # 지금 확인중인 숫자는 넘어가게
        if left == i:
            left += 1
            continue
        if right == i:
            right -= 1
            continue
            
        sum_of_left_right = nums[left] + nums[right]
        
        if sum_of_left_right == target:
            result += 1
            break
        elif sum_of_left_right < target:
            left += 1
        else:
            right -= 1

print(result)