[PROGRAMMERS] 프로그래머스 코딩테스트 연습 > 완전탐색 파이썬 문제풀이

프로그래머스 코딩테스트 연습 > 고득점 kit > 완전탐색 파트 문제풀이 파이썬 https://programmers.co.kr/learn/courses/30/parts/12230

프로그래머스

 

 

모의고사 (Level 1)

 내 코드 

def solution(answers):
    answer = []
    n = len(answers)
    
    p1 = [1, 2, 3, 4, 5] # 5
    p2 = [2, 1, 2, 3, 2, 4, 2, 5] # 8
    p3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] # 10
    
    a1, a2, a3 = 0, 0, 0
    
    for i in range(n):
        if answers[i] == p1[i % 5]: 
            a1 += 1
        if answers[i] == p2[i % 8]: 
            a2 += 1
        if answers[i] == p3[i % 10]: 
            a3 += 1

    answer.append((1, a1))
    answer.append((2, a2))
    answer.append((3, a3))
        
    max_p = max(answer, key=lambda x: x[1])
    max_list = list(filter(lambda x: x[1] == max_p[1], answer))
    idx_list = list(map(lambda x: x[0], max_list))

    return idx_list

학생 3명의 반복되는 답안 패턴을 미리 지정해두고 답안 패턴의 길이가 정해져있음으로 나머지 연산자를 이용하여 인덱스를 구해 정답과 학생들의 답을 비교하였다.

이후 학생번호와 맞춘 답변 개수를 튜플 형태로 리스트에 추가한 뒤 최대 정답수를 가진 학생들의 번호를 필터로 구하였고 튜플들에서 학생 인덱스만 꺼내 문제를 해결하였다.

직관적이긴 하나 내가 실력이 됐다면 코드를 더 간결하게 쓸 수 있었을 것 같다.

 

* filter(함수, 데이터) : 특정 조건(주어진 함수)을 만족하는 요소들 iterator 객체 만들어 반환, 함수의 결과가 참인지 거짓인지에 따라 요소로 포함할지 결정

target = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# target의 요소들 중 주어진 람다 함수를 만족하는 객체만 반환
result = filter(lambda x : x % 2==0, target) # [2, 4, 6, 8, 10]

 

 다른 사람 코드 1 

def solution(answers):
    p = [[1, 2, 3, 4, 5],
         [2, 1, 2, 3, 2, 4, 2, 5],
         [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    s = [0] * len(p)

    for q, a in enumerate(answers):
        for i, v in enumerate(p):
            if a == v[q % len(v)]:
                s[i] += 1
    return [i + 1 for i, v in enumerate(s) if v == max(s)]

 다른 사람 코드 2 

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

 

 

소수 찾기 (Level 2)

각 숫자를 조합하여 만들 수 있는 모든 경우의 수를 생각해야하기 때문에 순열 관련 라이브러리가 필수인 듯 하다.

 

 내 코드 

from itertools import permutations

def solution(numbers):
    answer = []

    nums = list(map(int, numbers))
    length = len(nums)

    perms = []
    for i in range(1, length + 1):
        perms.extend(list(permutations(nums, i))) # 순열
    
    num_list = set()
    for p in perms:
        p = tuple(map(str, p)) # 튜플의 숫자 이어서 숫자 생성
        num = int(''.join(p))
        if num > 1:
            num_list.add(num) # 0과 1 제외

    for n in num_list:
        if is_prime_number(n): 
            answer.append(n)

    return len(answer)

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False 
    return True

 

 다른 사람 코드1 

from itertools import permutations

def solution(numbers):
    nums = set()

    for i in range(len(numbers)):
        # 순열로 생성한 튜플을 바로 join으로 하나의 문자열로 만든 뒤 map(int, )로 바로 변환
        nums |= set(map(int, map("".join, permutations(list(numbers), i + 1)))) # 합집합
        
    nums -= set(range(0, 2)) # 0-1 제외

    # 에라토스테네스 체
    for i in range(2, int(max(nums) ** 0.5) + 1): # 집합에서 가장 큰 수의 sqrt
        nums -= set(range(i * 2, max(nums) + 1, i)) # i의 배수 집합 제외

    return len(nums)

map() 이용하여 for문을 작성하지 않고 코드를 짧게 줄일 수 있다.

 

* 에라토스테네스 체 : 대표적인 소수 판별 알고리즘으로 대량의 소수를 한꺼번에 판별하고자할 때 사용

[참고] https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

이전의 내 코드의 시간복잡도는 O(n)

def is_prime_number(x):
    for i in range(2, x):
        if x % i == 0:
            return False 
    return True

에라토스테네스의 체 코드

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

1. 찾고자하는 수까지 초기화된 배열 생성

2. 2를 제외한 2의 배수, 3을 제외한 3의 배수 ... sqrt(n)을 제외한 sqrt(n) 배수를 모두 false로 전환

3. 2에서 n인 수까지 true인 수만 반환

 

 다른 사람 코드 2 

primeSet = set()

def isPrime(number):
    if number in (0, 1):
        return False
    for i in range(2, number):
        if number % i == 0:
            return False

    return True

def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])

def solution(numbers):
    makeCombinations("", numbers)
    answer = len(primeSet)

    return answer

재귀를 사용하여 가능한 모든 조합으로 숫자 생성

 

 

카펫 (Level 2)

문제의 실행예시 설명

모양은 항상 사각형으로 만들어지며 전체 가로 세로 길이는 노란색 타일로 이뤄진 사각형 가로 세로 길이에 +2씩 한 것(상하 좌우 한줄씩 갈색이 추가됨으로)

 

 내 코드 

def solution(brown, yellow):
    # 전체 가로세로 길이 = 노란색 가로세로 길이 + 2

    answer = []

    # 1. 노란색 타일 수의 약수 튜플 리스트 -> 만들어질 수 있는 사각형의 형태
    divisors = []
    for i in range(1, int(yellow ** (1/2) + 1)): # (가로, 세로) 가로 >= 세로
        if yellow % i == 0:
            divisors.append((int(yellow/i), i))

    # 2. 갈색 타일의 수 계산
    for d in divisors:
        brown_cnt = 0
        print(d)
        brown_cnt += (d[0] + 2) * 2 # 가로 2줄
        brown_cnt += (d[1]) * 2 # 세로 2줄

        if brown_cnt == brown:
            # 3. 알맞은 타입의 사각형일때 정답 도출
            answer = (d[0]+2, d[1]+2)
            return answer

예시를 직접 그려보며 이해하니 쉽게 규칙을 찾을 수 있었다.

1. 노란색 타일은 내부에서 사각형의 모양을 이루고 있음으로 약수 쌍이 가로 세로 길이 쌍이 될 수 있다.

   (여기서 중요한 점은 가로 길이가 세로 길이보다 같거나 길고 정답을 반환할 때 가로 길이가 앞에 와야함으로 큰 수를 앞으로 둘 것)

2. 노란색 타일의 사각형을 갈색 사각형이 둘러싸고 있음으로 갈색 타일의 가로 길이는 노란색 타일 가로 길이의 +2, 세로 길이는 노란색 타일 세로 길이와 동일하며 각각 *2하여 더해준다(반대로 적용 가능).

3. 계산한 갈색 타일의 수가 주어진 갈색 타일의 수와 동일할 때 가로, 세로 길이에 2씩 더해주어 전체 사각형의 크기를 구한다.

 

 다른 사람 코드 

def solution(brown, red):
    for i in range(1, int(red**(1/2))+1):
        if red % i == 0:
            if 2*(i + red//i) == brown-4:
                return [red//i+2, i+2]

이렇게 짧게도 가능하다니............