매 순간 가장 좋은 선택을 하고, 그 선택들이 모여 최종적인 결과가 최적해이길 기대하는 그리디 알고리즘, 개념 자체는 간단하지만 최적해를 도출하는 방법을 찾고 방법의 정당성을 검증하는 과정에서 오랜 시간이 소요되었던 거 같다.
또한 혹여나 발생할 수 있는 시간 초과를 대비하여 입력값을 받을 때 기존에 사용하던 input()이 아닌 sys.stdin.readline()을 사용하는 데 익숙해지려 노력 중이다. 여기서 주의해야 할 점은 sys.stdin.readline() 같은 경우 개행 문자 /n가 포함되기 때문에, 이를 없애기 위해 split, rstrip, 형 변환 등을 이용해주어야 한다.
11047 : 동전 0
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 가 오름차순으로 주어진다. (1 ≤ ≤ 1,000,000, = 1, i ≥ 2인 경우에 -1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
풀이
가장 큰 화폐 단위부터 가능한 최대로 사용하는 방식으로 문제를 풀면 된다. 동전의 가치를 오름차순으로 입력 받았기 때문에, 가장 큰 화폐 단위부터 사용하기 위해서는 내림차순으로 다시 정렬을 해준다.
가장 큰 화폐 단위부터 순서대로 K를 나누어 몫만큼 count에 더해주고, 나머지는 새로운 k 값으로 정의한다. 최종적으로는 몫을 더해준 count의 값을 출력한다.
코드
import sys
n, k = map(int, sys.stdin.readline().split())
coin_types = [int(sys.stdin.readline()) for _ in range(n)]
count = 0
coin_types.sort(reverse=True)
for coin in coin_types:
count += k // coin
k %= coin
print(count)1339 : 단어 수학
민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.
단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.
예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.
N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.
출력
첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.
풀이
처음에는 접근 방법이 쉽게 떠오르지 않았던 문제. 뭔가 간단해 보이면서도 정확한 해결 방안이 생각나지 않았다. 따라서 사용할 수 있을 것 같은 키워드를 먼저 고민해 보았을 때 생각난 것이 다음의 세 가지였다.
Keyword
딕셔너리, 인덱스 비교, 큰 값부터 차례대로 할당
문제에서 주어진 예시 외에 다른 예시들을 떠올리며 생각을 해보았다.
만약, ABCD + CDE + FG라면
- A는 천의 자리 수이기 때문에 1000
- B는 백의 자리 수이기 때문에 100
- C는 백의 자리 수, 십의 자리 수이기 때문에 110
- D는 십의 자리 수, 일의 자리 수이기 때문에 11
- E는 일의 자리 수이기 때문에 1
- F는 십의 자리 수이기 때문에 10
- G는 일의 자리 수이기 때문에 1
을 주고, 숫자를 내림차순으로 정렬한 뒤 9부터 순서대로 값을 할당해 주면 된다. 마지막으로 할당된 값과 각 숫자를 곱해서 더하면 문제에서 요구한 합의 최댓값을 도출할 수 있다.
위 기준에 따른 숫자를 할당하기 위하여 딕셔너리를 이용했다. 각 알파벳이 key가 되고, 할당된 숫자(1000, 100 등)는 value가 된다. 값을 할당할 때는 1, 10, 100, 1000 등 할당되는 값 자체가 10의 제곱수라는 점을 이용하여, 10 ** (문자열의 길이 - 알파벳의 인덱스 - 1)과 같은 식으로 구했다.
마지막으로 value를 기준으로 큰 값부터 차례대로 정렬을 해준 뒤에, 9부터 내림차순으로 곱하고 그 모든 값을 더해 출력한다.
코드
import sys
n = int(sys.stdin.readline())
word_list = [sys.stdin.readline().strip() for _ in range(n)]
alphabet = []
count_dict = {}
result = 0
for word in word_list:
for a in word:
alphabet.append(a)
for a in set(alphabet):
count_dict[a] = 0
for word in word_list:
for i, a in enumerate(word):
count_dict[a] += 10 ** (len(word) - i - 1)
sorted_values = sorted(count_dict.values(), reverse=True)
for i in range(len(sorted_values)):
result += sorted_values[i] * (9 - i)
print(result)1946 : 신입사원
언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.
그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.
이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.
출력
각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
| 2 5 3 2 1 4 4 1 2 3 5 5 7 3 6 7 3 4 2 1 4 5 7 2 5 6 1 | 4 3 |
풀이
신입사원으로 채용될 수 있는 기준이 명확하게 제시된 문제이다. 하지만 이 기준 자체를 예시에 적용할 때는 헷갈리는 부분들이 있어, 여러 예시들을 생각해보며 기준이 적용되는 과정을 구체적으로 파악하려 했던 거 같다.
시도 1
처음에는 모든 지원자들을 비교하여 기준에 맞지 않는 사람들을 채용되지 않는 not_employee 리스트에 추가한 뒤, 전체 지원자의 수에서 채용되지 않는 지원자의 수를 뺀 값을 구했다.
하지만 이러한 방식은 모든 지원자의 서류심수 성적 및 면접 성적을 비교하고, 해당 지원자가 not_employee 리스트에 있는지까지 확인하는 반복문이 계속되는 동시에 이중 for 문으로 인해 시간적인 측면에서 비효율적이었던 것 같다. 결국 시간 초과로 인해 오답 처리 되었다.
시도 2
서류심사 성적 순으로 정렬을 한 뒤에 면접 성적을 비교해 채용하는 방법을 생각해보았다. 서류심사 성적 순으로 정렬을 하게 되면 1등을 제외한 다른 지원자들은 면접 성적이 좋아야 채용될 수 있다.
따라서 정렬된 리스트를 기준으로 차례대로 면접 성적을 비교하고, 면접 성적이 더 높아 채용이 된다면 top 값을 갱신해주어 (서류 기준) 후순위 지원자들과의 명확한 비교가 가능하도록 만들어줬다.
코드
시도 1 (시간 초과)
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
applicant = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
not_employee = []
for a in applicant:
for b in applicant:
if b[0] > a[0] and b[1] > a[1] and b not in not_employee:
not_employee.append(b)
print(len(applicant) - len(not_employee))시도 2
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
applicant = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(n)])
top = 0
employee_num = 1
for j in range(len(applicant)):
if applicant[j][1] < applicant[top][1]:
top = j
employee_num += 1
print(employee_num)