[내일배움캠프 17일차 TIL] programmers 숫자 짝꿍

코드카타 하면서 시간초과를 마주하지 않아 나름 행복하게 진행중이었는데 결국 피하지 못한 시간초과...

그놈의 시간복잡도.... ㅂㄷㅂㄷ..

하지만 그놈의 시간복잡도 때문에 내가 이런 생활이 가능한거겠지....

시간초과때문에 내가 이 문제에만 한 시간을 넘게 매달렸다고...

---

 

문제는 다음과 같다

 

X와 Y라는 숫자로 이루어진 문자열을 받아와 공통으로 나타나는 수들을 조합하여 최대값을 문자열로 반환하는 문제이다.

 

 

첫 번째 시간초과

 

처음에는 받아온 두 문자열을 리스트로 만들고 하나의 리스트에서 요소를 하나씩 추출하며

다른 리스트들 돌며 해당 문자가 있는지 확인하고 해당 문자가 있으면

common이라는 새로운 리스트에 추가하였다

그리고 common 리스트를 정렬한 후 join을 사용해 문자열로 만들어준 후 조건에 맞게 반환하는 코드를 짰다

물론 이중반복문에 안쪽의 반복문은 길이 이상으로 돌아서 시간이 많이 걸릴 것이라는걸 예상하고

deque를 사용해 조금이라도 시간을 줄여보고자 했지만,,,

TC 11~15번에서 시간초과를 맞이했다....

 

 

from collections import deque
def solution(X,Y):
    X = [i for i in X]
    Y = deque([i for i in Y])
    common = []
    while X :
        x = X.pop()
        for _ in range(len(Y)):
            y = Y.popleft()
            if x == y:
                common.append(x)
                break
            else:
                Y.append(y)
    return f'{int("".join(sorted(common, reverse=True)))}' if len(common) != 0 else "-1"

 

 

 

두 번째 시간초과

 

두 번째 시도에서는 받아온 두 문자열을 리스트로 만든 후에

common을 두 리스트의 교집합으로 저장하고

교집합을 돌면서 각 리스트에 공통된 요소가 몇 개 있는지 확인하였다

그리고 공통된 요소를 key값으로 각 문자열에서 공통된 요소의 최소값을 value로 가지는 딕셔너리를 만들었다

그리고 딕셔너리를 돌면서 숫자들을 이어붇이기 했다

하지만 여기서도 TC 11~15번의 시간초과 벽을 넘지 못했다

 

def solution(X,Y):
    X = [i for i in X]
    Y = [i for i in Y]
    common = set(X) & set(Y)
    common_dict = {}
    for c in common:
        common_dict[c] = min(X.count(c), Y.count(c))
        
    l = []
    for i in common_dict.items():
        for _ in range(i[1]):
            l.append(i[0])

    return f"{int(''.join(sorted(l, reverse=True)))}" if len(l)!=0 else "-1"

 

 

 

세 번째 시간초과

 

세 번째로 생각해낸 코드에서는 Counter를 이용하여 코드를 작성했다

Counter는 문자를 key로 가지고 문자의 개수를 value로 하는 딕셔너리를 반환해준다

입력받은 X,Y를 Counter를 사용해서 딕셔너리로 바꾸어준 후에

key값들의 교집합을 common에 담았다

그리고 common의 요소들을 반복하며 공통된 요소의 최소값을 담은 딕셔너리를 만들어주고

딕셔너리를 돌며 숫자들을 이어붙여줬다

하지만 여기서도 마주해버린 TC 11~15번의 시간초과...

 

from collections import Counter

def solution(X,Y):
    X, Y = Counter(X), Counter(Y)

    common = set(X.keys())&set(Y.keys())
    common_dict = {}

    for c in common:
        common_dict[c] = min(X[c], Y[c])

    l = []
    for i in common_dict.items():
        l.append(i[0]*i[1])

    return f"{int(''.join(sorted(l, reverse=True)))}" if len(l)!=0 else "-1"

 

 

 

이쯤되면 반복문의 문제가 아닌 다른 부분에서 문제가 발생하는 것이라 생각하고

결국엔 구글링을 시도했다....

구글링을 한 결과 문자열을 정수형으로 변환한 후 다시 문자열로 변환하는 과정에서 시간초과가 발생한다는 사실을 알게되었다...

진짜 너무 허무하고 화났다

코드의 line을 줄이고자한 나의 욕망이 이런 결과를 초래했던 것......

 

 

드디어 통과한 코드

 

계속해서 리턴값에

f"{int(''.join(sorted(l, reverse=True)))}" if len(l)!=0 else "-1"

 

이렇게 작성했는데

0만 존재하는 경우를 따로 빼고, int와 포멧팅하는 부분을 날려버렸다

...


if common == set("0"): 
        return "0"
        
        
 ...


''.join(sorted(l, reverse=True)) if len(l)!=0 else "-1"

 

이렇게 고치고 나서는 통과했다,,,,

 

from collections import Counter

def solution(X,Y):
    X, Y = Counter(X), Counter(Y)

    common = set(X.keys())&set(Y.keys())

    # 문자를 숫자형으로 변환하고 다시 문자형으로 변환하는 과정에서 시간초과 오류 발생!
    if common == set("0"):
        return "0"

    common_dict = {}

    for c in common:
        common_dict[c] = min(X[c], Y[c])

    l = []
    for i in common_dict.items():
            l.append(i[0]*i[1])

    return ''.join(sorted(l, reverse=True)) if len(l)!=0 else "-1"

---

 

코드카타를 진행하면서 가장 오랜 시간이 걸린 문제였다....

숏코딩 도파민에 미쳐가지고

간결하고 짧은 코드를 짜는 것도 좋은 연습이 되겠지만

다른 사람이 봤을 때 이해하기 쉽고 직관적인 코드가 정말 중요하다는 것을 다시금 상기시켜주는 시간이었던 것 같다

자료형 변환하는데 많은 비용이 필요하다는 것을 깨달을 수 있는 시간이었고

한 줄이 아닌 여러줄에 조건을 나누어 적어 시간복잡도를 줄일 수 있다는 것도 알게된 좋은 시간이었던 것 같다!