무지의 먹방 라이브
https://programmers.co.kr/learn/courses/30/lessons/42891
- 정확도는 모두 통과했지만 효율성은 어떻게 개선할지 감이 오지 않는다
- rotate는 deque로 푸는 것이 생각나 deque로 해결하였다
- 하지만 이 문제 푸는데 한시간 이상이 걸렸는데 앞으로 막막하다
알고리즘
1. 함수가 호출되면 음식의 개수를 food_kinds에 담는다.
2. deque를 선언해 튜플 형식으로 (index,value)를 모두 집어넣는다
3. 반복문을 통해 pop을 하며 k와 value를 모두 -1 해준다
4. deq가 모두 비거나(음식을 다 먹었거나) k가 0이 될 때 까지 반복한다
from collections import deque
def solution(food_times, k):
food_kinds=len(food_times)
deq = deque()
for i in range(food_kinds):
deq.append((i+1,food_times[i]))
print("init: ", deq)
while(True):
print(deq)
idx, value = deq.popleft()
print('idx: ',idx,'value: ', value)
if k==0:
return idx
value -= 1
k -= 1
print('idx: ',idx,'value: ', value)
if value != 0:
deq.appendleft((idx, value))
deq.rotate(-1)
if len(deq)==0:
return -1
2110 공유기 설치
풀었던 문제지만 헷갈렸다
- 가장 인접한 두 공유기 사이의 '거리'를 구하는 것이기 때문에
- 최소값과 최대값을 각각 1, N[-1] - N[0]로 지정
- 이진탐색을 통해 값을 바꿔가며 공유기가 모두 설치가능한 지점을 찾는다
import sys
_ , C = map(int,input().split())
N = sorted(list( int(sys.stdin.readline()) for _ in range(_)))
# 가장 인접한 두 공유기 사이의 '거리'를 구하는 것이기 때문에
# 최소값과 최대값을 각각 1, N[-1] - N[0]로 지정
start = 1
end = N[-1] - N[0]
result = 0
while(start<=end):
mid = (start + end) // 2
current = N[0]
cnt = 1
for i in range(1,len(N)):
if N[i]-current >= mid:
current = N[i]
cnt += 1
if cnt >= C:
start = mid+1
result = mid
else:
end = mid-1
print(result)가사 검색 - 카카오 블라인드
- 음.. 로직은 어렵지 않았다
- 정확도는 맞았지만 효율성에서 틀렸다
- 시간날 때 파이썬 내장함수를 이용해서 다시 풀어봐야겟다
로직
- 검색 키워드마다 ?을 제외한 부분을 start, end 변수에 위치를 담는다.
- 단어와 비교하여 ?을 제외한 부분이 일치하면 cnt를 증가시켜 최종 cnt를 answer에 append
def solution(words, queries):
answer = []
# 검색키워드 대응
for key in queries:
key_len = len(key)
start = 0
end = key_len-1
cnt = 0
all_q = 0
if key[0] == '?' and key[key_len-1] == '?':
all_q = 1
elif key[0] == '?':
for i in range(1,key_len):
if key[i] != '?':
start = i
break
else:
for i in range(key_len-1,-1,-1):
if key[i] != '?':
end = i
break
if all_q == 1:
for word in words:
if len(word) == key_len:
cnt += 1
else:
for word in words:
if len(word) != key_len:
continue
elif word[start:end+1] == key[start:end+1]:
cnt += 1
answer.append(cnt)
return answer다시 풀어봤다
- 이전 코드에서 len() 함수가 반복적으로 사용되는 것을 한번만 호출하여 사용하도록 했다
- 비교 연산을 이용하여 비교하지 않고 내장 함수를 사용했다
- 확실히 시간은 줄었지만 그래도 실패 ㅠㅠ
- 머가 문제징
def solution(words, queries):
answer = []
# 검색키워드 대응
words_len = []
for word in words:
words_len.append(len(word))
for key in queries:
key_len = len(key)
start = 0
end = key_len-1
cnt = 0
all_q = 0
if key[0] == '?' and key[key_len-1] == '?':
all_q = 1
for word_len in words_len:
if word_len == key_len:
cnt += 1
elif key[0] == '?':
for i in range(1,key_len):
if key[i] != '?':
start = i
break
for i in range(len(words)):
if words_len[i] != key_len:
continue
elif words[i].endswith(key[start:]):
cnt += 1
else:
for i in range(key_len-1,-1,-1):
if key[i] != '?':
end = i
break
for i in range(len(words)):
if words_len[i] != key_len:
continue
elif words[i].startswith(key[:end+1]):
cnt += 1
answer.append(cnt)
return answerbefore
after
11404 플로이드
-
플로이드 와샬 알고리즘을 익힌 후 어렵지 않게 풀 수 있었다.
-
다만 계속 98%에서 틀렸다고 떠서 비용이 100,000보다 작거나 같은 수 이므로 1000,000으로 INF 값을 설정했었는데, max값은 (버스) 100,000 × (도시) 100을 곱한 값보다 커야 한다는 것을 알았다
import sys
input = sys.stdin.readline
INF = 20000000
N = int(input())
M = int(input())
navi = [[ INF for _ in range(N) ] for _ in range(N)]
for _ in range(N):
navi[_][_] = 0
for _ in range(M):
i, j, weight = map(int, input().split())
if navi[i-1][j-1] > weight:
navi[i-1][j-1] = weight
for k in range(N):
for i in range(N):
for j in range(N):
if navi[i][j] > navi[i][k] + navi[k][j]:
navi[i][j] = navi[i][k] + navi[k][j]
for i in range(N):
for j in range(N):
if navi[i][j] == INF:
navi[i][j]=0
print(navi[i][j],end=' ')
print()
@flip_404