99클럽 코테 스터디 23일차 TIL / 완전탐색

✏️ 문제

[프로그래머스/Programmers] 소수 찾기(https://school.programmers.co.kr/learn/courses/30/lessons/42839)

 

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: 프로그래머스 Level.2

✅ 소요 시간: 20분

✅ 권장 시간: 1시간 15분

 

피로도 문제의 DFS 풀이를 참고해서 푼 거라 소요 시간+30~35분 정도 해야 100% 내 힘으로 푼 시간으로 칠 수 있을 것 같다.

 

💡 풀이

1) 문제 이해

어제 푼 피로도 문제와 동일하게 문제에 적힌대로 쭉 구현하면 되는 문제다. numbers가 최대 길이로 들어올 경우 13,699개의 조합을 만들 수 있고 완전탐색으로 충분히 처리 가능한 범위이다.

 

피로도 문제 때처럼 permutations 함수를 쓰면 금방 풀렸겠지만 너무 내장 함수에 의존하는 것 같아 이번에는 DFS 알고리즘으로 풀어봤다.

 

2) 아이디어 흐름

문제 풀이를 위해 아주 러프하게 떠올린 구현 흐름은 아래와 같다. 일단 큰 틀만 정리했기 때문에 매우 간단함!

 

① 주어진 numbers 문자열로부터 나올 수 있는 숫자 모두 만들기

 

② 소수 판별 알고리즘 구현

 

③ 소수 판별 알고리즘을 이용해 만들어진 숫자 확인

 

④ 전체 소수 개수 출력

 

3) DFS의 역할 및 작동 방식

1️⃣ 역할

DFS는 2)-① 과정에서 쓰인다. 좀 더 풀어서 설명하면 '숫자를 이어 붙여 가능한 조합을 생성하는 역할'을 하는 것이다.

 

재귀를 통해 한 자리 수, 두 자리 수, ... 처럼 점차 길이를 늘려가며 numbers 문자열에서 새로운 숫자를 찾아 나간다. 즉 DFS 알고리즘을 이용해 permutations 함수 없이 가능한 모든 숫자를 만들 수 있다.

 

2️⃣ 작동 방식

• DFS 함수는 현재 만든 숫자, 남은 숫자를 인자로 받고 이때 두 인자의 자료형은 모두 문자열
• 현재 만든 숫자가 빈 문자열이 아니라면 숫자 후보 집합에 추가
• 현재 만든 숫자와 남은 숫자를 활용해 DFS 함수 재귀적으로 호출

# DFS 호출 흐름

numbers = "123"
candidates = set()

def DFS(path, remaining):
    if path:
        candidates.add(int(path))

    for i in range(len(remaining)):
        DFS(path + remaining[i], remaining[:i] + remaining[i+1:])

DFS("", numbers)

print(candidates)

 

DFS("", "123"): path가 빈 문자열이기 때문에 바로 for문 실행

DFS("1", "23"): path는 빈 문자열이 아니기 때문에 candidates 집합에 1 추가

DFS("12", "3"): candidates 집합에 12 추가

DFS("123", ""): candidates 집합에 123 추가

 

위의 과정을 반복하면서 numbers 문자열에서 나올 수 있는 모든 숫자가 만들어지게 된다.

 

4) 소수 판별 알고리즘

소수 판별은 에라토스테네스의 체를 활용하면 된다.

 

나는 소수 관련 문제를 풀 때 보통 전체 소수 리스트를 만들어두는데 이 문제에서는 좀 더 빠른 처리를 위해 다른 방식을 써봤다. 하나라도 나누어지는 수가 있으면 False를 리턴해서 함수를 바로 빠져나오고, 미리 빠져나오지 못하면 True를 리턴해서 소수로 분류하는 방식을 썼다.

 

5) 구현

def is_prime(number):
    if number < 2:
        return False
    else:
        for i in range(2, int(number**0.5)+1):
            if number%i == 0:
                return False
        
        return True
    
def solution(numbers):
    answer = 0
    
    # DFS로 숫자 생성(permutations 함수를 안 쓰는 방법)
    def DFS(current_num, remaining):
        nonlocal candidates
        
        if current_num:
            candidates.add(int(current_num))
            
        for i in range(len(remaining)):
            DFS(current_num+remaining[i], remaining[:i]+remaining[i+1:])
    
    candidates = set()
    
    DFS("", numbers)
    
    for num in candidates:
        if num != 0 and is_prime(num):
            answer += 1
            
    return answer

 

6) 어려웠던 점/배운 점

🚨 어려웠던 점

• 참고할 코드가 없었다면 DFS 알고리즘으로 가능한 모든 조합을 만드는 과정을 떠올리는 게 쉽지 않았을 것 같다. - 오늘은 permutations 함수를 쓰지 않고 완전탐색 문제를 하나 더 풀어봐야겠다.

❗ 배운 점

• nonlocal 키워드의 의미!