기출 3일차 | 볼링공 고르기, 무지의 먹방 라이브
📍 이것이 코딩테스트다(나동빈) - part3.알고리즘 유형별 기출문제 를 풀고 기록했습니다.
1. 볼링공 고르기
- 총 N개의 볼링공이 있다. (1<=N<=1,000)
- 각 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. (1<=M<=10)
- N개의 볼링공 무게가 공백으로 구분되어 입력된다.
- 무게가 다른 볼링공 2개를 고르는 조합은?
단, 무게가 같더라도 다른 공으로 간주한다. 예를들어 5개의 볼링공의 무게가 [1, 3, 2, 3, 2]로 주어질 때, 두 번째 볼링공과 네 번째 볼링공은 서로 다른 공이다.
1.1 내 답안
- ⏳ 10분 소요
- 모든 조합의 경우의 수를 nC2로 구하고
- 1부터 M까지의 무게별로 중복 횟수를 기록함. (count)
- 같은 무게를 뽑는 경우의 수를 제외함.
# 모든 조합 경우의수(nC2) - 같은 무게 뽑는 경우의 수
n, m = map(int, input().split())
data = list(map(int, input().split()))
result = int(n*(n-1)/2) # 모든 조합의 경우의 수
count = [0]*(m+1) # 무게별 중복 횟수 기록
for x in data:
count[x] += 1
for i in range(1,m+1):
if count[i] > 1 :
result -= int(count[i]*(count[i]-1)/2)
print(result)
2.2 책 답안
- 먼저 무게마다 볼링공이 몇 개가 있는지 계산하고
- 예를 들어
- 무게가 1인 볼링공 : 1개
- 무게가 2인 볼링공 : 2개
- 무게가 3인 볼링공 : 2개
- 무게가 낮은 볼링공부터 확인하면.(조합)
- 무게가 1인 볼링공을 선택하는 경우의 수 : 1*4
- 무게가 2인 볼링공을 선택하는 경우의 수 : 2*2
- 무게가 3인 볼링공을 선택하는 경우의 수 : 2*0
- 이중 for문으로 만들거라 생각했는데 (총 볼링공 개수=n)을 순차적으로 줄이면서 경우의 수 구했음
n, m = map(int, input().split())
data = list(map(int, input().split()))
# 1부터 10까지의 무게를 담을 수 있는 리스트(m범위)
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인 볼링공의 개수 제외
result += array[i]*n # (무게가 i인 볼링공 개수)*(무게 i 초과인 공들의 개수)
print(result)
2. 무지의 먹방 라이브
- 총 N개의 볼링공이 있다. (1<=N<=1,000)
- 각 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. (1<=M<=10)
- N개의 볼링공 무게가 공백으로 구분되어 입력된다.
- 무게가 다른 볼링공 2개를 고르는 조합은?
단, 무게가 같더라도 다른 공으로 간주한다. 예를들어 5개의 볼링공의 무게가 [1, 3, 2, 3, 2]로 주어질 때, 두 번째 볼링공과 네 번째 볼링공은 서로 다른 공이다.
# 모든 조합 경우의수(nC2) - 같은 무게 뽑는 경우의 수
n, m = map(int, input().split())
data = list(map(int, input().split()))
result = int(n*(n-1)/2) # 모든 조합의 경우의 수
count = [0]*(m+1) # 무게별 중복 횟수 기록
for x in data:
count[x] += 1
for i in range(1,m+1):
if count[i] > 1 :
result -= int(count[i]*(count[i]-1)/2)
print(result)
- 무게가 1인 볼링공 : 1개
- 무게가 2인 볼링공 : 2개
- 무게가 3인 볼링공 : 2개
- 무게가 1인 볼링공을 선택하는 경우의 수 : 1*4
- 무게가 2인 볼링공을 선택하는 경우의 수 : 2*2
- 무게가 3인 볼링공을 선택하는 경우의 수 : 2*0
n, m = map(int, input().split())
data = list(map(int, input().split()))
# 1부터 10까지의 무게를 담을 수 있는 리스트(m범위)
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인 볼링공의 개수 제외
result += array[i]*n # (무게가 i인 볼링공 개수)*(무게 i 초과인 공들의 개수)
print(result)
프로그래머스 링크 : https://programmers.co.kr/learn/courses/30/lessons/42891?language=python3
- 회전판에 무지가 먹어야할 음식이 N개 있다. 각 음식에는 1부터 N까지 번호가 붙어있다.
- 각 음식을 섭취하는데 일정 시간이 소요된다.
- 무지는 1번부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
- 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
- 회전판이 다음 음식을 무지 앞으로 가져오는 데 걸리는 시간은 없다고 가정한다.
- 무지가 먹방을 시작한지 k초 후에 네트워크 장애로 방송이 잠시 중단되었다. 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는 데 필요한 시간이 담겨 있는 배열 food_times, 네트워크 장애가 발생한 시간 k초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는기 return하도록 solution함수를 완성하라.
- 만약 더 섭취해야할 음식이 없다면 -1을 반환한다.
정확성 테스트 제한 사항
- 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 이하의 자연수
2.1 내 답안
- 첫 번째 답안(틀림)
def solution(food_times, k):
answer = 0
#n번 째에 j번째를 섭취했다면 (n+1)번째는 (j+1)%len(food_times )
count = 0
n = len(food_times)
if min(food_times) >= k:
return (k-1)%n+1
while count <= k:
if sum(food_times) == 0:
return -1
if food_times[answer]:
food_times[answer] -= 1
count += 1
answer = (answer+1)%n
return answer
- 두번째 답안 (틀림)
def solution(food_times, k):
answer = 0
n = len(food_times)
not_0 = len(food_times) # 0이 포함되지 않은 음식 개수
# k< not_n 또는 k < len(food_times )이 될 때까지 계속 먹음
while k>= not_0 and k>= n:
k -= not_0
food_times = [x-1 for x in food_times if x != 0]
not_0 = len([x for x in food_times if x != 0])
# k < not_0 또는 k < len(food_times)인 상황
while k >= 0:
if food_times[answer%n]:
food_times[answer%n] -= 1
k -= 1
if k == -1:
break
answer += 1
answer = answer%n + 1
return answer
2.2 책 답안
- 우선순위 큐를 사용하여 (음식 시간, 음식 번호) 을 시간을 기준으로 정렬 가능.
- while문은 다 먹는 음식을 제거해 나가는 과정.
- sum_value와 previous의 차이가 뭐냐?
- q =
[(4, 3번), (6, 2번), (8, 1번)]
이고, k=15일 때 - 가장 처음 3번 음식이 동나고
sum_value
=4(초)*3(length)= 12,previous
= 4(초)가 됨. - 이후 큐는 q =
[((6-previous)=2, 2번), ((8-previous)=4, 1번)]
- q =
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 # 이전 음식 시간 재설정. (+= now가 아님 주의)
# 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
result = sorted(q, key =lambda x: x[1]) # 음식의 번호 기준으로 정렬
return result[(k - sum_value) % length][1]
Author And Source
이 문제에 관하여(기출 3일차 | 볼링공 고르기, 무지의 먹방 라이브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hong_journey/기출-3일차-볼링공-고르기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)