프로그래머스 - k진수에서 소수 개수 구하기, 피로도, n^2 배열 자르기

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

• 사이트/난이도: 프로그래머스 / 2
• 코드

import math

def solution(n, k):
    answer = 0
    s = parse(n, k)
    arr = s.split("0")
        
    for a in arr:
        if a == '': 
            continue
        if check_prime(int(a)):
            answer += 1
    return answer

def parse(n, k):
    result = ""
    while n != 0:
        result += str(n % k)
        n = n // k
    return result[::-1]

def check_prime(n):
    if n <= 1:
        return False 
    for i in range(2, int(math.sqrt(n) + 1)):
        if n % i == 0:
            return False
    return True

• 느낀점
  • 쉬운 구현 문제
  • 하지만 소수 판별할 때 제곱근 까지 제한해서 판단하지 않고 n-1까지 하면 시간초과 남
  • 그리고 “0”으로 split후 빈 문자열 ‘’ 이 있을수도 있으니 해당 조건 추가하기

피로도

• 사이트/난이도: 프로그래머스 / 2
• 코드

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    for combs in list(permutations(dungeons,len(dungeons))):
        temp = k
        result = 0
        for first, second in combs:
            if temp >= first:
                temp -= second
                result += 1
        answer = max(answer, result)
    return answer

# 백트랙킹
answer = 0
n = 0
visited = []
def dfs(k, result, dungeons):
    global answer
    if result > answer:
        answer = result
        
    for i in range(n):
        if k >= dungeons[i][0] and not visited[i]:
            visited[i] = 1
            dfs(k - dungeons[i][1], result + 1, dungeons)
            visited[i] = 0
    
def solution(k, dungeons):
    global n, visited, answer
    n = len(dungeons)
    visited = [0] * n
    dfs(k, 0, dungeons)
    return answer

• 느낀점
  • 던전의 최대 길이가 8이기 때문에 완탐으로 해도 시간복잡도 안걸리는 문제
  • 이를 위해 익숙한 방식인 순열을 이용해서 하나씩 비교하면서 풀었음
  • 다른 사람은 백트랙킹으로 풀길래 해당 코드를 참고해서 나도 백트랙킹으로 풀어봤음
  • 여기서 전역변수를 함수 내부에서 사용시에 global로 명시해야 되는거 같음.

n^2 배열 자르기

• 사이트/난이도: 프로그래머스 / 2
• 코드

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        row = i // n
        col = i % n
        answer.append(max(row, col) + 1)
    return answer

• 느낀점
  • n의 크기가 천만까지이므로 해당 1차원 배열을 만드려고 이중포문 쓰면 바로 시간초과 난다.
  • 직접 만들지 말고, 규칙성이 있으므로 left, right+1 까지의 숫자를 받아서 row, col로 바꾼뒤 답에 추가하면 풀린다
  • 규칙성은 row, col 을 구한후 더 큰 값에 +1 해주면 해당 1차원 배열의 값과 같다.