리스트의 pop(0)은 0(n)의 시간복잡도를 가지고 deque의 popleft()는 O(1)의 시간복잡도를 가지기 때문에 deque사용한다
1초가 지날때마다 현재 다리에 있는 트럭의 무게와 다음으로 올라갈 트럭의 무게의 합이 최대 하중을 넘는지 확인한다
하중을 넘지 않는다면 다음 트럭을 올리고
그렇지 않다면 0을 더해 다리를 왼쪽으로 밀어낸다
- 첫번째 풀이(실패)
Point. 하나의 테스트케이스에서 시간초과가 났다 -> sum이 O(n)이라 시간초과 발생
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
truck_q = deque(truck_weights)
q = deque([0] * bridge_length)
while q:
time += 1
q.popleft()
if truck_q:
if sum(q) + truck_q[0] <= weight:
q.append(truck_q.popleft())
else:
q.append(0)
return time
- 두번째 풀이 (성공) -> sum대신 다리의 무게를 따로 관리해준다
from collections import deque
def solution(bridge_length, weight, truck_weights):
time = 0
truck_q = deque(truck_weights)
q = deque([0] * bridge_length)
t_weight = 0 # 현재 다리의 무게
while q:
time += 1
# 나갈 트럭이 있다면 그 무게를 빼준다
if q[0] != 0: t_weight -= q[0]
q.popleft()
if truck_q:
# 다리의 무게와 대기하는 트럭의 크기가 weight값을 넘지 않으면 더해준다
if t_weight + truck_q[0] <= weight:
t_weight += truck_q[0]
q.append(truck_q.popleft())
else:
q.append(0)
return time
맨 앞 대기목록의 중요도와 나머지 중요도를 비교해 중요도가 가장 높으면 출력을 아니면 뒤로 빼준다 -> deque를 써야하는 이유 앞뒤로 빠져야되니까
from collections import deque
def solution(priorities, location):
answer = 0
queue = deque(i for i in range(len(priorities)))
dic = {}
for i in range(len(priorities)):
dic[i] = priorities[i]
while queue:
tmp = queue.popleft()
dic_value = list(dic.values())
if dic[tmp] == max(dic_value):
del dic[tmp]
answer+=1
if tmp == location:
break
else:
queue.append(tmp)
return answer
+ (GOOD) 풀이
deque에 중요도와 순서를 함께 저장함
from collections import deque
def solution(priorities, location):
answer = 0
# v : 중요도 , i : 순서
queue = deque((v,i) for i,v in enumerate(priorities))
while queue:
item = queue.popleft()
if item[0] < max(queue)[0]:
queue.append(item)
else:
answer+=1
if item[1] == location:
break
return answer
# 자연수 뒤집어 배열로 만들기
def solution(n):
answer = []
for i in str(n):
answer.append(int(i))
answer.reverse()
return answer
#return list(map(int, reversed(str(n))))
# 나누어 떨어지는 숫자 배열
def solution(arr, divisor):
answer = []
for i in arr:
if i%divisor == 0:
answer.append(i)
if len(answer) == 0:
answer = [-1]
else:
answer.sort()
return answer
def solution(s, n):
answer = ''
alpa = 'abcdefghijklmnopqrstuvwxyz'
Alpa = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in s:
if i in alpa:
answer += alpa[(alpa.index(i)+n)%26]
elif i in Alpa:
answer += Alpa[(Alpa.index(i)+n)%26]
else:
answer += " "
return answer
# 콜라츠 추측
def solution(num):
answer = 0
while num!=1:
if num % 2 == 0:
num = num//2
else:
num = num*3 +1
answer+=1
if answer == 500:
answer =-1
break
return answer
# 하샤드 수
def solution(x):
answer = True
x_sum = sum(int(i) for i in str(x))
if x % x_sum != 0:
answer = False
return answer
from collections import defaultdict
def solution(tickets):
# 특정 티켓의 인접 리스트를 구하는 함수
def init_graph():
routes = defaultdict(list)
for key, value in tickets:
routes[key].append(value)
return routes
# 스택을 사용한 DFS
def dfs():
stack = ["ICN"] # 첫시작은 ICN
path = [] # 가려고하는 경로를 저장하는 변수
while stack: # stack이 비어있을 때까지
top = stack[-1]
# 특정 공항에서 출발하는 표가 없다면 또는 있지만 티켓을 다 써버린 경우
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top].pop(0))
return path[::-1]
routes = init_graph() # 그래프로 만들기
for r in routes: # 알파벳순 정렬
routes[r].sort()
answer = dfs() # 경로 구하기
return answer
Point. 그래프 문제인 이유 : 한 개의 알파벳만 달라 다음에 올 수 있는 단어를 방문하여 target값을 찾는다
방문한(pop)한 원소 temp가 방문할 수 있는 값은 temp와 한 개의 알파벳만 다른 words 원소 값이다.
from collections import deque
def solution(begin, target, words):
answer = 0 # 변환할 수 없는 경우 0 return
queue = deque()
for i in words: # 한 개의 알파벳만 다를 경우
count = 0
for j in range(len(begin)):
if begin[j] != i[j]:
count+=1
if count == 1:
queue.append([i,0])
words.remove(i)
while queue:
temp, idx = queue.popleft()
idx += 1
if temp == target: # 변환이 가능한 경우 몇단계인지 저장
answer = idx
else:
for i in words:
count = 0
for j in range(len(begin)):
if temp[j] != i[j]:
count+=1
if count == 1:
queue.append([i,idx])
words.remove(i)
return answer
# 문자열을 정수로 바꾸기
def solution(s):
return int(s)
# 자릿수 더하기
Point. 문자열로 변환해 한자리씩 들고온 후, 다시 정수형으로 변환해 더해준다
def solution(n):
answer = 0
for i in str(n):
answer+=int(i)
return answer
# 정수 내림차순으로 배치하기
Tip. 리스트 합쳐서 하나의 문자열로 바꾸는 함수 : '구분자'.join(리스트)
def solution(n):
answer = ""
n_list = list(str(n))
n_list.sort(reverse=True)
for i in n_list:
answer+=i
return int(answer)
# return int("".join(n_list))
s = "Zbcdefg"
s = list(s)
print(s)
>>> ['Z', 'b', 'c', 'd', 'e', 'f', 'g']
s.sort(reverse = True)
print(s)
>>> ['g', 'f', 'e', 'd', 'c', 'b', 'Z']
a = [1, 10, 5, 7, 6]
a.sort()
a
>>> [1, 5, 6, 7, 10]
y = sorted(a)
y
>>> [1, 5, 6, 7, 10]
a.reverse()
a
>>> [6, 7, 5, 10, 1]
+ 문자열의 길이를 기준으로 정렬 : 문자열.sort(key=lamba x:len(x))
+ 문자열의 n번째 수 기준으로 정렬 : 문자열.sort(key=lambda x:x[n])
+ 다중 조건 정렬 : 문자열.sort(key=lambda x: (x[0],x[1])) // x[0] 기준으로 정렬하고 x[1] 기준으로 정렬
a = [(4,0), (4,3), (4,2), (3,2), (2,1), (1,0)]
# 인자 없이 sorted()를 사용하면 리스트 아이템의 각 요소 순서대로 정렬
# 첫 번째 요소가 같으면 두 번째 요소로 비교
b = sorted(a)
print(b)
>>> [(1, 0), (2, 1), (3, 2), (4, 0), (4, 2), (4, 3)]
# key인자에 lambda 함수를 넘겨주면 반환값을 가지고 비교해 정렬
# 이 때, key로 전달되지 않은 요소에 대해선 정렬하지 않음
c = sorted(a, key=lambda x : x[0])
print(c)
>>> [(1, 0), (2, 1), (3, 2), (4, 0), (4, 3), (4, 2)]
d = sorted(a, key=lambda x : x[1])
print(d)
>>> [(4, 0), (1, 0), (2, 1), (4, 2), (3, 2), (4, 3)]
# 정렬 기준으로 다중 조건을 넘겨줄 수도 있다
# 첫 번째 인자를 기준으로 오름차순 정렬을 먼저 한다.
# 그 결과를 가지고 두 번째 인자를 기준으로 내림차순 정렬(-를 붙이면 내림차순 정렬)
e = sorted(a, key = lambda x : (x[0], -x[1]))
print(e)
>>> [(1, 0), (2, 1), (3, 2), (4, 3), (4, 2), (4, 0)]
주어지 문자열에서 알파벳 외의 문자(숫자, 특수문자, 띄어쓰기 등)로 나누어져 있는 첫 글자를 모두 대문자로 바꾸는 함수 : 문자열.title()
소문자 확인 : 문자열.islower() -> True / False로 리턴
대문자 확인 : 문자열.isupper() -> True / False로 리턴
※ capitalize()와 title() 차이 주의!
+ 알파벳/숫자인지 확인하기 -> True / False로 리턴
알파벳인지 확인하기 : 문자열.isalpha()
숫자인지 확인하기 : 문자열.isdigit()
알파벳 또는 숫자인지 확인하기 : 문자열.isalnum() -> 특수문자 있는지 확인
※ 문자열에 공백이 포함되어 있으면 False를 리턴합니다
+ 소문자 / 대문자
'abcdefghijklmnopqrstuvwxyz'
'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
a = 'hobby'
# 소문자로 바꾸기
s5 = a.lower()
print(s5)
>>> hobby
C = 'a2b3c4'
# 대문자로 바꾸기
C.upper()
>>> 'A2B3C4'
# 주어진 문자열의 맨 첫 글자를 대문자로 바꾸는 함수
C.capitalize()
>>> 'A2b3c4'
# 주어지 문자열에서 알파벳 외의 문자(숫자, 특수문자, 띄어쓰기 등)로
# 나누어져 있는 첫 글자를 모두 대문자로 바꾸는 함수 : 문자열.title()
C.title()
>>> 'A2B3B4'
# 소문자 확인
a.islower()
>>> True
# 대문자 확인
a.isupper()
>>> False
