[프로그래머스] - 시저 암호, 스킬트리, 후보키, 타겟 넘버, N진수 게임

시저 암호

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

from string import ascii_lowercase, ascii_uppercase

def solution(s, n):
    answer = ''
    upper = list(ascii_uppercase)
    lower = list(ascii_lowercase)
    for i in s:
        if i in upper:
            idx = upper.index(i)
            answer += upper[(idx + n)%len(upper)]
        elif i in lower:
            idx = lower.index(i)
            answer += lower[(idx + n)%len(lower)]
        else:
            answer += " "
    return answer

• 느낀점
  • 간단한 문자열 구현 문제
  • 대문자, 소문자 리스트를 가져올때 ascii 라이브러리 이용하기.
  • 다른 사람 풀이보니 ord 이용해서 풀었음

스킬트리

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

from collections import defaultdict

def solution(skill, skill_trees):
    answer = 0
    dic = defaultdict(int) # 스킬네임: 번호
    for i in range(len(skill)):
        dic[skill[i]] = i
    for skill_tree in skill_trees:
        temp = []
        flag = True
        for s in skill_tree:
            if s in skill:
                if not temp and dic[s] == 0: # 맨처음 스킬이라면
                    temp.append(dic[s])
                elif dic[s] - 1 in temp: # 이전 스킬이 잇다면
                    temp.append(dic[s])
                else:
                    flag = False
                    break
        if flag:
            answer += 1
     
    return answer

# 다른사람 풀이
def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

• 느낀점
  • 위상정렬 느낌나서 그렇게 해서 풀려다가 오히려 꼬여서 힘들었던 문제
  • 그냥 간단하게 생각해 각 스킬 순서대로 인덱스를 부여하여 해당 스킬을 배웠는지 체크하여 품
  • 다른사람 풀이보니 더 간단하게 그냥 skill을 리스트로 만들어 pop하면서 바로 비교하면서 품

후보키

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

from itertools import combinations

def solution(relation):
    answer = 0
    row = len(relation)
    col = len(relation[0])
    
    combi = [] # 컬럼의 가능한 조합 리스트
    for i in range(1, col + 1):
        for com in list(combinations(range(col), i)):
            combi.append(com)
    
    unique = []
    for com in combi:
        temp = [tuple([r[i] for i in com]) for r in relation]
        flag = True
        if len(set(temp)) == row: # 유일성 검사
            for u in unique:
                if set(u).issubset(com): # 최소성 검사
                    flag = False
                    break
            if flag:
                unique.append(com)
                
    return len(unique)

• 느낀점
  • 완탐 (combination)을 이용하는 구현 문제
  • row, col이 매우 작기 때문에 조합 라이브러리를 이용해서 완탐해도 됨
  • 유일성 검사는 set을 이용해 길이가 변화하는지를 체크했는데 최소성 검사에서 매우 애먹었음
  • https://velog.io/@sem/프로그래머스-LEVEL2-후보키-Python
  • 그러다 다른 사람 풀이에서 issubset 을 이용해서 최소성 검사를 하는걸 보고 품

타겟 넘버

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

def solution(numbers, target):
    global answer
    answer = 0
    
    def dfs(start, temp): # 시작 인덱스, 중간 합계
        global answer
        
        if start >= len(numbers):
            if temp == target:
                answer += 1
            return
        
        dfs(start + 1, temp + numbers[start])
        dfs(start + 1, temp - numbers[start])
    
    dfs(0, 0)
    
    return answer

# 다른사람 풀

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

• 느낀점
  • 정석적인 dfs 문제
  • 매개변수에 시작 인덱스와, 중간 합계를 두어 numbers 배열을 다 돌았을 때 그 합계가 타겟넘버와 일치하는지 비교함
  • 다른 사람은 재귀로 풀었는데 엄청 간단하다.

N진수 게임

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

def solution(n, t, m, p):
    answer = ''
    s = ""
    number = 0
    while len(s) <= t * m:
        for i in parse(number, n):
            s += i
        number += 1
        
    idxs = [i*m + (p-1) for i in range(t)]
    for idx in idxs:
        answer += s[idx]
    return answer

def parse(num, n):
    alpha = ["A", "B", "C", "D", "E", "F"]
    result = ""
    if num == 0:
        return "0"
    
    while num > 0:
        num, mod = divmod(num, n)
        if mod >= 10: # 10진수 이상의 수라면
            result += alpha[mod % 10]
        else:
            result += str(mod)
    return result[::-1]

• 느낀점
  • n진수로 변환하여 구현하는 문제
  • n진수 변환 시 divmod 라는 것을 이용해 몫 과 나머지 바로 구해서 구현함