프로그래머스 숫자 짝꿍(Python)

시간 초과가 나는 문제들은 블로그에 따로 이해 후 정리한다.

오답 코드 (시간 초과)

def solution(X, Y):
    answer = ''
    common = []
    Y = list(Y) 
    
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                common.append(int(X[i]))
                Y[j] = '' 
                break
                
    common.sort(reverse = True)
    if not common:
        return '-1'
    elif common[0] == 0:
        return '0'
    else:
        answer = ''.join(map(str, common))
            
    return answer

처음에 풀이하였던 방식이다.
공통되는 값을 넣어줄 common 리스트를 초기화 하고 넣어주었다.
이렇게 하였을 시 이중 for문으로 순회를 하기 때문에 앞의 값들을 중복해서 들어가는 경우가 생겨서 넣은 후 공백으로 치환해버리면 해결된다.
그리고 X[i]가 5일 때 Y[j]가 5를 만났으면 이를 해결하고 넘겨야하므로 break를 해주었다.

결과는 테스트케이스 5개 가량이 시간초과가 발생했다.

정답 코드

def solution(X, Y):
    answer = ''
    count_X = [0] * 10
    count_Y = [0] * 10
    common = []
    
    for i in X:
        count_X[int(i)] += 1
    for i in Y:
        count_Y[int(i)] += 1
    
    for i in range(10):
        if count_X[i] > 0 and count_Y[i] > 0:
            common.extend([i] * min(count_X[i], count_Y[i]))

    common.sort(reverse = True)
    if not common:
        return '-1'
    elif common[0] == 0:
        return '0'
    else:
        answer = ''.join(map(str, common))
            
    return answer

이중 for문 부분을 건드려야겠다고 생각이 들어서 시간을 깎아보았다.
우선 0부터 9까지의 개수를 기록할 카운트 리스트를 선언한다.

그리고 각각 나온 개수만큼 추가를 해준다.
그 다음은 0부터 9까지 공통되는 값을 common 리스트에 넣어주면 된다.

for i in range(10):
    if count_X[i] > 0 and count_Y[i] > 0:
        common.append(i)

여기서 문제가 생겼는데 테스트케이스 5번의 경우 2, 5, 5가 입력되어야하나 2, 5만 입력되는 경우가 생겼다.

이를 정답 코드로 변경해준 결과

본래 처음에 말했던 2, 5가 아닌 5가 추가된다.

해결 방안

위에서 count_X, count_Y 리스트를 확인하면 인덱스 6, 즉 5의 공통적인 부분을 찾는 값은 3, 2가 나와있다.

1, 1이 나왔다는 뜻은 공통된 값이 한 개씩 있으므로 한번씩 추가해주면 되나 2, 2가 있다면 두번 공통되는 값이 있다는 뜻이므로 그 만큼을 추가해주어야한다.

if count_X[i] > 1 and count_Y[i] > 1:
	common.append(i)

처음에는 이렇게 해본 결과 테스트케이스에서는 잘 나왔다.
무식하게 다른 것은 전혀 고려하지 않고 한번 더 추가해주었기 때문이다.
하지만 전체적인 테스트케이스에서는 공통되는 숫자 값이 더 숨어져있었고 실패가 나와서 코드를 수정했다.

for i in range(10):
    if count_X[i] > 0 and count_Y[i] > 0:
            common.extend([i] * min(count_X[i], count_Y[i]))

min(count_X[i], count_Y[i])는 두 문자열에서 해당 숫자가 등장한 횟수 중 작은 값을 구한다. 왜냐하면 공통으로 등장하는 숫자는 두 문자열에서 등장한 횟수 중 적은 횟수만큼만 추가되어야 하기 때문이다. 그리고 extend([i] * min(count_X[i], count_Y[i]))는 해당 숫자를 common 리스트에 추가하는데, 이때 등장한 횟수만큼 추가된다.
예를 들어, X에서 숫자 5가 3번 등장하고, Y에서 숫자 5가 2번 등장한다면, 공통 리스트에는 숫자 5가 2번 추가된다.

💡 append 대신 extend를 사용한 이유
위의 코드에서는 공통으로 등장한 숫자를 리스트에 추가해야 하며, 이때 각 숫자가 등장한 횟수만큼 추가되어야 한다.
따라서 extend() 메서드를 사용하여 각 숫자를 등장한 횟수만큼 추가한다. 만약 append()을 사용한다면 각 숫자를 한 번씩만 추가할 것이다.

풀이 후기

시간복잡도를 깎아보려고 구글링을 해봤는데 set을 쓰고 Counter를 쓰는데 나에게는 그리 직관적으로 다가오지 않아서 직접 풀이를 해보았다.