[PROGRAMMERS] 완전탐색 뽀개기 | 파이썬 | 프로그래머스 완전탐색 문제풀이

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

프로그래머스

 

Lv1. 모의고사

1번 수포자부터 3번 수포자까지 답을 찍는 패턴(규칙)이 정해져있다. 정답 배열이 주어지면 가장 문제를 많이 맞춘 학생을 반환한다.

점수가 같을 경우(답을 여러명 반환해야할 경우) 오름차순으로 정렬하여 반환한다.

 

내 코드)

def solution(answers):
    answer = []
    
    student1 = [1, 2, 3, 4, 5] # 5
    student2 = [2, 1, 2, 3, 2, 4, 2, 5] # 8
    student3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] # 10
    
    score = [0, 0, 0]
    
    for i in range(len(answers)):
        if student1[i % 5] == answers[i]:
            score[0] += 1
        if student2[i % 8] == answers[i]:
            score[1] += 1
        if student3[i % 10] == answers[i]:
            score[2] += 1
        
    max_score = max(score)
    for i in range(3):
        if max_score == score[i]:
            answer.append(i+1)
            
    return answer

각 수포자의 패턴에 따른 정답지를 먼저 만들어놓고 주어진 정답 배열과 각 수포자의 정답지를 채점한다.

점수는 answer 배열에 저장한 뒤 가장 높은 점수(max_score)와 점수가 같은 수포자들의 번호(answer 배열의 인덱스)를 반환한다.

 

 

Lv2. 소수찾기

입력된 숫자 numbers를 구성하는 숫자들로 만들 수 있는 수들 중 소수가 몇개인지 찾아 반환하라.

 

내 코드)

import itertools, math

def solution(numbers):
    answer = 0
    numbers = [str(n) for n in numbers]
    nums = set()
    
    for i in range(1, len(numbers)+1):
        for p in set(itertools.permutations(numbers, i)):
            num = int(''.join(p))
            if num > 1:
                nums.add(num)
    
    for num in nums:
        ck = True
        for i in range(2, int(math.sqrt(num))+1):
            if num % i == 0:
                ck = False
                break
        if ck:
            answer += 1
        
    return answer

숫자 1과 7이 주어졌을 때 17과 71은 다른 숫자이다. 숫자들에서 요소를 고를 때 순서가 의미있음으로 순열(itertools.permutations)을 이용했다.

순열로 numbers에서 나올 수 있는 모든 경우의 수를 구해서 num에 저장한다. 그리고 하나씩 꺼내 소수인지 아닌지 판단하여 소수일 때 정답에 카운트한다.

원래 반복문이 중간에 안멈추고 다 돌았는지 판단하기 위해 보통 마지막 인덱스값으로 확인하였지만 그냥 ck라는 변수를 둬서 이를 확인했다.

* 소수인지 판별할 때 굳이 2부터 N까지 반복문을 돌지 않고 N^(1/2)까지만 검사해도 된다. 가운데를 대칭으로 짝을 이루는 약수 성질때문!

 

 

Lv2. 카펫

갈색 타일은 테두리에만 칠해지고 안의 직사각형 모양의 타일들은 모두 노란색이다.

전체 타일 영역의 높이가 height, 너비가 weight일 때 가장 테두리의 길이와 안의 노란색 영역 테두리의 길이는 아래와 같다.

갈색 타일의 개수는 ( 2*width + 2*height - 4 )이고 노란색 타일 개수는 ( height-2 ) * ( width-2 )이다.

갈색과 노란색 타일 개수가 주어졌을 때 전체 타일영역의 높이와 너비를 구하여라. 단 너비가 항상 높이보다 길다.

 

내 코드) 

def solution(brown, yellow):
    h = 3
    while True:
        w = int((brown+4-2*h)/2)
        Y = (w-2) * (h-2)
        if (Y==yellow):
            return [max(w, h), min(h, w)]
        h += 1

너비는 주어진 갈색 타일 수와 노란 타일 수 그리고 높이에 대한 식으로 바꿀 수 있다. 이렇게하면 좌변에서 변수는 h(높이)만 남는다.

노란색 타일은 너비와 높이의 식으로 나타낼 수 있고 최소 높이인 3부터 대입해가며 주어진 노란색 타일 수와 일치한지 검사한다.

주어진 값들에 맞는 높이와 너비가 되면 정답을 반환한다.

노란색 타일을 갈색 타일들이 둘러싸고 있어야함으로 높이의 최솟값은 3이다.

 

다른 사람 코드) 

import math
def solution(brown, yellow):
    w = ((brown+4)/2 + math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    h = ((brown+4)/2 - math.sqrt(((brown+4)/2)**2-4*(brown+yellow)))/2
    return [w,h]

변수도 width, height 2개로 정리할 수 있고 갈색과 노란색 타일 수가 주어지기 때문에 주어진 식도 2개라 이차방정식으로 풀 수 있다.

위 코드는 다른 사람이 이차방정식을 풀기 위해 근의 공식을 이용한 풀이