[LV.3] 연습문제 > 숫자 짝꿍 ⭐️

문제

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

프로그래머스

---

문제 설명

• 두 문자열 X, Y가 주어짐 (각각 정수처럼 생긴 숫자 문자열)
• X와 Y에 공통으로 등장하는 숫자들을 골라 가장 큰 수를 만들어야 함
  • 각 숫자는 양쪽에 공통으로 존재하는 만큼만 사용 가능
  • 숫자 순서를 조합해 가장 큰 정수를 만들 것
• 짝꿍이 없다면 → "–1" (공통 숫자 없음)
• 제한사항
  3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000
  X, Y는 0으로 시작하지 않음
  X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환

---

풀이 흐름

1. 각 숫자의 개수 세기

2. 공통 숫자의 개수 구하기

3. 내림차순으로 조합

4. 짝꿍 없을 때의 예외 처리

---

정답 코드 (개선점 존재)

def solution(X, Y):
    # 딕셔너리 - 각 숫자별 등장 횟수 저장
    cnt_X = {}
    cnt_Y = {}
    
    # 각 숫자의 등장 횟수 세기
    for i in X:
        if i in cnt_X:
            cnt_X[i] += 1
        else:
            cnt_X[i] = 1   # 해당 숫자가 처음 등장할 때 += 1 하면 에러 (초기값 1 할당)
    
    for i in Y:
        if i in cnt_Y:
            cnt_Y[i] += 1
        else:
            cnt_Y[i] = 1
            
    # 리스트 - 공통으로 등장하는 숫자들 저장
    result = []
    
    # 9~0까지 큰 숫자부터 처리하기 위해 내림차순으로 (가장 큰 수 만드는 것이 목적이라)
    for j in range(9, -1, -1):
        d = str(j)         # 숫자 j를 문자열로 변환 (딕셔너리 키는 문자열)
        
        # X와 Y 모두에 숫자 d가 등장하는 경우
        if d in cnt_X and d in cnt_Y:
            count = min(cnt_X[d], cnt_Y[d]) # 두 수에서 공통으로 사용할 수 있는 숫자의 최소 등장 횟수
            result.append(d * count)        # 숫자 d를 count만큼 반복하여 결과 리스트에 추가
            
    answer = ''.join(result)                # 리스트에 담긴 숫자들을 모두 이어 붙여 문자열 생성
    
    # 공통 숫자가 하나도 없으면 "-1" 반환
    if not answer:
        return "-1"
    # 결과가 '0'으로 시작한다는 것은 모든 숫자가 0으로만 이루어진 경우
    elif answer[0] == '0':
        return "0"
    else:
        return answer  # 완성된 가장 큰 짝꿍 문자열 반환

---

1. 딕셔너리 대신 collections.Counter 사용

 

2. if d in cnt_X and d in cnt_Y: 불필요

- Counter는 기본값이 0이라 키 존재 여부 체크 없이 최소값 비교만으로 충분

---

개선된 코드

from collections import Counter

def solution(X, Y):
    # 각 숫자의 등장 횟수
    count_X = Counter(X)
    count_Y = Counter(Y)
    
    result = []

    # 9부터 0까지 공통 숫자 확인 (큰 숫자부터 추가하기 위함)
    for digit in map(str, range(9, -1, -1)):
        common_count = min(count_X[digit], count_Y[digit])
        result.extend([digit] * common_count)

    # 공통 숫자가 하나도 없으면 -1 반환
    if not result:
        return "-1"

    answer = ''.join(result)

    # 결과가 0으로만 이루어져 있으면 "0" 반환
    return "0" if answer[0] == '0' else answer

---

- for digit in map(...):

# map()은 여러 값에 같은 함수를 쉽게 적용할 때 사용

# 각 숫자를 문자열로 바꾸기
for digit in map(str, range(9, -1, -1)):
    # digit은 '9', '8', '7', ... '0' 이렇게 문자열로 순서대로 나옴

 

- result.extend 사용 이유