베를린 3일차!
민보형 덕분에 3일이 아니고 3주 째 여기 있는 것 같다..
날마다 재밌게 보내는 중 ~
코테 문제는 확실히 난이도가 올라간 느낌
3일차인데 벌써 적응다 된 집앞 풍경 한국에서 못 보는 건축구조 덕분인지 여행 온 기분이 난다
치킨 케밥, durum doner라는 것도 먹어봤는데 개인적으로 빵이 더 바삭한 것은 케밥인듯 어쨌든 엄청 맛있었다. 베를린에 케밥이 유명하다고 합니다 ~.~
독일은 12/31만 폭죽을 허용한다고 하는데 그래서인지 진짜 말도안되게 다들 터뜨리고 있다. 한국 폭죽보다 훨씬 시끄럽고 아무 곳에서나 다 터뜨리고 있어서 위험하긴 한데 뭐.. 연말이라고 다들 봐주는 느낌
새해를 해외에서 경험하는게 처음인데 아주 좋은 추억을 쌓았다!
문제풀이
2개 이하로 다른 비트
def solution(numbers):
answer = []
for num in numbers:
binary = list('0' + bin(num)[2:])
idx = ''.join(binary).rfind('0')
binary[idx] = '1'
if num % 2 == 1:
binary[idx+1] = '0'
answer.append(int(''.join(binary), 2))
return answer< 풀이 과정 >
문제 해석하는데 여러 숫자를 예시로 생각을 많이 해 본 문제.
numbers 리스트 내 숫자가 홀수인 경우와 짝수인 경우로 나누어서 볼 수 있다.
- 홀수인 경우
숫자를 binary 변환 후 가장 오른쪽 0을 찾아 1로 바꾸고 그 다음 숫자는 0으로 변환하기 - 짝수인 경우
숫자 binary 변환 후 가장 오른쪽 0을 찾아 1로 바꾸기
위 과정을 거치면 문제에서 제시한 비트 변환 이후 2개 이내의 문자만 변환하여 제일 작은 수를 찾을 수 있다.
최종적으로 answer에 binary 형태의 문자열을 2진 변환하여 리턴
2 x n 타일링
def solution(n):
dp = [0 for _ in range(n)]
for i in range(n):
if i == 0:
dp[i] = 1
if i == 1:
dp[i] = 2
if i >= 2:
dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
return dp[n-1]
< 풀이 과정 >
n이 1~4인 case를 직접 그려보니 피보나치 수열을 따르는 형태임을 파악해 재귀함수를 이용하여 구현하였다.
dp라는 n길이의 0으로 꽉찬 리스트를 만들어주고 for 문을 n만큼 돌면서 가로 길이가 1인 경우 1, 길이가 2인 경우 2를 만들어주고 else인 케이스는 재귀를 돌려준다.
이때 1,000,000,007만큼 나눠주는 이유는 세로 길이가 지정되어 있지 않기에 무한대로 직사각형을 붙일 수 있기 때문이다.
다리를 지나는 트럭
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = [0 for _ in range(bridge_length)]
while bridge:
answer += 1
bridge.pop(0)
if truck_weights:
if sum(bridge) + truck_weights[0] <= weight:
w = truck_weights.pop(0)
bridge.append(w)
else:
bridge.append(0)
return answer< 풀이 과정 >
bridge 길이를 1만큼 건널 때 1초가 소요된다.
마지막 입출력 예시를 보면, input으로 100 100,[10,10,10,10,10,10,10,10,10,10] 이렇게 받는데, 차 한대가 다리를 건너는데 걸리는 시간은 100초이고 제일 마지막 차량이 지나가는데 10초가 더 소요되므로 총 110초가 걸리게 된다.
- 이를 이용하여 문제를 풀어보면, bridge라는 실제 다리 길이만큼의 리스트를 생성한다.
- 다리 길이 동안 매초를 나타내기 위해 answer + 1을 해주고 다리길이 pop으로 -1
- truck_weight이 비어있지 않으면, 다리에 올라가 있는 트럭 무게 + 이제 다리에 올라갈 트럭 무게가 weight이하면 bridge에 append해주고 truck_weight에서 pop
- 아니면 다시 다리 길이 원위치
