[프로그래머스] 숫자 짝꿍

무려 푸는데만 1시간... 시간초과 문제로 다시 풀어보는데 1시간 반... ^_^

즐거운 알고리즘 문제 푸는 시간...

하루 한문제 열심히 풀고 있지만 풀때마다 현타가 쎄게 온다...후 그래도 계속 하다보면 실력이 늘어나겠지?!!?!

---

문제 설명

---

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다.

예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가 2개 나타나므로 남는 5 한 개는 짝 지을 수 없습니다.)
두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해주세요.

 

제한사항

---

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

나의 풀이 - 첫번째

---

def solution(X, Y):
    X = list(X)
    Y = list(Y)
    
    result = []
    for x, x_v in enumerate(X):
        for y, y_v in enumerate(Y):
            if x_v == y_v:
                Y[y] = -1
                result.append(y_v)
                break

    lst = [int(r) for r in result]

    if sum(lst) == 0 and len(result) > 0:
        return "0"
    elif sum(lst) == 0 and len(result) == 0:
        return "-1"
    else:
        return "".join(sorted(result, reverse=True))

기본 테스트 케이스 예제는 실행이 잘 되지만 추가 19개의 테스트에서 시간초과 문제가 발생했다..

예상하는건 이중 for문과 pop의 사용..!

 

1. 시간 복잡도를 알아야 하는 이유

- 알고리즘을 풀다 보면 '시간 초과'되는 경우가 있음

- 문제를 풀고 나서도 결과 시간이 다른 사람들보다 상당히 높게 나오는 경우가 있음

 

2. 시간 복잡도

- 시간이 얼마나 걸리느냐

- 예를 들어, 길이가 n인 리스트를 처음부터 끝까지 요소를 하나씩 출력한다면, print 함수를 n번 사용하므로 O(1) * n 이므로 O(n)이라고 생각할 수 있다.

즉, 이중 for문은 O(n^2), 삼중 for문은 O(n^3)..... ㅎ

- pop의 경우도 마지막 값을 빼내기 위해 전체 복사를 해주기 때문에 시간 복잡도가 O(1)이 아닌 O(n)이다..

 

결국 나의 코드 문제는..!! 이중 for문과 pop의 합작으로 시간이 오래 걸렸던 것이었다....

(나름 잘 풀었다고 생각했는데... ^____^)

 

그래서 같이 문제 푼 사람들의 코드 리뷰를 듣고 다시 문제를 풀어보았다!

 

나의 풀이 - 두번째

---

def solution(X, Y):
    X = [int(x) for x in X]
    Y = [int(y) for y in Y]
    
    setNum = set(X)

    x_dict = { n:X.count(n) for n in setNum }
    print(x_dict)
    y_dict = { n:Y.count(n) for n in setNum }
    print(y_dict)


    result = []
    for n in setNum:
        for i in range(min(x_dict[n], y_dict[n])):
             result.append(n)
    

    if sum(result) == 0 and len(result) > 0:
        return "0"
    elif sum(result) == 0 and len(result) == 0:
        return "-1"
    else:
        result = [str(n) for n in result]
        return "".join(sorted(result, reverse=True))

이중 for문을 없애고 해당 리스트의 숫자마다 개수를 dict 형태로 저장해서 문제를 해결하였다.

 

 

해당 문제는 Counter를 사용해서 숫자의 빈도를 dict 형태로 바로 반환해서 해결 할 수도 있다!

from collections import Counter

 

또한 리스트의 차집합, 합집합을 리스트 컴프리헨션으로 구현한다면

A = [1,2,3]
B = [1,4,5]

차집합 = [ _ for _ in A if _ not in B ]
합집합 = [ _ for _ in A if _ in B ]

 

위의 두가지 방법을 적절히 활용한다면 더 간단하게 문제를 해결 할 수 있다!

 

---

참고 자료 :

https://chancoding.tistory.com/43

[Python] 파이썬 자료형 및 연산자의 시간 복잡도(Big-O) 총 정리

https://hyun-am-coding.tistory.com/entry/Python-list-%EC%97%B0%EC%82%B0%EC%97%90-%EB%94%B0%EB%A5%B8-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

Python list 연산에 따른 시간 복잡도