브루트 포스
2503 - 숫자야구
민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.
소스 코드
import itertools
# 1. 숫자 야구에 사용할 수 있는 모든 경우의 수
baseball_list = list(itertools.permutations([i for i in range(1, 10)], 3))
for _ in range(int(input())):
number, strike, ball = map(int, input().split())
number = list(map(int, str(number))) # 2. int로 입력받은 숫자를 자릿수마다 나눠서 리스트에 저장
temp = list()
for baseball in baseball_list:
s_cnt, b_cnt = 0, 0
for i in range(3):
if number[i] in baseball:
if number[i] == baseball[i]:
s_cnt += 1
else:
b_cnt += 1
if strike == s_cnt and ball == b_cnt:
temp.append(baseball)
baseball_list = temp
print(len(baseball_list))
설명
숫자 야구에서 나올 수 있는 모든 경우의 수에서 입력받은 number, strike, ball의 조건에 맞는 정답이 될 수 있는 조합만 남기는 방법을 사용
-
1~9까지의 숫자를 중복 없이 조합하지만 순서에 따라 strike와 ball이 다르기 때문에 순열(perminations)을 사용한다.
-
한 행에서 number, strike, ball을 모두 입력받아 int자료형으로 바꾸었기 때문에 123 -> [1, 2, 3]으로 바꾸어 아래 코드에서 오류없이 작동하도록 자료형을 바꾼다.
반복문을 돌면서 입력받은 number의 요소가 경우의 수에 존재하고 위치도 같다면 strike_count를 증가, 위치는 다르다면 ball_count를 증가
입력받은 strike, ball과 count가 같다면 해당 경우의 수는 답이 될 수 있는 후보이기 때문에 이를 temp(임시) 리스트에 저장
그렇게 해서 모은 정답 후보 리스트를 모든 경우의 수로 바꾸고 2번째 입력부터는 정답 후보 리스트 중 정답 범위를 좁히는 목적으로 위 과정을 반복
반복문을 종료하고 baseball_list에 저장된 값이 정답 가능성이 있는 값들이다.
2231 - 분해합
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
소스 코드
import sys
n = int(sys.stdin.readline())
for a in range(1, n):
sum = 0
for i in str(a):
sum += int(i)
if (a + sum) == n:
print(a)
break
else:
print("0")
설명
1 부터 입력받은 숫자까지 반복하면서 해당 숫자와 숫자의 각 자릿수를 더한 값이 n이 되면 결과를 출력하고 break를 사용해 반복문을 종료한다. 이는 생성자가 여러 개일 경우 가장 작은 생성자를 찾았기 때문에 반복문을 더 돌릴 필요가 없다.
for-else 구문은 else절은 for문을 모두 반복하고 나서 동작하는 원리인데 생성자가 존재한다면 break로 인해 반복문 중간에 종료되기 때문에 else절이 동작하지 않지만 생성자가 없을 경우 반복문을 모두 동작하고 0을 출력한다.
모의고사
1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.
소스 코드
def solution(answers):
one=[1,2,3,4,5]
two=[2,1,2,3,2,4,2,5]
three=[3,3,1,1,2,2,4,4,5,5]
cnt_solve=[0,0,0]
for i, answer in enumerate(answers):
if one[i%len(one)]==answer:
cnt_solve[0]+=1
if two[i%len(two)]==answer:
cnt_solve[1]+=1
if three[i%len(three)]==answer:
cnt_solve[2]+=1
max_cnt=max(cnt_solve)
answer = []
for i, value in enumerate(cnt_solve):
if value==max_cnt:
answer.append(i+1)
return answer설명
1, 2, 3번 수포자가 찍는 방식은 규칙을 가지고 반복하기 때문에 규칙의 한 주기를 각각 저장
index, value를 같이 반환하는 enumerate와 반복하는 수포자의 찍는 방식 리스트를 나머지를 구하는 것으로 answer의 index와 동일한 위치의 찍은 답을 도출하여 비교한다.
가장 많이 문제를 맞힌 사람은 여러 명일 수 있기 때문에 반복문을 사용하여 맞힌 숫자와 가장 많이 많힌 숫자가 같다면 해당 사람을 결과 리스트에 저장
그리디 알고리즘
11047 - 동전 0
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
소스 코드
n, k = map(int, input().split())
coin = []
for _ in range(n):
coin.append(int(input()))
coin.sort()
result = 0
while k != 0:
if k >= coin[-1]:
result += k // coin[-1]
k = k % coin[-1]
coin.pop()
print(result)
설명
입력받은 동전의 가치를 coin 리스트에 저장, 오름차순으로 정렬
오름차순으로 정렬되어 있기 때문에 coin[-1]은 리스트 중 동전의 가치가 가장 높은 값
가장 높은 값보다 k가 크거나 같다면 해당 동전의 최대 개수를 저장(누적)
동전의 가치가 k보다 크거나 작거나 해당 반복문을 돌면 삭제(coin[-1]을 k보다 작은 가장 큰 동전의 가치로 유지하기 위함)
11399 - ATM
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
소스 코드
n = int(input())
atm_time = list(map(int, input().split()))
accum = []
sum_time = 0
atm_time.sort()
for i in atm_time:
sum_time += i
accum.append(sum_time)
print(sum(accum))
설명
accum: 각 사람의 누적 시간을 저장
Pi를 오름차순으로 정렬, 앞 사람의 시간이 적게 걸릴수록 시간의 합이 작아진다.
반복문을 돌면서 accum에 누적시간을 저장하고 이를 더한 값을 출력
1931 - 회의실 배정
사용할 수 있는 회의의 최대 개수를 출력한다.
소스 코드
meeting_time = []
for _ in range(int(input())):
meeting_time.append(list(map(int, input().split())))
meeting_time.sort(key=lambda x: (x[1], x[0]))
end_time = 0
result = 0
for start, end in meeting_time:
if start >= end_time:
result += 1
end_time = end
print(result)설명
회의 정보를 meeting_time 리스트에 저장
list.sort(key=lambda x: x)를 사용하여 정렬의 우선순위를 두고 정렬이 가능하다.
회의가 끝나는 시간을 기준으로 오름차순으로 정렬을 하고 끝나는 시간이 같다면 시작시간이 더 빠른 회의가 앞에 오도록 (x[1], x[0])을 사용하여 2개의 우선순위를 가진 정렬을 한다.
회의 정보를 반복하면서 회의 시작시간이 기존에 저장한 회의가 끝나는 시간과 같거나 크다면 결과값을 증가하고 해당 회의의 끝나는 시간을 end_time에 저장한다.
