[프로그래머스 lv.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의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

 

예전 풀이

생각

X와 Y를 이중 for문을 돈다

X 내의 요소를 기준으로 하나하나 Y의 요소와 비교하며

같은 것이 있을 경우 해당 숫자를 list에 append한 뒤 양쪽에서 del 해준다.

이 과정을 반복한다.

 

인덱스로 접근하고 싶어서 X와 Y를 리스트화해주기

 

코드

def solution(X, Y):
    answer = ''
    list_X = list(X)
    list_Y = list(Y)
    list_ = []
    i = 0
    while i < len(list_X):
        if list_X[i] in list_Y:
            list_.append(list_X[i])
            list_Y.remove(list_X[i])
            del list_X[i]
        else:
            i += 1
    list_ = sorted(list_, reverse = True)
    
    if len(list_) == 0:
        return '-1'
    if all(x == '0' for x in list_):
        return '0'
    
    for i in list_:
        answer += i
    return answer

- .remove() 함수는 해당 value 값을 찾아서 첫 번재로 발견되는 항목만 삭제한다.

- list_X의 현재 요소가 list_Y에 없는 경우 i를 증가시켜준다. list_X의 현재 요소가 list_Y에 존재해서 해당 요소를 list_X에서 삭제할 때 리스트의 길이가 줄어들고 i번째 요소가 다음 요소로 대체된다. 따라서 i를 증가시키지 않으면 다음 반복에서 새로운 i번째 요소를 검사하게 된다. 하지만 list_X의 현재 요소가 list_Y에 없을 경우 list_x에서 아무런 삭제가 일어나지 않으므로 다음 요소로 넘어가기 위해 i를 1 증가시켜야 한다.

- 중복이 없는 경우와 0만 중복되는 경우에 대한 조건을 추가해줬다.

- 0만 중복되는 경우는 all() 과 list comprehension을 사용했다. 이건 내가 잘 모르는 개념이어서 힌트를 얻어 작성했다.

복습이 필요하다.

- 처음에 answer에대 해당 값('-1' 혹은 '0')을 넣어주고 return에서 answer을 반환해주었는데 오류가 난것이다. 해당 if문 안에서 바로 return해주어야 에러가 나지 않았다. 밑에 for문과 관련이 있는 듯 하다.

- 문제는 시간초과,,ㅠㅠ

다시 생각해보기

생각

문자열도 순회 가능하기 때문에 리스트로 바꾸는 부분을 빼려고 했는데 그러면 remove가 안될 것 같다

마지막 for문도 혹시나 해서 빼려고 map함수를 사용해봤는데 큰 차이는 없다.

(일단 시간 복잡도는 갖고, map()함수가 내장함수라서 순수 파이썬으로 작성된 for문보다는 빠를 수도 있으나 메모리 사용량이 높아질수도)

 

- list_Y.remove(list_X[i])의 연산은 리스트에서 원소를 제거할 때 O(n)의 시간복잡도를 가짐. 만약 Y의 길이가 n이라면 최악의 경우 시간복잡도는 O(n²)

- list_X[i] in list_Y도 리스트에 대한 in 연산이 O(n)의 시간 복잡도를 가짐

- 정렬 할 때 다 찾고 정렬하는 게 좋을지, 중간에 정렬하는 게 좋을 지 생각해보기

- list_가 빈리스트이거나 모두 0이라면 반복문 중간에 미리 판단해서 조기에 결과 반환하는 방법 생각해보기

- if list_X[i] in list_Y에서 list_Y에서 원소를 찾는 데 걸리는 시간복잡도는 O(n), 만약 list_X의 크기가 m이라면 최악의 경우 O(mn)의 시간 복잡도를 가짐

 

 

코드

def solution(X, Y):
    answer = ''
    list_X = list(X)
    list_Y = list(Y)
    list_ = []
    i = 0
    while i < len(list_X):
        if list_X[i] in list_Y:
            list_.append(list_X[i])
            list_Y.remove(list_X[i])
            del list_X[i]
        else:
            i += 1
    list_ = sorted(list_, reverse = True)
    
    if len(list_) == 0:
        return '-1'
    if all(x == '0' for x in list_):
        return '0'
    
    answer = ''.join(map(str, list_))
    return answer

 

다른 사람 풀이

def solution(X, Y):
    answer = ''

    for i in range(9,-1,-1) :
        answer += (str(i) * min(X.count(str(i)), Y.count(str(i))))

    if answer == '' :
        return '-1'
    elif len(answer) == answer.count('0'):
        return '0'
    else :
        return answer

코드 스스로 해석하고 이해하기

- 9부터 0까지 숫자를 역으로 순회한다

- 현재 순회 중인 숫자 i가 문자열 X, Y에서 각각 몇 번 등장하는지 count

     - str(i)를 통해 순회 중인 숫자를 문자열로 바꾼다 (X와 Y가 문자열이기 때문에, 연산을 위해서)

      - count메서드를 사용해 각 문자열에서 해당 숫자가 몇 번 등장하는지 세준다.

      - 두 결과 중 작은 것을 가져와

      - 해당 숫자를 위의 결과 만큼 반복해서 answer에 넣어준다

- 만약 answer가 빈 문자열이라면 -1을 반환한다

- 만약 answer의 길이와 answer에서 0의 등장 횟수가 같다면 answer은 0으로 이루어진 것이므로 0을 반환

- 나머지 모든 경우에 대해서는 answer를 그대로 반환한다

 

 

 

def solution(X, Y):
    answer = []
    for i in (set(X)&set(Y)) :
        for j in range(min(X.count(i), Y.count(i))) :
            answer.append(i)
    answer.sort(reverse=True)
    if len(answer) == 0:
        return "-1"
    if answer[0] == "0":
        return "0"
    answer = "".join(answer)
    return answer

코드 스스로 해석하고 이해하기

- 중복을 제거한 X와 Y의 교집합에 해당하는 숫자를 순회한다

- X에서 숫자 i 그리고 Y에서 숫자 i를 세고 더 적은 수 만큼 순회한다

- answer에 i를 넣는다. = i가 j만큼 들어감

- answer를 내림차순 정렬하고

- 만약 answer의 길이가 0이라면 -1을 반환

- 만약 answer의 첫 번째 요소가 0이라면 (내림차순 정렬 했는데도 맨 앞이 0이라면 모두 0인 것) 0을 반환

- 나머지는 문자열로 만들어 반환한다