백준 SILVER 3 [3273번] 두 수의 합 {언어 : Python}

문제 링크

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

정답 코드

n = int(input())
arr = sorted(list(map(int, input().split())))
val = int(input())
left = 0
right = n - 1
answer = 0
while left < right:
    tmp = arr[left] + arr[right]
    if tmp == val:
        left += 1
        right -= 1
        answer += 1
    elif tmp > val:
        right -= 1
    else:
        left += 1
print(answer)

풀이 방법

1. 투 포인터를 사용했다.
2. 정렬한 배열의 좌 우측에서 값을 가져온다.
3. 값이 원하는 값과 같다면 좌를 키우고 우를 낮춰서 범위를 줄여준다.
4. 값이 작다면 좌측에서 값을 키워야 하므로 좌를 키운다.
5. 값이 크다면 우측에서 값을 낮춰야 하므로 우를 낮춘다.
6. 좌우 값이 같지 않을 때 까지 한다.
   1. 인덱스가 겹치지 않는 서로 다른 양의 정수의 쌍을 찾는 문제
7. 값이 같을 때만 answer에 1을 더해주고 이를 출력하면 끝! 

느낀점

• 다른 사람 풀이가 60ms도 내 풀이 84ms 보다 빠르기에 확인해봤다.

def solution(arr, val):
    arrSet = set(arr)
    cnt = 0
    for num in arr:
        if val - num in arrSet:
            cnt += 1
    return cnt // 2

n = int(input())
arr = list(map(int, input().split()))
val = int(input())
print(solution(arr, val))

• 속도는 빠르지만 메모리가 올라간 것을 확인할 수 있다.
• 시간 복잡도는 낮출 수 있지만 set를 사용하면서 공간 복잡도를 키웠다고 생각한다.
• 둘 중에 어떤 알고리즘을 선택하는 것은 자유이나 상황에 맞는 알고리즘을 선택하는 개발자가 되겠다.