📍 이것이 코딩테스트다(나동빈) - part3.알고리즘 유형별 기출문제 를 풀고 기록했습니다.
1. 모험가 길드
- 공포도가 X인 모험가는 반드시 X명 이상의 모험가와 그룹이 되어 마을을 떠난다.
- 몇 명의 모험가는 마을에 그대로 남아있어도 된다.
- 첫째 줄에 모험가의 수 N이 입력됨(1<=N<=100,000)
- 둘째 줄에 각 모험가의 공포도가 N이하의 자연수로 주어지며, 공백으로 구분되어 입력됨.
출력조건) 여행을 떠날 수 있는 그룹 수의 최댓값은?
1.1 내 답안
- ⏳ 50분 소요
- 모험가를 공포도 기준으로 내림차순 정렬했고
search(n, list): n을 그룹에 포함시킬 때, 최대 그룹수 구하는 함수 생성- 모든 모험가에 대해 해당 모험가가 그룹에 포함되었을 때, 최대 그룹수를 구해서 result에 갱신함.
def search(n, list):
# n 이 그룹에 포함될 때, 최대 그룹수를 구하는 함수
count = 0
# 초기 list는 공포도가 n이하인 모험가만
list = [i for i in list if i<=n]
while len(list)>= n:
count += 1
list = list[n:]
if not list:
break
n = list[0]
return count
n = int(input())
array = list(map(int, input().split()))
# array 정렬
array.sort(reverse=True)
result = 0
# 모든 모험가에 대해 해당 모험가가 그룹에 포함되었을 때, 최대 그룹수를 구해서 갱신함.
for i in array:
result = max(search(i, array), result)
print(result)
1.2 책 답안
- 항상 최소한의 모험가의 수만 포함하여 그룹을 만들기 = 최대한 많은 수의 그룹 만들기
- 공포도를 기준으로 오름차순 정렬함
- (현재 확인하고 있는 공포도) <= (현재 만들어진 그룹 길이) 이라면 이를 바로 그룹으로 설정.
- 예를 들어 공포도가 [1,2,2,2,3]이면
- [1] > 그룹 결정 > [2] > [2,2] > 그룹 결정
- 최대 2개 그룹이 만들어짐.
- 만약 공포도를 기준으로 내림차순 정렬하여 이 방법 쓴다면, 최소한의 모험가 수만 포함하여 그룹 만들지 못함.
- 여기까지 읽고 짜본 코드
n = int(input())
data = list(map(int, input().split()))
data.sort()
count = 0
group = []
for i in data:
group.append(i)
if i <= len(group):
count += 1
group = []
print(count)
- 책 코드
- group생성해서 len(group) 구하는 것 보다
- count로 계산하는 게 더 간단하군
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)2. 곱하기 혹은 더하기
- 각 자리가 숫자(0부터 9)로만 이루어진 문자열 s가 주어졌을 때
(1<=s의 길이<=20)- 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '*' 또는 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수 구하기
2.1 내 답안
- ⏳ 5분 소요
s = list(input()) # 문자열을 리스트화
s = list(map(int, s)) # 숫자로 변환
result = 0
for i in s:
result = max(result+i, result*i)
print(result)
2.2 책 답안
- 두 수에 대해 연산을 수행할 때 곱하기할 때가 더 큰 경우, 더하기가 더 큰 경우를 나눈다.
- 두 수 중, 0과 1이 포함되어있을 때는 곱하기보다 더하기를 할 때 더 큰 수가 나옴.
- 두 수 중에서 하나라도 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)
3. 문자열 뒤집기
- 0과 1로만 이뤄진 문자열 s가 입력됨 (s의 길이는 100만 보다 작음)
- s 에서 연속된 하나 이상의 숫자를 뒤집을수 있다. (0에서 1로, 1에서 0으로)
- 숫자를 뒤집어서 모두 같은 숫자로 만들고자 할 때, 최소로 뒤집는 횟수는?
3.1 내 답안
- ⏳ 10분 소요
- s에서 1로 이루어진 묶음 수, 0으로 이루어진 묶음 수 구함.
- 연속된 수는 한 개로 셈
- 예를 들어
10011001은- 1로 이루어진 묶음 수 : 4
- 0으로 이루어진 묶음 수 : 2
- 오류 : s가 모두 같은 숫자인 상태일 떄
s = input()
count = [0,0] # 0묶음 수, 1묶음 수 (연속된 수는 한 개로 셈)
now = int(s[0])
count[now] += 1
for i in range(1, len(s)):
num = int(s[i])
if now != num:
# (i-1번째수now)와 (i번째수num)가 다르면 (i번째 수에 해당하는 묶음수)에 1 추가
count[num] += 1
now = num
print(min(count))
3.2 책 답안
- i 번째와 i+1 번째를 비교해서 count하는게 헷갈려서 묶음수로 계산했는데
- 묶음수가 아니라 '전부 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))
DEEP DIVER