일주일에 5문제- Week 1: Leetcode Array

 모두의 연구소 풀잎스쿨 10기에서 스터디 두개를 참여하고 있다. 하나는 '일주일에 5문제', 다른 하나는 '파이썬 어디까지 써봐썬'이다.

 새 회사로 가야하는데 코딩테스트에서 번번히 죽을 쑤고 있어서 (...) 강제로라도 문제를 풀기 위해서 참여하게 되었다.

 스터디는 leetcode에서 코딩테스트에서 빈번하게 출제된 문제 위주로 풀고 서로 풀이를 공유하는 방식이다. 어제 첫 모임을 다녀왔는데 다 못 풀고 가는 바람에 내가 못해서 눈치보이지 않을까 걱정했는데, 걱정이 무색하게 다들 친절하셔서 마음이 놓였다. 

 

첫 주의 주제는 배열 관련이었다.

- problem set: https://leetcode.com/list/xuahk4h6/

Favorite - LeetCode

- 참고자료: https://leetcode.com/explore/learn/card/array-and-string/

Explore - LeetCode

각 문제 풀이는 내 repo에 올려놨는데 마지막 문제까진 못 풀었고, 2번까진 풀었고 3번은 사실 Time Exceed가 나서 다시 풀어야한다 (...) O(N^2)인줄 알았는데 다시 보니 O(N^3)이다. 이러니까 Time exceed가 나지... 

 

1. 3sum

- 하나의 배열을 주고, 여기서 합쳐서 0이 되는 세개의 숫자 조합을 찾는 문제다. 여기서 중복이 발생하면 안된다!

 

첫번째 접근

- 아 이건 조합 문제구나! 하고 바로 itertools를 임포트하고 combination을 썻는데 바로 시간 초과가 뜬다. 조합의 시간복잡도가 무려 O(N^3)이기 때문이다. 여기에 중복제거도 따로 해줘야한다. 아마도 (-1, -1, 0,1, 1) 식으로 되어있을때 인덱스가 다르면 중복이 안 되는 값이라고 인식하는 것 같다. 그러니까 똑같은 (-1, 0, 1)도 두번째 인덱스의 -1인지, 아니면 뒤의 1이 마지막 인덱스의 1인지에 따라 다른 녀석이라고 생각하는 듯. 때문에 발생한 조합에서 중복을 제거해줘야했는데 난 이것도 비효율적으로 검사했다. 그래도 언젠간 유용하게 쓰일 것이라 생각하고 일단 기록해둔다.

Collections.Counter

if collections.Counter(list_one) == collections.Counter(list_two):

 

두번째 접근

- 아 조합은 안되는구나 하고 깨달았는데 다음으로 생각나는 거라곤 기껏 리스트에서 하나 고르고 걔를 뺀 나머지에서 하나를 고르고, 또 이 두개를 제외한 리스트에서 하나를 고르기다. 이러면 조합과 다를 바가 없는 Cubic이다. 

세번째 접근 (Accepted)

sort()
result = []
loop : i in range(len(nums)-1, 1)
if same num : continue
target_val = -num[i]
j, k = 0, i-1
	second loop: j<k
    	if nums[j]+nums[k] == -num --> result add (nums[i], nums[j], nums[k])
        if same nums[k], nums[j] --> repeat j+1, repeat k -1
return result

두번째 루프에서 다른 두 개의 값을 같이 가져오도록 한다! 이렇게 하면 드디어 Cubic에서 탈출해서 Quadratic으로 갈 수 있다.

 

2. Merge Intervals

- 간격을 요소로 갖고 있는 리스트가 들어오면, 겹치는 간격들을 병합하는 문제. 이 문제는 수월하게 풀었다.

 

먼저 각 interval을 정렬한다. 그리고 나서 인접한 두 간격에서 첫번째 간격의 두번째 요소(first_interval[1])과 두번째 간격의 첫번째 요소(second_interval[0])를 뺐을 때 그 값이 0보다 작거나 같으면 두 간격은 겹치는 부분이 있어 합칠 수 있다. 이런 식으로 겹치는 간격이 있으면 합치고 겹치지 않으면 직전의 간격은 결과 리스트에 추가하고 다시 비교해나간다. 이렇게하면 정렬에서 O(nlogn)이 뜨고 accept를 받을 수 있다.

 

3. Subarray Sum Equals K

- 리스트와 값 K를 받아서 리스트 내의 하위 리스트중 총합이 K가 되는 리스트의 갯수를 구하는 문제

 

이 문제의 경우엔 Brute-force 방식으로 풀어서 시간복잡도가 Cubic이 되어버렸고, 당연하게도 시간 초과가 떳다. 다시 풀어봐야하지만 일단은 discussion에서 봤던 멋진 풀이에 대해서 정리하는 걸로.

- 풀이 링크

- 풀이 설명 링크

멋진 풀이라고 했지만 사실 처음에 봐선 잘 이해가 되지 않아 여러번 들여다 봐야했다. 그러다가 위의 geek for geek에서 풀이설명을 보고 간신히 감을 잡았다. 너무나 직역이지만 .... 일단 여기에 적어둔다. 

"먼저 배열을 조회하는 동안 currsum이라는 곳에 현재 총합을 저장한다. 동시에  currsum의 다른 값들을 카운트한 값을 맵(파이썬에선 Dict)에 유지한다. 만약 currsum의 값이 [기대하는 총합]과 같아지는 순간이 있다면, 하위 배열의 카운트 값을 증가시킨다. 현재 currsum의 값은 기대하는 값을 currsum - sum만큼 초과한다. 만약 currsum의 값에서 이 값이 제거되면, [기대하는 총합]이 얻어진다. 맵에서 해당하는 하위 배열의 값을 찾으면 currsum - sum만큼 총합을 찾을 수있다."

- 그러니까 현재의 총합이 우리가 찾는 k값을 x만큼 초과한다고 했을 때, 만약 계속 총합을 저장해놓았던 곳에서 초과하는 만큼의 값을 가지는 총합이 들어가 있는 부분이 있다면, 현재 총 합에서 해당 총합을 제거하면 k값이 되므로 이 때 결괏값을 1씩 늘려주는 것 같다. 

 

4. Minimum Domino Rotations For Equal Row

- 두 개의 배열이 있고, 각각의 배열은 주사위의 한 면을 뜻한다. 두 배열의 값을  바꿈으로써 하나의 배열이 다 같은 값을 갖게 할 수 있는 최소한의 횟수를 구하는 문제.

- 풀이 링크

이 문제는 사실 마지막에 시간이 모자라서 손대보지도 못했다. 다른 사람들의 풀이를 보면 일단 한 숫자로 꽉 채워야하므로, A[0] 아니면 B[0] 하나가 그 숫자가 될 것이다. 이후 순회를 하면서 최소한으로 변경하는 값을 구하는 방식이다.