[백준] 3273 - 두 수의 합 (python)

문제 링크

문제에서 시간 제한을 1초로 줬다. 아무래도 완전 탐색으로 하면 연산 횟수가 10^8보다 크게 나오기 때문에 반복문을 한 번 이상 쓰면 힘들 거 같다는 생각이 들었다. 그걸 알고 있음에도 풀이에 있어서 접근을 어떤 식으로 해야 하는지 감이 안 왔다.

내가 문제를 풀던 것을 보던 오빠가 먼저 정렬을 하면서 접근해 보라고 했고, 정렬을 하니 금방 감이 왔다.

이 예시에서는 정렬한 뒤 배열의 맨 앞의 인덱스는 start, 끝을 end라고 한다면

start와 end를 더하면 13이 되는 것이 보인다.

하지만 여기서 만약 합이 13이 아닌 12인 것을 구해야 한다면?

end를 한 칸 앞으로 옮기면 된다.

또 여기서 합이 14인 것을 구하라고 하면

start를 한 칸 뒤로 보내면 된다.

자 다시 13인 것을 구하는 상황으로 돌아와보자

1과 12가 13이 되기 때문에 2와 11로 이동을 해야 한다. 이것은 start와 end가 동시에 이동을 해야 한다는 것을 의미한다.

하지만 이 과정이 계속된다면 인덱스 에러가 떠버린다.

그렇기 때문에 종료 조건을 줘야 하는데 start가 end와 만나거나 start가 end보다 커지게 되면 이미 탐색은 다 끝낸 거기 때문에 종료해 주면 된다.

말주변이 없어서 오히려 코드 보는 게 이해에 더 도움이 될 지경이다.

# 입력
n = int(input())
l = list(map(int,input().split()))
x = int(input())

# j -> end, i -> start
j = n - 1
i = 0
cnt = 0

# 정렬
l = sorted(l)


while True:
    if i >= j:
        break
    if l[i] + l[j] > x:
        j -= 1
    elif l[i] + l[j] < x:
        i += 1
    else:
        cnt += 1
        i += 1
        j -= 1
print(cnt)

이게 투포인터라고 한다. 전에 코테를 보았을 때 투포인터를 잘 몰라 완탐으로 해서 효율성에서 문제가 생겼는데 이거보니 대충 뭔 의미인지는 알겠다. (하지만 그 문제가 훨 어려움😢)

다른 문제유형으로 좀 더 익숙해져봐야 겠다.
또한 오빠가 말한 것처럼 좀 노트에 적으면서 알고리즘을 풀고자 해보아야 겠다.