[프로그래머스] 숫자 짝꿍 파이썬 알고리즘 문제풀이 # 반복문 기준 정하기 # sort 함수 안 쓰기

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘은 프로그래머스 Lv1. 숫자 짝꿍 문제 풀어보겠습니다.

 

 

 

 

 

해당 문제 바로 가기 ↓↓↓ 하단 링크 클릭

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

프로그래머스

 

 

 

 

 

1. 정답 공개

---

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

프로그래머스에서 가장 채택을 많이 받은 정답입니다. (22.12.12 기준)
제가 푼 풀이하고 원리는 비슷하지만 더 간결하고 좋은 정답 같습니다.
특히 문자열 '000'을 걸러내는 테크닉이 인상 깊었습니다.

 

 

 

 

 

# 1. 뭘 대상으로 반복문을 돌릴지... X? Y? no.. 0 ~ 9까지 10개만!
# 2. 정렬하지 않고도 자동으로 정렬이 되게 하는 법? (sort는 시간을 많이 잡아먹음..)

def solution(X, Y):
    answer = ''
    # ★ 포인트1. 반복되는 숫자를 저장하기 위한 dictionary (key: 0 ~ 9)
    numx = {str(n):0 for n in range(10)}
    numy = {str(n):0 for n in range(10)}
    
    # X 문자열 하나씩 돌면서 카운트
    for x in X:
        numx[x] += 1
    
    # Y 문자열 하나씩 돌면서 카운트
    for y in Y:
        numy[y] += 1
    
    # ★ 포인트2. 9부터 0까지 반복문 돌기. sort를 안 하기 위함.
    #           짝꿍을 큰 수부터 더해가면 자동으로 제일 큰 수가 됨.
    for k in range(9, -1, -1):
        k = str(k)
        iternum = min(numx[k], numy[k])
        
        # ★ 포인트3. "000" -> "0"으로 만들어주기 위한 조건문
        if answer == '' and k == '0' and iternum != 0:
            return "0"
        
        # 실패 코드 #############################
        # for _ in range(iternum):             #
        #     answer = ''.join([answer, k])    #
        ########################################
        # 성공 코드 ★★★★★
        # '9'*3 = '999'가 되는 원리를 이용
        answer = ''.join([answer, k*iternum])  
        ########################################
    
    if answer == '':
        return "-1"
    else:
        return answer

제가 푼 정답입니다.
코드가 더 길어보이는 이유는 설명 주석을 다느라 그렇습니다. ^^
아무래도 이해하시기는 더 편할지도 모릅니다.

위에서 부터 차근차근 설명해보도록 하겠습니다.

 

 

 

 

2. 0 ~ 9 범위의 dictionary 만들기

---

def solution(X, Y):
    answer = ''
    # ★ 포인트1. 반복되는 숫자를 저장하기 위한 dictionary (key: 0 ~ 9)
    numx = {str(n):0 for n in range(10)}
    numy = {str(n):0 for n in range(10)}

    print('numx:', numx)
    print('numy:', numy)

numx: {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}
numy: {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

딕셔너리를 출력해보면 위와 같이 나옵니다.
0 부터 9까지의 숫자값을 str로 만든 뒤, 모두 0으로 초기화 했습니다.

이러한 딕셔너리들을 만든 이유는,
반복문을 돌릴 때, X나 Y를 기준으로 돌리는 것이 아니라,
숫자 0~9를 기준으로 돌리기 위해서 입니다.
(X 기준으로 Y랑 겹치는 것을 다 일일이 카운트 하면... 시간 초과가 납니다!)

 

 

 

 

 

def solution(X, Y): # X:"12321", Y:"42531"
    answer = ''
    # ★ 포인트1. 반복되는 숫자를 저장하기 위한 dictionary (key: 0 ~ 9)
    numx = {str(n):0 for n in range(10)}
    numy = {str(n):0 for n in range(10)}

    # X 문자열 하나씩 돌면서 카운트
    for x in X:
        numx[x] += 1
    
    # Y 문자열 하나씩 돌면서 카운트
    for y in Y:
        numy[y] += 1

    print('numx:', numx)
    print('numy:', numy)

numx: {'0': 0, '1': 2, '2': 2, '3': 1, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}
numy: {'0': 0, '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 0, '7': 0, '8': 0, '9': 0}

이제 문자열들을 하나씩 돌려보면서
각각의 dictionary key들의 value들을 하나씩 늘려 주었습니다. (+1)
각각의 dictionary들을 프린트 해보면 위와 같은 결과가 나옵니다.
(참고로 X, Y는 4번 예시를 썼습니다.)

이렇게 함으로써, 각각의 X, Y에 0~9 숫자들이
얼마나 들어있는지 한눈에 확인할 수 있습니다.

반응형

 

 

 

 

3. sort 함수 안 쓰고, for문으로 자동 정렬하기

---

def solution(X, Y): # X:"12321", Y:"42531"
    answer = ''
    # ★ 포인트1. 반복되는 숫자를 저장하기 위한 dictionary (key: 0 ~ 9)
    numx = {str(n):0 for n in range(10)}
    numy = {str(n):0 for n in range(10)}

    # X 문자열 하나씩 돌면서 카운트
    for x in X:
        numx[x] += 1
    
    # Y 문자열 하나씩 돌면서 카운트
    for y in Y:
        numy[y] += 1

    # ★ 포인트2. 9부터 0까지 반복문 돌기. sort를 안 하기 위함.
    #           짝꿍을 큰 수부터 더해가면 자동으로 제일 큰 수가 됨.
    for k in range(9, -1, -1):
        k = str(k)
        iternum = min(numx[k], numy[k])
        
        # ★ 포인트3. "000" -> "0"으로 만들어주기 위한 조건문
        if answer == '' and k == '0' and iternum != 0:
            return "0"

        print(k, ':', iternum)

9 : 0
8 : 0
7 : 0
6 : 0
5 : 0
4 : 0
3 : 1
2 : 1
1 : 1
0 : 0

이제 만들어둔 딕셔너리를 가지고, 숫자 짝꿍들을 세어봅시다.
숫자 짝꿍은 두 X, Y 에서 공통으로 나타나는 숫자들을 말합니다.

iternum = min(numx[k], numy[k])
해당 코드는 두 딕셔너리 값 중 더 작은 수를 return합니다.
예를 들어 X에서 3이라는 숫자가 4번, Y에서 3이라는 숫자가 6번 반복된다면?
공통적으로 반복되는 것은 숫자3 이 4번이라는 것입니다. (min 함수를 쓴 이유)

이것을 iternum에 할당하고 그 숫자만큼 반복된 문자열을 더해주는데요,
9부터 0까지 역순으로 내려가기 때문에, sort함수를 쓸 필요가 없습니다.
(반복문이 끝나면 자동으로 가장 큰 수가 나오는 원리)

마지막으로, 저는 문자열 "000"을 걸러내는 조건문을 만들었는데요,
음.. 이것보다는 모범답안의 정답이 좀 더 우아하군요..
그것으로 대신하겠습니다.

   elif len(answer) == answer.count('0'):
        return '0'

전체 문자열이 0으로 채워진 것을 카운트하고, 전체 문자열의 길이와
비교하는 부분입니다. (제 코드보다 훨신 깔끔하네요 ^^;)

 

 

 

 

 

4. 반복되는 문자열 더해주기 (중요)

---

# 1. 뭘 대상으로 반복문을 돌릴지... X? Y? no.. 0 ~ 9까지 10개만!
# 2. 정렬하지 않고도 자동으로 정렬이 되게 하는 법? (sort는 시간을 많이 잡아먹음..)

def solution(X, Y):
    answer = ''
    # ★ 포인트1. 반복되는 숫자를 저장하기 위한 dictionary (key: 0 ~ 9)
    numx = {str(n):0 for n in range(10)}
    numy = {str(n):0 for n in range(10)}
    
    # X 문자열 하나씩 돌면서 카운트
    for x in X:
        numx[x] += 1
    
    # Y 문자열 하나씩 돌면서 카운트
    for y in Y:
        numy[y] += 1
    
    # ★ 포인트2. 9부터 0까지 반복문 돌기. sort를 안 하기 위함.
    #           짝꿍을 큰 수부터 더해가면 자동으로 제일 큰 수가 됨.
    for k in range(9, -1, -1):
        k = str(k)
        iternum = min(numx[k], numy[k])
        
        # ★ 포인트3. "000" -> "0"으로 만들어주기 위한 조건문
        if answer == '' and k == '0' and iternum != 0:
            return "0"
        
        # 실패 코드 #############################
        # for _ in range(iternum):             #
        #     answer = ''.join([answer, k])    #
        ########################################
        # 성공 코드 ★★★★★
        # '9'*3 = '999'가 되는 원리를 이용
        answer = ''.join([answer, k*iternum])  
        ########################################
    
    if answer == '':
        return "-1"
    else:
        return answer

이 부분은 특히 중요하기에 실패코드와 성공코드로
주석을 현란하게 구분해 두었습니다!
문자열을 더할 때, 반복문으로 하나씩 더해주는 것보다
[문자열] * [숫자] 방식으로 더해주는 게 훨씬 시간 단축이 됩니다.

계속 11 ~ 15번 예시에서 시간 초과가 떴는데,
이 부분을 해결하니 더 이상 시간초과가 뜨지 않았습니다!

 

 

 

 

5. 마무리

---

오늘 짚어볼 포인트는 크게 3가지 입니다.

1. 공통된 부분을 찾기 위한, for문의 기준 잡기
=> X, Y가 아닌 0~9의 10개 숫자로 기준 잡아서 돌리기

2. sort함수를 안 쓰고 시간 단축하는 원리 알기
=> for k in range(9, -1, -1)로 자동으로 큰 정답 구하기

3. 반복된 문자열을 효울적으로 더하는 방법
=> 반복문 보다 [문자열] * [숫자] 테크닉 이용하기


도움이 되셨다면 댓글과 하단의 하트 부탁드립니다.
감사합니다.