[HackerRank] 양말 짝 맞추기

문제

요약하면, 양말색(숫자 리스트)별로 양말 리스트가 주어졌을 때, 색이 짝을 이루는 양말의 갯수를 반환하는 문제이다.

 

코드

# import numpy as np
import collections as co
"""
- n : 주어지는 양말의 갯수
- ar : 실제 양말의 색상과 양말들
"""

# method 1 : deque
def sockMerchant(n, ar):
    dq = co.deque([])
    ndq = 0
    res = 0
    append_flag = False

    for i in range(n):
        if ndq == 0:                      # deque init
            dq.append(ar[i])
            ndq += 1
            print(dq)
        else:
            for j in range(ndq):
                if dq[j] == ar[i]:      # 양말 짝을 맞췄을 때
                    res += 1
                    ndq -= 1
                    dq.remove(ar[i])
                    append_flag = True
                    print(dq)
                    break
            if append_flag:
                append_flag = False
                continue
            dq.append(ar[i])
            ndq += 1
            print(dq)

    return res



# method 2 : sorted list & binary search



if __name__ == '__main__':

    n = 9
    ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]


    result = sockMerchant(n, ar)

    print(result)

결과 : 주어진 테스트 케이스 모두 통과!

해설 :

1. stack과 queue의 합친 자료구조인 collections package의 deque를 이용
2. 일종의 컴파일러의 괄호짝 맞추기 느낌으로 풀음
3. deque list에 양말 list의 값을 하나씩 append하면서 deque list를 순회하면서 양말 짝을 찾을 수 있는지를 확인.
4. deque를 이용한 풀이는 $ O(n^2) $의 시간 복잡도를 소모하기 때문에 time-out을 예상했지만, 이상하게 성공.
5. 아마 주어진 수와 list크기가 크지 않아서인 것 같다.

두 번째로 고안한 방법은

1. sorted list를 만들어서 값을 하나씩 넣을 때마다, sort를 시킨다.
2. 이후 binary search로 해당 값을 찾아내고, 해당 값을 제거하는 알고리즘을 생각했다.
3. 해보진 않았지만, 첫번째 풀이보다는 시간 복잡도가 낮을 것 같았다.