은공지능 공작소 :: 'Python' 카테고리의 글 목록

안녕하세요.
오늘은 프로그래머스 lv1 문제 "로또의 최고 순위와 최저 순위" 문제 풀어보겠습니다.

 

 

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

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

 

 

1. 리스트의 count 함수 사용하여 0의 개수 세기


def solution(lottos, win_nums):
    # lottos: [44, 1, 0, 0, 31, 25]
    # win_nums: [31, 10, 45, 1, 6, 19]
    
    zeros = lottos.count(0)               # 리스트에서 0의 개수 세기
    print(zeros)
2
[리스트형 자료].count(세고 싶은 대상)
위와 같이 리스트에서 원하는 구성 요소들을 셀 수 있습니다.

lottos 리스트에 0은 2개 있으므로, zeros는 2 입니다.
이렇게 미리 0의 개수를 세어두면 문제를 간단히 풀 수 있습니다.

최고 점수는 0인 숫자들을 다 맞췄다고 생각하면 되고,
최저 점수는 0인 숫자들을 한 개도 못 맞췄다고 생각하면 되기 때문입니다.
다음 단계로 넘어가겠습니다.

 

 

 

 

 

2. 순위 값 딕셔너리로 미리 할당


def solution(lottos, win_nums):
    # lottos: [44, 1, 0, 0, 31, 25]
    # win_nums: [31, 10, 45, 1, 6, 19]

    zeros = lottos.count(0)               # 리스트에서 0의 개수 세기
    win = 0                               # win 변수 = 맞춘 개수 (0으로 초기화)
    scores = {0: 6, 1: 6, 2: 5, 3: 4,     # ★ 포인트1. 경우의 수가 7개 밖에 없으므로
              4: 3, 5: 2, 6: 1}           #           각각의 맞춘 개수에 순위 할당하기
                                          # ★ 포인트2. 0개 맞은 순위 = 1개 맞은 순위
순위 값들을 딕셔너리에 미리 할당해 두었습니다.
원래 코딩 테스트에서 하드 코딩은 지양해야 하지만,
지금은 워낙 경우의 수가 적으니까요.. (다 해도 7개 밖에 없습니다)

또 한 가지 포인트는, 0개 맞은 순위와 1개 맞은 순위가 같다는 것 입니다. (둘 다 꼴찌)
1개 맞아도 6등으로 처리해야 하고,
다 빗나가도 6등으로 처리해줘야 테스트를 통과할 수 있습니다.

 

 

 

 

 

3. 맞은 번호의 개수 세기


def solution(lottos, win_nums):
    # lottos: [44, 1, 0, 0, 31, 25]
    # win_nums: [31, 10, 45, 1, 6, 19]

    zeros = lottos.count(0)               # 리스트에서 0의 개수 세기
    win = 0                               # win 변수 = 맞춘 개수 (0으로 초기화)
    scores = {0: 6, 1: 6, 2: 5, 3: 4,     # ★ 포인트1. 경우의 수가 7개 밖에 없으므로
              4: 3, 5: 2, 6: 1}           #           각각의 맞춘 개수에 순위 할당하기
                                          # ★ 포인트2. 0개 맞은 순위 = 1개 맞은 순위
    
    for l in lottos:                    
        if l in win_nums:
            win += 1
    print('win:', win)
win: 2
이제 lottos 리스트를 하나씩 반복문으로 돌면서,
맞았는지 카운트를 해줍니다.
(win이라는 변수에 저장)

맞춘 번호는 1, 31 입니다.
그래서 win에는 2가 할당되어 있습니다.

 

 

 

 

 

4. 최고 점수와 최저 점수 구하기


def solution(lottos, win_nums):
    # lottos: [44, 1, 0, 0, 31, 25]
    # win_nums: [31, 10, 45, 1, 6, 19]

    zeros = lottos.count(0)               # 리스트에서 0의 개수 세기
    win = 0                               # win 변수 = 맞춘 개수 (0으로 초기화)
    scores = {0: 6, 1: 6, 2: 5, 3: 4,     # ★ 포인트1. 경우의 수가 7개 밖에 없으므로
              4: 3, 5: 2, 6: 1}           #           각각의 맞춘 개수에 순위 할당하기
                                          # ★ 포인트2. 0개 맞은 순위 = 1개 맞은 순위
    
    for l in lottos:                    
        if l in win_nums:
            win += 1
    
    most = win + zeros                    # 맞춘 번호 + 0이 다 맞았다고 가정 -> 최고 순위
    least = win                           # 0이 다 틀렸다고 가정 -> 최저 순위
    print('most:', most)
    print('least:', least)
most: 4
least: 2
이제 최고 점수와 최저 점수를 각각 구해봅니다.
최고 점수는 0으로 센 것들이 다 맞았다고 가정하기 때문에,
그냥 zeros를 더해주면 됩니다. (most)

최저 점수는 0으로 된 것들이 다 틀렸다고 생각하면 됩니다.
그래서 그대로 맞은 것들만 반환해 줍니다. (least)

(이제와서 생각해보니.. 변수 이름을 highest, lowest로 하는게
더 나았을 걸 그랬네요.. 이건 뭐 콩글리시도 아니고..)

 

 

 

 

 

5. 마무리


def solution(lottos, win_nums):
    # lottos: [44, 1, 0, 0, 31, 25]
    # win_nums: [31, 10, 45, 1, 6, 19]

    zeros = lottos.count(0)               # 리스트에서 0의 개수 세기
    win = 0                               # win 변수 = 맞춘 개수 (0으로 초기화)
    scores = {0: 6, 1: 6, 2: 5, 3: 4,     # ★ 포인트1. 경우의 수가 7개 밖에 없으므로
              4: 3, 5: 2, 6: 1}           #           각각의 맞춘 개수에 순위 할당하기
                                          # ★ 포인트2. 0개 맞은 순위 = 1개 맞은 순위
    
    for l in lottos:                    
        if l in win_nums:
            win += 1
    
    most = win + zeros                    # 맞춘 번호 + 0이 다 맞았다고 가정 -> 최고 순위
    least = win                           # 0이 다 틀렸다고 가정 -> 최저 순위
    return [scores[most], scores[least]]  # 딕셔너리를 이용하여 깔끔하게 리턴
이제 아까 만들어둔 딕셔너리의 key로
most와 least를 각각 넣어주면 코드가 완성 됩니다.
오늘의 포인트를 2가지로 정리하겠습니다.


1. count함수를 이용하여 list의 요소 세기
2. 딕셔너리를 이용하여 순위 계산 쉽게 하기


이상으로 마치겠습니다.
반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,

오늘은 파이썬 알고리즘에 많이 사용되는
문자열 다루는 꿀팁 테크닉을 알려드리려고 합니다.
간단히 다음 장에서 결론부터 말씀드리고 설명 드리겠습니다.

 

 

 

 

 

1. 요약 정리


결론은 그냥 문자열을 +하는 것보다 join 함수를 쓰라는 것입니다.
시간 절약을 4배 이상 할 수 있습니다.
다만, 결론에서 말씀드렸다시피 "잘~" 쓰시는게 중요합니다.
다음 절에서 join 함수에 관해 설명 드리겠습니다.

 

 

 

 

 

2. join 함수란?


data = ['a', 'b', 'c']
print(''.join(data))
print('/'.join(data))
output
------------------------------------------
abc
a/b/c
join 함수는 리스트를 합쳐 문자열로 만들어주는 함수입니다.
그런데, join 함수는 구분자를 지정해 줄 수 있습니다.
위의 예시를 살펴보겠습니다.

''.join(data) -> data를 합치는데, 구분자를 공백으로 하니 'abc'가 나옵니다.
'/'.join(data) -> data를 합치는데 구분자는 슬래시(/)로 하니 'a/b/c'가 나옵니다.

보통 코딩테스트에서 join의 구분자는 공백과 함께 많이 쓰게 됩니다.
(문제에 따라 다르겠지만요)

 

 

 

 

 

3. join 함수 잘 쓰는 법


뜬금없이 퀴즈입니다.
join을 잘 쓰려면 어떻게 써야 할까요?

case1은 미리 리스트를 만들어 두고 나중에 join으로 한 번에 합치는 방식이고,
case2는 그 때 그 때 s라는 문자열에 join을 시켜버리는 방식입니다.
과연 정답은?
반응형

 

 

 

 

리스트를 미리 만들어 둔 Case1의 승리입니다.
둘 다 join 함수를 써서 시간 차이가 별로 나지 않긴 하네요 ^^
하지만 +=로 재보았을 때는 125초가 나왔답니다.

 

 

 

 

 

4. 왜 join이 +=보다 빠른가?


https://waymoot.org/home/python_string/

 

Efficient String Concatenation in Python

  Efficient String Concatenation in Python An assessment of the performance of several methods Introduction Building long strings in the Python progamming language can sometimes result in very slow running code. In this article I investigate the computati

waymoot.org

왜 join이 +=보다 빠를까요?
결론부터 말씀드리면, new representation이 매 번 생기지 않기 때문이라고 합니다.
(representation: 객체를 print해보면 나오는 표현식의 일종)

+= 연산은 매 번 new representation을 생성합니다.
그리고 이것은 파이썬 알고리즘 문제풀이에서
많은 시간초과를 발생시키는 원인이기도 합니다.
(궁금하신 분들을 위해 representation에 관한 reference를 남겨두겠습니다)

이것이 join 연산이 +=에 비해 월등히 빠른 이유입니다.

 

 

참고자료: https://www.pythonmorsels.com/string-representations/

 

String Representations for Classes

All Python objects have two different string representations, although we almost always use just one of them. You can customize both of these string representation on your Python objects.

www.pythonmorsels.com

 

 

 

 

 

5. 정리


반복적인 문자열을 처리할 때는
join함수를 이용하되,
미리 리스트를 만들어 두고 처리하자!

이상으로 포스팅을 마치겠습니다.
도움이 되셨다면 댓글과 하단의 하트 한 번씩 부탁드립니다.
감사합니다.
반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,

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

 

 

 

 

 

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

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

 

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


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

 

반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘은 level 1 "기사단원의 무기" 문제 풀어보겠습니다.
효율적으로 약수의 개수를 구하는 방법이 중요한 문제입니다.

 

 

 

 

 

해당 문제 바로가기 링크 ↓↓↓

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

 

1. 약수의 개수 구하는 함수 만들기


def get_cds(n, limit , power):
    cnt = 0
    for i in range(1, int(n**(1/2))+1): # ★포인트1. 제곱근만큼만 반복
        if n%i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2 # 제곱근이 아닐 경우, 2개 카운트 (i, n//i)
        if cnt > limit:  # ★포인트2. 소수의 개수가 limit를 넘어가면
            return power #            강제로 power만큼을 return 
    return cnt
약수의 개수를 구하는 함수에서 중요한 포인트는 2가지 입니다.

첫번째로, for문을 돌릴 때, int(제곱근)까지만 반복하는 것 입니다.
예를 들어, 18의 제곱근은 4.xxx정도가 나옵니다.
for문을 돌리면 1, 2, 3, 4가 각각 18의 약수인지를 볼 것입니다.
[1, 2, 3]이 각각 카운트되고, 18을 각각의 약수들로 나눈 [18, 9, 6]도 카운트 됩니다.

18의 제곱근 이상 반복하는 것은 의미가 없습니다.
반복문이 돌아 6이 나온다고 해도, 이미 약수에 추가가 되어 있기 때문입니다.
여기서 6을 추가하면, 중복카운트 이므로 정답이 아니게 됩니다.
두 번째 포인트는, 문제의 제한조건을 활용하는 것입니다.
문제에서, 약수의 개수가 특정 숫자를 넘어가면,
강제로 power만큼으로 고정하라는 조건이 나옵니다.


제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는
협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다.


그렇기에 cnt의 개수가 limit을 넘어가면
for문이 더 돌 필요도 없이, 강제로 power를 리턴하고 종료하는 것입니다.
limit과 power는 get_cds의 파라미터로 받았습니다.
반응형

 

 

 

 

2.  전체 정답 공개


def get_cds(n, limit , power):
    cnt = 0
    for i in range(1, int(n**(1/2))+1): # ★포인트1. 제곱근만큼만 반복
        if n%i == 0:
            if i == n//i: # 제곱근일 경우 -> 1개만 카운트하기
                cnt += 1
            else:
                cnt += 2 # 제곱근이 아닐 경우, 2개 카운트 (i, n//i)
        if cnt > limit:  # ★포인트2. 소수의 개수가 limit를 넘어가면
            return power #            강제로 power만큼을 return 
    return cnt

    
def solution(number, limit, power):
    total = 1
    for i in range(2, number+1):
        len_cds = get_cds(i, limit, power)
        total += len_cds

    return total
solution 부분은 단순히 약수들의 개수를 합산해주는 부분이라,
보고 이해하시기 어렵지 않으실 것 입니다.
도움이 되셨다면 하단의 하트 부탁드립니다! 

모두 코딩테스트를 통과하는 그날까지 화이팅!

 

반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘은 프로그래머스 유한소수 판별하기 문제 풀어보겠습니다.

문제를 풀기 위해 알아야 할 개념은 크게 2가지 입니다.
1. 유클리드 호제법 (최대공약수)
2. 소인수 분해

소인수 분해를 사용하지 않고 푸는 방법도 있는데,
가장 깔끔한 풀이법이었습니다.
해당 정답 공개 후, 문제 풀이 시작하겠습니다.

 

 

 

 

 

프로그래머스 문제 바로 가기 ↓↓↓ 링크 클릭

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

 

 

1. 정답 공개


from math import gcd
def solution(a, b):
    b //= gcd(a,b)
    while b%2==0:
        b//=2
    while b%5==0:
        b//=5
    return 1 if b==1 else 2
gcd는 최대공약수(Greatest Common Divisor, GCD)를 의미합니다.
파이썬의 math 라이브러리에 내장되어 있는 기본 함수를 사용했습니다.
(실제 코딩테스트에서 사용 가능 가능할지는 모르겠네요... 알아두면 개꿀이니 숙지는 해야겠습니다)

이후 분모(b)를 최대공약수로 나누고
각각 2와 5로 나누어 떨어진다면, while문에 진입합니다.
최종적으로 b가 1인지 아닌지를 return합니다.

소인수분해를 사용하지 않은 대신,
while문을 각각 사용한 것이 인상적이었습니다.

 

 

 

 

 

그러나 만약 math 함수를 쓰지 말라고 한다면?
면접에서 최대공약수 구하는 과정을 설명해보라 한다면?
왜 분모를 최대공약수로 나누는지 이유는?

그렇기 때문에 최대공약수를 구하는 유클리도 호제법
소인수 분해에 대한 알고리즘을 꼭 아셔야 합니다!

 

 

 

 

 

2. 유클리드 호제법 (최대공약수 구하기)


간단한 문제를 통해 유클리드 호제법이 무엇인지 살펴보았습니다.
유클리드 호제법은 2가지만 기억하시면 됩니다.

① 다음 단계에서 분모는 분자가 된다.
② 다음 단계에서 나머지는 분모가 된다.
이제 유클리드 호제법을 코드로 구현해 보겠습니다.

 

 

 

 

 

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)
재귀함수를 이용하여 유클리드 호제법을 구현하였습니다.

① 다음 단계에서 분모분자가 된다. -> ba자리에 왔습니다.
② 다음 단계에서 나머지분모가 된다. -> a%bb자리에 왔습니다.

나머지가 0으로 나누어 떨어지면?
그것이 바로 최대공약수입니다.

 

 

 

 

 

3. 소인수 분해


def factorization(x):
    d = 2
    output = []
    
    while d <= x:
        if x % d == 0:
            output.append(d)
            x /= d
        else:
            d += 1
            
    return output
위의 코드는 소인수분해를 함수로 구현한 것입니다.
변수 d는 2부터 시작하여, 원래 input으로 주어진 x까지 반복됩니다.

그러나 x 또한 고정된 것이 아니라 변화합니다.
d로 나누어 떨어지면, 나누어 떨어진 몫을 x로 대체합니다. (x /= d)

마지막으로 반환되는 output은 소인수분해에 사용된
소수들을 담고 있습니다.

 

 

4. 유클리드 호제법 + 소인수분해를 이용한 풀이법


def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

def factorization(x):
    d = 2
    output = []
    
    while d <= x:
        if x % d == 0:
            output.append(d)
            x /= d
        else:
            d += 1
            
    return output
    
def solution(a, b):
    divide_num = gcd(b, a)
    result = b // divide_num
    
    for num in factorization(result):
        if num not in [2, 5]:
            return 2
    return 1
마지막 solution 파트에 대해서만 설명드리겠습니다.
최대 공약수를 구한 뒤, b를 최대공약수로 나누게 되면,
기약분수가 적용된 분모의 형태를 띄게 됩니다. (result)

그 이후는 문제에서 준 힌트와 동일합니다.
분모를 소인수 분해한 뒤, 2 또는 5 이외의 소인수가 나오는지 체크하는 과정입니다.
만약 하나라도 2 또는 5가 아니라면 무한 소수입니다.

for문에서 return되지 않고 끝까지 간다면?
유한소수이기 때문에 1을 return해주면 됩니다.

 

 

 

 

 

5. 마무리


개인적인 생각이지만,
이런 종류의 문제는 암기하고 많이 익숙해지는게 정답인 듯 합니다.
유클리드 호제법과 소인수분해를 알아야 수월하게 풀 수 있습니다.

어떻게 보면 마냥 모니터 앞에서 고민하는게 정답이 아닐 수도 있습니다.
사전 지식이 잘 탑재되어 있으면 쉽게 해결될 문제가 많습니다.
다만 차이가 있다면.. 힘들게 푼 문제가 기억에 오래 남는다 정도?
(그냥 여러 번 풀고 익히는게 더 기억에 오래 남을수도 있습니다)

그러니 알고리즘 문제를 풀다가 너무 답이 안나오면
해답을 보는 것도 괜찮은 방법입니다 :)
오늘은 이만 마치겠습니다. 수고하셨습니다.

 

반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘 풀어볼 문제는 "햄버거 만들기" 라는 문제입니다.

고민해 볼 포인트가 많은 문제인데요,
리스트의 일부를 효율적으로 제거하는 방법이 중요합니다.
이에 대해서 중점적으로 설명드리겠습니다.

 

 

해당 문제 바로가기 ↓↓↓ 아래 링크 클릭

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

 

1. 정답 공개

바로 정답 공개하도록 하겠습니다.
그 이후에 시간초과가 걸리는 코드와 정답으로 통과한 코드를 비교해 보겠습니다.
먼저, 사람들이 가장 많이 채택한 정답입니다.
def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            for _ in range(4):
                s.pop()
    return cnt

 

 

 

 

다음으로 시간초과로 통과할 수 없는 코드를 보여드리겠습니다.
위의 코드와 동일하나, 딱 한 줄이 다릅니다.
def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            s = s[:-4] # 해당 부분으로 인해 시간 초과 발생
    return cnt

 

 

 

 

 

2. Pop() 함수에 대한 이해

input_list = [1, 2, 3, 1]
input_list.pop()
print(input_list)
output
------------------------------------
[1, 2, 3]
.pop() 함수를 통해 리스트의 일부 요소를 제거할 수 있습니다.
[리스트 데이터].pop()을 사용하게 되면, 해당 리스트의 맨 마지막 요소가 제거됩니다.
이 때, 별도 변수에 리스트를 다시 할당할 필요가 없습니다.

 

 

 

input_list = [1, 2, 3, 1]
input_list.pop(0)
print(input_list)
output
------------------------------------
[2, 3, 1]
pop() 함수 안에 파라미터를 지정할 수도 있습니다.
pop 함수 안에 제거하고 싶은 리스트 요소의 인덱스 번호를 넣어주면,
리스트의 해당 요소만 제거됩니다.

위의 예시에서 pop안에 0이라고 했기 때문에,
리스트의 0번 index인 1이 제거되었습니다.

 

 

 

input_list = [1, 2, 3, 1]
a = input_list.pop(0)
print(input_list)
print('a:', a)
output
---------------------------------------
[2, 3, 1]
a: 1

 

리스트에서 튀어나온(pop) 녀석을 변수에 할당할 수도 있습니다.
위의 코드에서 튀어나온 녀석을 a라는 변수에 할당했는데요,
그래서 a의 값은 1이 됩니다.

 

 

 

def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            for _ in range(4):
                s.pop()
    return cnt
다시 정답 코드로 돌아가 봅시다.
리스트의 마지막 4요소가 [1, 2, 3, 1] 이면, pop함수가 4번 실행되는 구조입니다.
따로 pop 함수에 인덱스를 지정해주지 않았기 때문에,
자동으로 마지막 요소가 4번 튀어나가 제거되는 원리입니다.

 

 

 

 

 

3. 다른 풀이 (del 이용)

del 함수를 이용하여 리스트의 일부를 강제로 지울 수도 있습니다.
시간은 실행할 때마다 달라져서, 비교가 어렵네요...
pop 보다 del을 이용하는게 더 코드가 짧습니다.
def solution(ingredient):
    s = []
    cnt = 0
    for i in ingredient:
        s.append(i)
        if s[-4:] == [1, 2, 3, 1]:
            cnt += 1
            del s[-4:]
    return cnt

 

 

 

 

 

4. 마무리

오늘 문제에서 가장 중요한 포인트는
리스트에서 특정 요소를 제거하는 방법입니다.

리스트 슬라이싱을 사용하지 않고
pop이나 del을 이용하여 제거하는 방법을 익혀두시길 바랍니다.

도움이 되셨다면 하단의 하트 한 번씩 부탁드립니다!
감사합니다.

 

반응형
블로그 이미지

pychan

딥러닝에 관련된 시행착오, 사소하지만 중요한 것들, 가능한 모든 여정을 담았습니다.

,