[코딩테스트] 연습문제 - 숫자 짝꿍

---

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

X, Y 두 문자열 중 겹치는 숫자로 만들 수 있는 최댓값을 리턴하는 문제. 겹치는 숫자가 없다면 -1을 리턴하고 만약 0이 여러개라면 0 하나만 리턴해야 한다.

 

정수형이 아니라 문자열인 점, 제한사항으로 X, Y의 길이가 3,000,000까지 증가할 수 있는 점을 고려해야 한다.

 

 

 

---

전략

 

01. Counter

  collections 라이브러리의 Counter를 이용하면 문자열 각각의 개수를 딕셔너리 형태로 리턴할 수 있으므로 X, Y 각각을 Counter 객체로 묶은 뒤에 &(AND) 연산해주면 겹치는 값만을 찾을 수 있다.

 

from collections import Counter

def solution(X, Y):
    x = Counter(X)
    y = Counter(Y)
    
    a = x & y
    result = ''

    for i in a.items():
        result += i[0] * i[1]

    
    if len(result) == 0:
        return "-1"
    elif int(result) == 0:
        return "0"
    else:
        return ''.join(sorted(result, reverse=True))

 

 이를 이용해 위와 같이 풀었으나 시간복잡도 때문에 11~15번 케이스를 통과하지 못했다. 지금 보니 elif int(result) == 0에서 형변환할 때 시간이 오래 걸렸었다. 대신 result[0]이 "0"인지 확인하는 방법으로 했더니 바로 통과했다.

 

 

02. 각 숫자 별 리스트 만들기

 0 ~ 9 자리의 리스트를 만든 뒤 개수를 센다. 마지막에 0 ~ 9의 개수만 세면 되니 시간이 많이 절약된다.

 

---

풀이

 

def solution(X, Y):
    num = [0] * 10
    num_result = [0] * 10
    result = ''
    
    for i in X:
        num[int(i)] += 1
    
    for j in Y:
        if num[int(j)] != 0:
            num[int(j)] -= 1
            num_result[int(j)] += 1
    
    for k in range(9, -1, -1):
        if num_result[int(k)] != 0:
            result += str(k) * num_result[int(k)]
    
    if result == "":
        return "-1"
    elif result[0] == "0":
        return "0"
    else:
        return result

 

 X의 각 자리수를 저장할 num이라는 리스트를 만들고, Y와 연산한 결과를 저장할 num_result라는 리스트를 만든다.

 

 이제 X의 각 자리수를 num에 넣어주고, 다시 Y로 연산한다. 이때, num[int(j)]가 어떤 양수값을 가질 때만 X에 같은 자리수가 있으므로 if num[int(j)] != 0 조건문을 이용해 True일 경우 값을 하나씩 빼주면서 num_result[int(j)]를 하나씩 추가해줬다. 이 방식으로 num_result에는 X, Y에 공통인 숫자들의 개수만 들어가게 된다.

 

 이제 가장 큰 정수로 나열해야 하므로 9부터 0까지 num_result를 하나씩 열어보며 연산해주면 된다.

 

 마지막으로 각 조건에 따라 "-1", "0", 그리고 result 자체가 나와야 하므로 다음과 같은 조건문을 추가해 주었다. 다만, 기존에 내가 했던 방식은 result가 "00000" 따위 일 수 있으므로 int형으로 바꾸어 주었었는데 아주 긴 문자열의 형변환은 아마도 시간을 많이 잡아먹는 것 같다. 따라서 result의 가장 큰 숫자가 0이라면 이 result는 0일 수 밖에 없으므로 result[0]만 체크해주는 방식으로 바꾸었더니 통과할 수 있었다.

 

 

효율성 테스트

---

다른 풀이

 

1. Counter

 

from collections import Counter

def solution(X, Y):
    x = Counter(X)
    y = Counter(Y)
    
    a = x & y
    result = ''

    for i in a.items():
        result += i[0] * i[1]

    
    if len(result) == 0:
        return "-1"
    elif result[0] == "0":
        return "0"
    else:
        return ''.join(sorted(result, reverse=True))

 

통과하지 못했던 Counter를 이용한 풀이를 다음과 같이 개선해 시간복잡도를 약 80% 개선했다. 여기서도 result의 정수형 형변환이 문제였던 것 같다. 

 

효율성 테스트

 

 

---

추가적인 고찰

 

str형으로 나타낸 숫자를 int형으로 바꿀 때 왜 시간이 오래 걸리는지 궁금해서 로컬환경에서 약 10000자로 된 문자열을 int형으로 바꾸는 실험을 해보았다.

 

 ValueError: Exceeds the limit (4300 digits) for integer string conversion

 

 파이썬의 int형은 임의의 길이만큼 정수 크기를 자유롭게 늘릴 수 있지만, 그만큼 메모리를 많이 잡아먹는다. 의도적으로 큰 수를 집어넣어 시스템에 무리를 주는 것을 막기 위해 파이썬은 기본적으로 int<->str 변환의 최대 자릿수를 4300자리로 제한해놓았다. 

 

import sys
sys.set_int_max_str_digits(10000)

 

위 코드를 통해 제한을 늘릴 수 있지만 그만큼 부하가 크므로 하지 않기로 했다.

 

원래 해보고 싶었던 건 자릿수의 증가에 따른 int형 변환과 0번 인덱스 체크의 연산시간 차이를 알아보고 싶었지만, 의미있는 결과를 낼 수 없었다.

 

0 ~ 4000까지 문자열 길이에 따른 int형 변환과 0번 인덱스 체크의 연산 속도 차이 그래프

 

 200 자리수씩 증가시키면서 연산을 시켰다. 중간 두번의 피크는 함수 연산이 문제라기보다 연속적인 연산 과정에서 딜레이가 생겼었던 것으로 보인다.

 

 

더 알아보니, 2의 거듭제곱 꼴이 아닌 str형의 문자열 숫자와 int형 정수를 상호 변환하는 알고리즘 중에 O(n), 즉 선형 시간을 갖는 알고리즘은 없다고 한다. 가장 잘 알려진 알고리즘조차도 2차에 가까운 시간이 걸린다. 따라서 int('5' * 100000)과 같은 연산은 시간이 많이 걸릴 수 밖에 없었다. 따라서 이를 제한하기 위해 파이썬이 위와 같은 제한을 둔 것으로 생각한다.

 

출처: https://runebook.dev/ko/docs/python/library/stdtypes?page=11