hackerrank - Sock Merchant - Python3

문제: https://www.hackerrank.com/challenges/sock-merchant/problem

John은 옷가게에서 일합니다. 짝을 지어야 팔 수 있는 양말 더미가 있습니다. 정수 배열은 각 양말의 색입니다. 얼마나 많은 짝의 양말이 있는지 확인하세요.

예를 들어, n=7개이고 ar=[1,2,1,2,1,3,2]색의 양말이 있습니다. 한 짝의 색1, 한 짝의 색 2가 있습니다. 그리고 나머지 3개의 양말이 있습니다. 짝의 수는 2입니다.

Sample Input

9
10 20 20 10 10 30 50 10 20

Sample Output

3

색 10이 2짝, 색 20이 1짝 있어서 3짝입니다.

다음 코드에서 sockMerchant함수를 완성합니다.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the sockMerchant function below.
def sockMerchant(n, ar):

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    ar = list(map(int, input().rstrip().split()))

    result = sockMerchant(n, ar)

    fptr.write(str(result) + '\n')

    fptr.close()

 

풀이 방법을 생각해 봅시다. 일단 같은 색상의 양말끼리 모읍니다. 양말이 3개 있다면 1짝 하고 1개가 남습니다. 3/2 = 1.5인데 소수점을 버리면 1짝이 됩니다. 양말이 4개라면 2로 나누면 2짝으로 깔끔하게 떨어집니다. 양말이 5개라면 2로 나누면 2.5인데 소수점을 떼면 2짝이 됩니다. 같은 색으로 모인 양말의 수를 각각 2로 나누고 소수점을 버리고 합을 구하면 팔 수 있는 양말 짝의 개수를 구할 수 있겠습니다.

다음과 같이 구현해 보았습니다.

def sockMerchant(n, ar):
    cn = {}
    for a in ar:
        if a in cn:
            cn[a] += 1
        else:
            cn[a] = 1

    temp = []
    for x in cn.values():
        temp.append(int(x/2))

    return sum(temp)

일단 cn dictionary에 색상별 양말의 개수를 저장합니다. cn.vaules()를 이용해서 개수만 뽑아내는데 2로 나눈 다음 int() 메서드로 소수점을 제거한 결과만 temp 리스트에 저장합니다.

temp의 합을 구하면 팔 수 있는 양말 짝의 총개수를 구할 수 있습니다.

아래는 좀 더 간단하게 구견해 본 코드입니다.

from collections import Counter

# Complete the sockMerchant function below.
def sockMerchant(n, ar):
    cn = Counter(ar)
    temp = [int(x/2) for x in cn.values()]
    return sum(temp)

collections의 Counter를 이용하면 배열의 요소들의 개수를 구해줍니다.

temp = [int(x/2) for x in cn.values()]

는

    temp = []
    for x in cn.values():
        temp.append(int(x/2))

을 한 줄로 줄여서 표현한 것입니다.

이 정도만 해도 충분해 보이는데요.

조금 더 메모리 사용량을 줄이고 for loop 돌리는 횟수를 줄이려면 다음과 같이 구현해 볼 수도 있습니다.

def sockMerchant(n, ar):
    sum = 0
    temp = {}
    for a in ar:
        if a in temp:
            del temp[a]
            sum += 1
        else:
            temp[a] = 1
    return sum

temp dictionary에 색깔이 이미 있으면 지우면서 sum을 1씩 추가합니다. 없으면 temp dictionary에 추가합니다. 성능상 미미한 수준의 향상이 있으나 크게 나아지지는 않습니다. 기존 풀이도 for loop가 중첩되지 않기 때문에 시간 복잡도는 둘 다 O(n) 이기 때문입니다.