문제 1. 곱하기 혹은 더하기 (난이도 1, 풀이 시간 19분/30분, 정답(추정))
#6:31 50
#문자열 s : 0~9로 이뤄짐
#숫자사이에 x + 넣으며 연산가능 최대값 , + x 사이 우선순위없음
#결과는 항상 20억 미만
data = list(map(int,input()))
# 2 9 0 8 4
# 0이 왼쪽 끝에 있을 때: 오른쪽이랑 +
# 0이 오른쪽끝 : 왼쪽이랑 +
# 0이 가운데: 0이 이전 인덱스에 있고 현재가 0이 아니면 +
#0 + 2
#0 + 2 + 2
#
#0 + 2 + 0 + 2 x 2
res = 0
for x,y in enumerate(data):
if x == 0 and y == 0:
continue
elif x == len(data)-1 and y == 0:
continue
else:
if y != 0:
if res == 0:
res += y
elif data[x-1] == 0:
res += y
else:
res *= y
elif y == 0:
continue
print(res)
문제 2. 문자열 뒤집기 (난이도 1, 풀이 시간 8분/20분, 정답(추정))
#6:52 7:00
#00110101 변화점 3개
#00110011 변화점 2개
#001101011 변화점 3개
data = list(map(int,input()))
if data[0] == 1:
for x,y in enumerate(data):
if data[x] == 0:
data[x] = 1
elif data[x] == 1:
data[x] = 0
point = 0
for i in range(1,len(data)):
if data[i-1] == 0 and data[i] == 1:
point += 1
print(point)
문제 3. 만들 수 없는 금액 (난이도 1, 풀이시간 44분/30분, 정답(추정))
#7:02 44
#N개의 동전으로 만들 수 없는 양의 정수금액 중 최소값 , 중복 X
import math
N = int(input())
data = list(map(int,input().split()))
data = sorted(data)
comb = []
i = 0
#만들 수 있는 조합 구하고 두 원소간 차이가 2 이상 나면 이전 원소값 +1 이 결과, 끝까지 차이가 안나면 만들 수 있는 조합의 합 최대값 +1
for i in range(2**N):
indi = [0] * N
j = 0
while i != 0:
if i%2 == 0:
indi[j] = 0
else:
indi[j] = 1
i = i // 2
j += 1
sum_ = 0
for j in range(N):
if indi[j] == 1:
sum_ += data[j]
comb.append(sum_)
comb = sorted(comb)
for i in range(1,len(comb)):
if comb[i] > comb[i-1] + 1:
print(comb[i-1]+1)
break
- 요소가 N가지 있을 때 2**N 의 방법에 대한 모든 조합을 구현하는데 애를 먹음
- 이진수의 형태를 참고해서 풀려했는데 이진수 구하기를 코드로 처음짜봐서 구현하는데 시간이 오래걸림
정답 참고
#7:02 44
#N개의 동전으로 만들 수 없는 양의 정수금액 중 최소값 , 중복 X
import math
N = int(input())
data = list(map(int,input().split()))
data = sorted(data)
# 1 1 2 3 9
#1 2 5 8 10
#1까지 만들수있을때 2 올수있음
#1옴
#2까지 만들수있을때 3 올수있음
#2옴
#4까지 만들수있을때 5 올수있음
#3옴
#7까지 만들수있을때 8 올수있음
#9옴 x
#8이 안와서 8을 못만들었으므로 결과는 8
tg = 1
for i in data:
if tg < i:
break
else:
tg = tg + i
- 이해하는데 한참 걸렸다
- 말로 풀어내는 연습 더 해야할 듯
문제 4. 볼링공 고르기 (난이도 1, 풀이시간 10분/30분, 비효율)
말 그대로 구현
#4:20
#공 n개 같은 무게 다른공
#무게 1~m
# 서로 다른 무게 볼링공 고르기
# 총 경우의 수
N,M = map(int,input().split())
data = list(map(int,input().split()))
cnt = 0
for i in range(0,N-1):
for j in range(i+1,N):
if data[i] != data[j]:
cnt += 1
print(cnt)
- 1차원 적인 구현
N,M = map(int,input().split())
data = list(map(int,input().split()))
cnt = 0
#1 3 2 3 2
#1 5 4 3 2 4 5 2
#(무게 낮은거, 무게 많은거) 조합
#무게1 -> 무게2 x2 무게3 x1 무게4 x2 무게5 x2 = 2+1+2+2 = 7
#무게2 x2 -> 무게3 x1 무게4 x2 무게5 x2 = 2+4+4 = 10
#무게3 x1 -> 무게4 x2 무게5 x2 = 2+2 = 4
#무게4 x2 -> 무게5 x2 = 4
#무게5 x2 -> x0 = 0
#총합 25
muge = [0]*11
for i in data:
muge[i] += 1
for i in range(0,len(muge)-1):
if muge[i] != 0:
cnt += muge[i] * sum(muge[i+1:])
print(cnt)- 좀 더 효율적인 구현
문제 5. 무지의 먹방 라이브 (난이도 1(체감 2.5), 풀이시간 x/30분, 책 풀이 참고하여 풀음)
import heapq
def solution(food_times, k):
q = []
for x,y in enumerate(food_times):
heapq.heappush(q,(y,x+1)) # 시간, 순번
passed = 0
prev = 0
while q:
k1 = k
print(q, k, passed)
if(prev == q[0][0]):
heapq.heappop(q)
continue
k1 -= len(q) * (q[0][0]-prev)
if k1 < 0:
break
k = k1
passed += len(q) * (q[0][0]-prev)
prev = q[0][0]
heapq.heappop(q)
if len(q) == 0:
return -1
if passed == 0:
return k % len(food_times) + 1
q = sorted(q,key=lambda x:x[1])
answer = q[k%len(q)][1]
return answer
print(solution([3,1,1,1,2,4,3],12) )
#3,1,2 3/ 2,0,1 2 / 1,0,0 1/
#30 15 20 10 5 3 /6x3/ 27 12 17 7 2 0 /5x2/ 25 10 15 5 0 0 /4x5/
#20초면 27 12 17 7 2 0 에서 20-18 = 2초 남은것
- 우선순위 큐 (heapq)를 써야한다는 힌트를 책에서 얻고 풀음