99클럽 코테 스터디_4기 34일차 TIL

 

 

TODAY TIL

📌 문제 설명

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 숫자들을 사용해 만들 수 있는 가장 큰 정수를 두 수의 "짝꿍"이라고 합니다.
짝꿍을 구하는 규칙은 다음과 같습니다:

1. X와 Y에 공통으로 나타나는 숫자만 사용합니다.
2. 공통 숫자 중 가능한 최대 빈도수만큼 사용합니다.
3. 공통 숫자가 없다면 -1을 반환합니다.
4. 짝꿍이 0으로만 구성되어 있다면 0을 반환합니다.

예시

• X = 3403, Y = 13203
  → 짝꿍: 330
• X = 5525, Y = 1255
  → 짝꿍: 552
• X = 12345, Y = 67890
  → 짝꿍: -1

---

💡 문제 해결 방법

이 문제를 해결하기 위한 단계별 접근법은 다음과 같습니다:

Step 1: 숫자의 빈도수 계산

• X와 Y의 각 숫자가 몇 번 나타나는지를 계산합니다.
• collections.Counter를 사용하면 간단하게 자릿수의 빈도를 구할 수 있습니다.

Step 2: 공통 숫자와 빈도수 찾기

• X와 Y의 공통 숫자를 찾고, 각 숫자의 최소 빈도를 기준으로 사용할 수 있는 최대 빈도를 계산합니다.

Step 3: 결과 문자열 생성

• 공통 숫자를 내림차순으로 정렬하여 가장 큰 숫자를 만듭니다.
• 예외 처리:
  • 공통 숫자가 없다면 -1 반환.
  • 결과가 0으로만 구성되어 있다면 0 반환.

🖥 코드 구현

from collections import Counter

def solution(X, Y):
    # Step 1: 숫자의 빈도수를 계산
    count_X = Counter(X)
    count_Y = Counter(Y)
    
    # Step 2: 공통 숫자와 최소 빈도 계산
    common_numbers = []
    for num in count_X.keys():
        if num in count_Y:
            # 공통으로 등장하는 숫자 중 가능한 최대 갯수를 추가
            common_numbers.extend([num] * min(count_X[num], count_Y[num]))
    
    # Step 3: 결과 문자열 생성
    if not common_numbers:  # 공통 숫자가 없으면
        return "-1"
    
    # 숫자를 내림차순으로 정렬
    common_numbers.sort(reverse=True)
    result = ''.join(common_numbers)
    
    # 숫자가 모두 0으로만 구성된 경우
    if result[0] == "0":
        return "0"
    
    return result

 

🛠 동작 원리 설명

1. Counter를 활용한 숫자 빈도수 계산

count_X = Counter("3403")  # {'3': 2, '4': 1, '0': 1}
count_Y = Counter("13203") # {'1': 1, '3': 2, '2': 1, '0': 1}

Counter는 각 숫자의 빈도를 딕셔너리 형태로 반환합니다.

2. 공통 숫자와 최소 빈도 찾기

count_X와 count_Y의 키를 비교하여 공통 숫자를 찾고, 가능한 최대 빈도를 리스트에 추가합니다.

common_numbers = ['3', '3', '0']  # 최소 빈도를 기준으로 계산

 

3. 결과 생성

common_numbers를 내림차순으로 정렬하여 가장 큰 숫자를 생성합니다.

common_numbers.sort(reverse=True)  # ['3', '3', '0']
result = ''.join(common_numbers)   # "330"

 

⚙️ 테스트 케이스

# 테스트 케이스
print(solution("3403", "13203"))  # 330
print(solution("5525", "1255"))   # 552
print(solution("12345", "67890")) # -1
print(solution("100", "203045"))  # 0
print(solution("0", "0"))         # 0

 

결과

XY결과

3403	13203	330
5525	1255	552
12345	67890	-1
100	203045	0
0	0	0

---

💡 문제 풀이 요약

1. 숫자의 빈도를 계산하여 X와 Y의 공통 숫자를 찾습니다.
2. 공통 숫자를 기준으로 가능한 최대 빈도를 계산하여 숫자를 조합합니다.
3. 숫자를 내림차순 정렬하여 가장 큰 짝꿍을 반환합니다.
4. 특별 케이스 (공통 숫자가 없거나, 결과가 0)를 처리합니다.

---

⏳ 시간 복잡도

• 빈도 계산: O(N + M) (X와 Y의 길이)
• 공통 숫자 탐색 및 정렬: O(10 + K log K) (K는 공통 숫자의 수, 최대 10)

최종 시간 복잡도는 **O(N + M)**입니다.

---

✏️ 블로그 마무리

이 문제는 문자열 조작과 빈도 계산을 효율적으로 다루는 연습에 적합합니다.
collections.Counter와 같은 내장 모듈을 활용하면 복잡한 문제도 간단히 해결할 수 있습니다.

여러분도 자신만의 풀이법으로 문제를 해결하고 Python을 더욱 깊게 이해해 보세요! 🚀
궁금한 점이나 추가적인 개선 아이디어가 있다면 댓글로 공유해 주세요! 😊