2021-01-18] Max Number of K-Sum Pairs

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3608/

오늘의 문제는 어렵게 생각하면 어렵고 쉽게 생각하면 쉬워지는 것 같다.

 

예시를 보며 생각해보자.

 

문제 예시 1-2

 

입력값으로 int형 리스트 nums와 target 값 k가 주어진다. nums의 원소 값 2개를 합하여 k를 만들어내면,

pair 1개가 완성된다. 첫번째 예시처럼

 

[1,2,3,4] -> 첫번째 원소, 마지막 원소를 합하면 1+4 =5 즉 1개의 pair가 완성된다.

그러면 나머지를 제거하고 [2,3] 도 두개의 원소를 합하면 5가 되므로 pair가 총 2개라는 것을 알 수 있다.

 

pair의 값을 구하는 것이므로, 2가지의 값이 같이 움직이게 된다.

 

그런데 또 생각해보면, 꼭 리스트에서 지워야 하는 것도 아니고, 2번처럼 정렬되지 않은 값을 이용할 필요도 없다.

 

2번을 설명할땐, 문제풀이의 방식을 설명해보겠다.

 

최초 입력받은 nums는 정렬되지 않아서, 우선 정렬시켜 최소 최대값을 볼수있도록 하겠다.

 

[3,1,3,4,3] -> [1,3,3,3,4]

 

최대 최소를 비교하며 생각해보자.

1) 1, 4의 합은 k보다 작은 5 이니 1->3으로 이동한다. (  index 값 0 ->1 , ... )

2) 3, 4의 합은 k보다 큰 7이니 4->3으로 이동한다. ( index 값 4->3 , ... )

3) 3, 3의 합은 k와 같은 6이니 pair count 를 하고, 두 값을 뺀다. ( index 1->2, index 3->2 )

만약 index값을 지나치면 종료. 후 pair count 값 반환

 

이게 나의 문제풀이이다.

 

코드로 이 내용을 다시 확인해보자.

 

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        nums.sort() # 입력받은 nums에 대해 정렬
        i,j=0,len(nums)-1 # nums의 최대, 최소 값의 index
        cnt=0 # pair를 세기 위한 값
        while i < j :
            sums=nums[i]+nums[j] # pair 확인을 위한 두 원소의 합
            if sums==k:
                cnt+=1 # pair count!
                i+=1 
                j-=1
            elif sums>k: # k가 작으면 최대값을 줄인다.
                j-=1
            else: # k가 크면 최소값을 키운다.
                i+=1
        return cnt