프로그래머스 문제 3,4

피로도

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다. “최소 필요 피로도”는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, “소모 피로도”는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 “최소 필요 피로도”가 80, “소모 피로도”가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

입력: k = 80, dungeons = [[80,20],[50,40],[30,10]]

출력: 3

내 풀이

def solution(k, dungeons):
    num_dungeon = []
    def dfs(iteration, k, dungeons):       
        for i, dungeon in enumerate(dungeons):
            if dungeon[0] <= k:                
                num_dungeon.append(dfs(iteration+1, k-dungeon[1], dungeons[:i]+dungeons[i+1:]))
                
        return iteration
     
    dfs(0, k, dungeons)
    return max(num_dungeon)

• dfs 방법으로 풀었다.
• dfs 함수에 재귀로 넘겨주는 인수는 (반복한 횟수+1, 현재 피로도, 남은 던전 리스트) 이다.
• num_dungeon은 각각의 경우에 해당하는 반복 횟수를 담은 리스트로, 최대 값을 리턴한다.

결과

정확성: 100.0
합계: 100.0 / 100.0

---

k진수에서 소수 개수 구하기

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

• 0P0처럼 소수 양쪽에 0이 있는 경우
• P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
• 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
• P처럼 소수 양쪽에 아무것도 없는 경우
• 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
  • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다. 정수 n과 k가 매개변수로 주어집니다. n을 k진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.

입력: 110011, 10

출력: 2

설명: 110011을 10진수로 바꾸면 110011d이다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 로 총 2개. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 한다.

내 풀이

def solution(n, k):
    converted = ''
    # k 진수로 바꿈
    while n > 0:
        n, rem = divmod(n, k)
        converted = str(rem) + converted
    
    # 소수를 찾는 함수
    def checkprime(num):
        if num == 1:
            return 0
        
        for i in range(2, num//2+2 if num%2 == 1 else num//2+1):
            if num%i == 0:
                return 0
        return 1
    
    # k 진수로 바꾼 문자열을 반복하면서 소수 여부를 찾는다.
    prime_count = 0
    prev_num = ''
    for c in converted:
        if c != '0':
            prev_num += c
            
        elif len(prev_num) != 0:
            prime_count += checkprime(int(prev_num))
            prev_num = ''
    
    if prev_num != '':
        prime_count += checkprime(int(prev_num))
        
    return prime_count

• 먼저 n을 k진수로 변경한다.
• 소수를 찾는 함수를 정의한다. 이 함수는 (해당 숫자)//2 만큼 반복하면서 iterator로 해당 숫자를 나누었을떄 0이 나오면 0을 리턴하고, 반복문을 통과하면 1을 리턴한다.
• k진수로 변경한 숫자를 반복하면서 0이 나오면 지금까지 나온 숫자를 저장한 prev_num의 소수 여부를 판단한다.
• 첫번째 테스트 케이스에 대한 결과가 시간초과였는데, 소수를 찾는 함수 checkprime에서 반복문을 실행하는데 너무 오래 걸려서 발생하였다. num//2+2 if num%2 == 1 else num//2+1 이 아닌 int(num**0.5)+1 만큼 반복하면 시간초과 에러가 해결된다.

결과

정확성: 88.1
합계: 88.1 / 100.0

풀이 1

def solution(n, k):
    word=""
    while n:            # 숫자를 k진법으로 변환
        word = str(n%k)+word
        n=n//k
        
    word=word.split("0")  # 변환된 숫자를 0을 기준으로 나눈다.
    
    count=0
    for w in word:
        if len(w)==0:    # 만약 0또는 1이거나 빈공간이라면 continue를 통해 건너뛴다.
            continue
        if int(w)<2:
            continue
        sosu=True
        for i in range(2,int(int(w)**0.5)+1): # 소수찾기
            if int(w)%i==0:
                sosu=False
                break
        if sosu:
            count+=1
            
    return count

• 소수로 변경하는 부분은 내 풀이 방법과 동일하다.
• 소수를 찾기 위해 k진수로 바꾼 소수에 split 함수를 적용하여 0을 기준으로 나눈다.
• 소수 여부를 판별할때 반복을 (해당 숫자의 제곱근 + 1)을 한 만큼 하였다.