[3273] 두수의 합

2023-03-21 | Algorithms / 백준 문제 풀이 모음 # Python, Sliver 3

백준 문제 풀이

3273번: 두 수의 합

• 해설

    N개의 원소 중 2개를 더했을 때 X 값이 되는 조합의 수를 구하는 문제이다.
      
    일일히 2개를 픽해서 더하는 방식도 가능하겠지만, N이 크기 때문에
    좀 더 효율적인 방식이 좋을 것이다.
      
    그래서 사용하는 것이 투 포인터이다.
      
    투 포인터
    포인터를 2개 둬서 조건에 따라 해당 포인터를 이동시키면서 조건에 맞는 지 체크하는 형식이다.
    우선, 투 포인터에서 중요한 점은 2개의 포인터 중 어떤 걸 옮길지 조건을 제시해주는 것이다.
    원소들을 정렬하고, 포인터를 양쪽 끝에 둔다면...
      
    첫번째 포인터는 가장 작은 값, 두번째 포인터는 가장 큰값을 가지게 된다.
    포인터에 해당하는 두 수의 합이 X보다 작다면, 앞의 포인터를 이동 시키고
    큰 경우는 뒤의 포인터를 이동시키는 방식으로 진행한다.
      
    같은 경우는 어떻게 할까...?
      
    같은 경우는 두 포인터를 모두 이동시킨다.
      
    물론 모든 경우의 수를 보지는 않기에 시간 복잡도가 낮고, X에 가까워지도록 코드를 작성했기 때문에
    X에 해당하는 경우의 수를 모두 찾을 수 있다.
  

• 답안

    import sys
      
    if __name__ == '__main__':
        N = int(sys.stdin.readline())
        nums = list(map(int, sys.stdin.readline().split()))
        X = int(sys.stdin.readline())
        start = 0
        end = N-1
        count = 0
        nums = sorted(nums)
        while start < end:
            sums = nums[start] + nums[end]
            if sums == X:
                count += 1
                start += 1
                end -= 1
            else:
                if sums < X:
                    start += 1
                else:
                    end -= 1
      
        print(count)