Q1. 모험가 길드
난이도: ⭐
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: 핵심 유형
'공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
예를 들어 N=5이고, 각 모험가의 공포도가 2 3 1 2 2라고 가정했을 때, 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두 명을 넣게 되면, 총 2개의 그룹을 만들 수 있다.
또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 모험가의 수 N이 주어진다. (1 <= N <= 100,000)
- 둘째 줄에 각 모험가의 공포도의 값은 N 이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.
출력 조건
- 여행을 떠날 수 있는 그룹 수의 최댓값을 출력한다.
# 입력 예시
5
2 3 1 2 2
# 출력 예시
2<내가 푼 방식>
- 공포도가 큰 순서대로 리스트 정렬
- 공포도가 1이면 혼자 가기 => 리스트에서 삭제
- 반복문을 돌려서(가장 큰 공포도 <= 여행 떠날 수 있는 모험가 수) 가장 큰 공포도만큼 한 그룹으로 묶어준다.
n = int(input())
fear = list(map(int, input().split()))
result = 0
# 공포도가 큰 순서대로 정렬
fear = sorted(fear, reverse=True)
for i in range(n):
# 공포도가 1이면 혼자 가기
if fear[i] == 1:
#first_one = i
#result += n - i
result += 1
del fear[i]
# 공포도가 큰 순서대로 정렬했으므로 0번 인덱스가 공포도가 가장 큰 사람
max_fear = fear[0]
# 가장 큰 공포도 수 만큼 모험가를 한 그룹으로 묶어주기
while max_fear <= len(fear): # max_fear 수 보다 사람이 적으면 그룹 못 만듦
max_fear = fear[0]
del fear[0:max_fear]
result += 1
if len(fear) == 0: break
print(result)<답안>
- 공포도 오름차순 정렬
- 공포도가 가장 낮은 모험가부터 하나씩 확인하면서 그룹에 포함될 모험가의 수 계산
- 만약 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹 결성!
공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹 결성
➡️ 따라서 최대한 많은 그룹이 구성되는 방법이므로, 항상 최적의 해를 찾을 수 있음
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 # 그룹 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in data: # 공포도가 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
print(result)Q2. 곱하기 혹은 더하기
난이도: ⭐
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: Facebook 인터뷰
각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.
입력 조건
- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다. (1 <= S의 길이 <= 20)
출력 조건
- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.
예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 (((0 + 2) x 9) x 8) x 4) = 576이다.
또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.
# 입력 예시 1
02984
# 출력 예시 1
576
# 입력 예시 2
567
# 출력 예시 2
210<내가 푼 방식>
- result를 문자열 첫 번째 숫자로 초기화
- 반복문을 range(1, len(s))로 돌림 - 문자열 인덱스 1번부터 마지막까지
- 연속하는 두 수(이전에 저장된 result와 이번 인덱스에 해당하는 수)를 더했을 때의 값과 곱했을 때의 값을 비교해서 더 큰 값을 result에 저장
s = list(map(int, input())) # 공백 없이 입력 받기
plus = 0 # 연속하는 두 수를 더한 경우의 값
mul = 0 # 연속하는 두 수를 곱한 경우의 값
result = s[0]
for i in range(1, len(s)):
plus = result + s[i]
mul = result * s[i]
if plus >= mul:
result = plus
else:
result = mul
print(result)<답안>
📌 두 수 중에서 하나라도 1 이하인 경우에는 더하기, 두 수가 모두 2 이상인 경우에는 곱하기
data = input()
# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])
for i in range(1, len(data)):
# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)Q3. 문자열 뒤집기
난이도: ⭐
풀이 시간: 20분
시간 제한: 2초
메모리 제한: 128MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/1439
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 잇는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다.
예를 들어 S = 0001100일 때,
- 전체를 뒤집으면 1110011
- 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있음
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하세요.
입력 조건
- 첫째 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력 조건
- 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.
# 입력 예시
0001100
# 출력 예시
1<내가 푼 방식> - ❗틀림❗
- 앞의 숫자와 현재 숫자가 같으면 continue
- 다를 경우, index가 0이면 현재 인덱스 i를 index에 저장. index가 0이 아니면 index부터 i-1까지 숫자 뒤집기
❗책의 예시는 맞았지만, 백준 예시에서 틀림
s = list(map(int, input()))
index = 0 # 앞 인덱스의 숫자와 이번 인덱스의 숫자가 다를 때, 이번 인덱스 저장
result = 0
for i in range(1, len(s)):
if s[i - 1] == s[i]:
continue
else:
if index == 0:
index = i
else:
if s[i] == 1:
for j in range(index, i):
s[j] = 1
else:
for j in range(index, i):
s[j] = 0
result += 1
print(result)- 앞의 숫자와 현재 숫자가 같으면 continue
- 다르면 0번 인덱스부터 앞의 인덱스까지 숫자 뒤집기
s = list(map(int, input()))
result = 0
for i in range(1, len(s)):
if s[i - 1] == s[i]:
continue
else: # 앞의 숫자와 현재 숫자가 다르면
if s[i] == 1:
for j in range(0, i): # 0번 인덱스부터 i-1까지 숫자 뒤집기
s[j] = 1
else:
for j in range(0, i):
s[j] = 0
result += 1
print(result)<답안>
📌 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산
data = input()
count0 = 0 # 전부 0으로 바꾸는 경우
count1 = 0 # 전부 1로 바꾸는 경우
# 첫 번째 원소에 대해서 처리
if data[0] == '1':
count0 += 1
else:
count1 += 1
# 두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
if data[i] != data[i + 1]:
# 다음 수에서 1로 바뀌는 경우
if data[i + 1] == '1':
count0 += 1
# 다음 수에서 0으로 바뀌는 경우
else:
count1 += 1
print(min(count0, count1))Q4. 만들 수 없는 금액
난이도: ⭐
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: K 대회 기출
N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에는 동전 개수를 나타내는 양의 정수 N이 주어진다. (1<=N<=1,000)
- 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다. 이때, 각 화폐 단위는 1,000,000 이하의 자연수이다.
출력 조건
- 첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.
# 입력 예시
5
3 2 1 1 9
# 출력 예시
8예를 들어, N=5이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리 동전이라고 가정한다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 8원이다.
또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원짜리 동전이라고 가정한다. 이때 만들 수 없는 양의 정수 금액 중 최솟값은 1원이다.
<내가 푼 방식>
- 동전으로 만들 수 있는 경우를 전부 리스트에 넣은 후, 중복된 원소 제거, 작은 수 부터 정렬
- 반복문 돌려서 리스트 원소 하나씩 확인하면서 만들 수 없는 금액 중 최솟값 찾기
이렇게 풀면 안될듯...🙄
<답안>
- 화폐 단위를 기준으로 오름차순 정렬
- 이후에 1부터 차례대로 특정한 금액을 만들 수 있는지 확인 ➡️ 1부터 target-1까지의 모든 금액을 만들 수 있다고 가정
- 현재 확인하는 동전을 이용해 target 금액을 만들 수 있는지 확인 ➡️ 만약 target 금액을 만들 수 있다면, target 값을 업데이트(증가시킴)
📌 현재 상태를 1부터 target-1까지의 모든 금액을 만들 수 있는 상태라고 했을때, 매번 target인 금액도 만들 수 있는지(현재 확인하는 동전의 단위가 target 이하인지) 체크하는 것. 만약 만들 수 있다면, target의 값을 업데이트(현재 상태를 업데이트)
n = int(input())
data = list(map(int, input().split()))
data.sort()
target = 1
for x in data:
# 만들 수 없는 금액을 찾았을 때 반복 종료
if target < x:
break
target += x
print(target)Q5. 볼링공 고르기
난이도: ⭐
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: 2019 SW 마에스트로 입학 테스트
A,B 두 사람이 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다.
두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어진다. (1<=N<=1,000, 1<=M<=10)
- 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다. (1<=K<=M)
출력 조건
- 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.
# 입력 예시 1
5 3
1 3 2 3 2
# 출력 예시 1
8
# 입력 예시 2
8 5
1 5 4 3 2 4 5 2
# 출력 예시 2
25예를 들어 N=5, M=3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여된다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 아래와 같다.
(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)
결과적으로 두 사람이 공을 고르는 경우의 수는 8가지!
<내가 푼 방식>
-
이중 반복문
- 바깥 반복문: 볼링공의 개수인 N만큼 반복
- 안 반복문: 현재 원소부터 마지막 원소까지 반복
-
안 반복문에서 현재 원소와 뒤에 있는 원소들을 비교해서 무게가 다르면 result 1 증가시킨다.
n, m = map(int, input().split())
k = list(map(int, input().split()))
result = 0
for i in range(n):
for j in range(i, n):
if k[i] != k[j]:
result += 1
print(result)<답안>
-
무게마다 볼링공이 몇 개 있는지 계산한다.
- 볼링공 무게가 1~10까지만 존재할 수 있다고 명시되어 있으므로, 리스트 변수를 선언해서 각 무게별로 볼링공 개수 기록
-
A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 계산한다.
- A를 기준으로 무게가 낮은 볼링공부터 순서대로 하나씩 확인한다.
n, m = map(int, input().split())
data = list(map(int, input().split()))
# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11
for x in data:
# 각 무게에 해당하는 볼링공의 개수 카운트
array[x] += 1
result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
result += array[i] * n # B가 선택하는 경우의 수와 곱해주기
print(result)반복문 안에 있는 result += array[i] * n을 위 문제의 예시를 기준으로 보면 아래와 같다.
1) A가 무게가 1인 공을 선택할 때의 경우의 수: 1(무게가 1인 공의 개수) x 4(B가 선택하는 경우의 수) = 4가지 경우
2) A가 무게가 2인 공을 선택할 때의 경우의 수: 2(무게가 2인 공의 개수) x 2(B가 선택하는 경우의 수) = 4가지 경우
3) A가 무게가 3인 공을 선택할 때의 경우의 수: 2(무게가 3인 공의 개수) x 0(B가 선택하는 경우의 수) = 0가지 경우
Q6. 무지의 먹방 라이브
난이도: ⭐
풀이 시간: 30분
시간 제한: 1초
메모리 제한: 128MB
기출: 2019 카카오 신입 공채
링크: https://programmers.co.kr/learn/courses/30/lessons/42891
📍 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 풀어야 한다!
회전판에 먹어야 할 N개의 음식이 있다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.
- 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
- 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
- 회전판이 다음 음식을 무지 앞으로 가져오는 데 걸리는 시간은 없다고 가정한다.
무지의 먹방을 시작한 지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는 데 필요한 시간이 담겨 있는 배열 food_times, 네트워크 장애가 발생한 시간 K초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하시오.
제한 사항
- food_times : 각 음식을 모두 먹는 데 필요한 시간이 음식의 번호 순서대로 들어 있는 배열
- k : 방송이 중단된 시간
- 만약 더 섭취해야 할 음식이 없으면 -1 return
정확성 테스트 제한 사항
- food_times 길이는 1 이상 2,000 이하
- food_times 원소는 1 이상 1,000 이하 자연수
- k는 1 이상 2,000,000 이하 자연수
효율성 테스트 제한 사항
- food_times 길이는 1 이상 200,000 이하
- food_times 원소는 1 이상 100,000,000 이하 자연수
- k는 1 이상 2 x 10^13 이하의 자연수
입출력 예시
| food_times | k | result |
|---|---|---|
| [3,1,2] | 5 | 1 |
입출력 예시에 대한 설명
- 0~1초 동안에 1번 음식을 섭취. 남은 시간은 [2,1,2]
- 1~2초 동안에 2번 음식을 섭취. 남은 시간은 [2,0,2]
- 2~3초 동안에 3번 음식을 섭취. 남은 시간은 [2,0,1]
- 3~4초 동안에 1번 음식을 섭취. 남은 시간은 [1,0,1]
- 4~5초 동안에 (2번 다 먹었으므로) 3번 음식을 섭취. 남은 시간은 [1,0,0]
5초에서 네트워크 장애가 발생했다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 된다.
<내가 푼 방식>
k초를 range로 반복문을 돌려서
현재 음식 번호에 해당하는 food_times의 원소의 시간을 -1
현재 음식 번호(answer)를 + 1씩 증가 => 마지막 번호를 벗어나면 다시 1로
현재 음식 번호에 해당하는 food_times의 원소 시간이 0이면
현재 음식 번호를 1 증가 => 원소 시간을 -1
for문 끝나고 현재 음식 번호에 시간이 0이 아니면 현재 번호 출력
0이면 0이 아닌 다음 번호 출력
def solution(food_times, k):
answer = 1 # 현재 음식 번호
for i in range(k + 1):
# 마지막 번호의 음식을 섭취한 후 다시 1번 음식
if answer > len(food_times):
answer = 1
# 현재 번호의 음식을 다 먹은 상태라면 남아있는 음식 번호 찾기
while(1):
if food_times[answer - 1] == 0:
answer += 1
else: break
# 네트워크 장애가 생겼을 때 중단
if i == k:
break
# 현재 번호의 음식을 섭취하고 시간을 -1
food_times[answer - 1] -= 1
# 회전판을 돌려 다음 음식을 가져오기
answer += 1
return answer<해설>
📌 시간이 적게 걸리는 음식부터 확인하는 그리디 방식으로 해결
- 모든 음식을 시간 기준으로 정렬
- 시간이 적게 걸리는 음식부터 제거
➡️우선순위 큐
우선순위 큐를 구현하기 위해 heapq를 이용 - 다익스트라 알고리즘 파트에 설명
step 0)
- 모든 음식을 우선순위 큐(최소 힙)에 삽입
- (음식 시간, 음식 번호) 튜플 형태로 삽입
step 1)
- 가장 적게 걸리는 음식을 뺀다.
- (남은 음식의 개수) x (뺀 음식을 먹는 시간)을 K초에서 뺀다. (= 남은 시간)
step 2)
- K초에서 (남은 음식의 개수) x (뺀 음식을 먹는 시간) > 남은 시간일 때 '다음으로 먹어야 할' 음식의 번호를 찾는다. (아니라면 step 1 반복)
남은 시간 + 1번째 음식 번호를 출력한다.
import heapq
def solution(food_times, k):
# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
if sum(food_times) <= k:
return -1
# 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
q = []
for i in range(len(food_times)):
# (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
heapq.heappush(q, (food_times[i], i + 1))
sum_value = 0 # 먹기 위해 사용한 시간
previous = 0 # 직전에 다 먹은 음식 시간
length = len(food_times) # 남은 음식의 개수
# sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
while sum_value + ((q[0][0] - previous) * length) <= k:
now = heapq.heappop(q)[0]
sum_value += (now - previous) * length
length -= 1 # 다 먹은 음식 제외
previous = now # 이전 음식 시간 재설정
# 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
return result[(k - sum_value) % length][1]