1. 같은 숫자는 싫어 (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/12906
# 이해
# 스택에 연속된 숫자가 저장되면 안 됨.
# 풀이
# arr을 탐색하며 stack에 추가
# 추가하기 전, stack의 top과 같은 경우 pass, 다른 경우 push
def solution(arr):
stack = []
for elem in arr:
if stack:
if elem != stack[-1]:
stack.append(elem)
else:
stack.append(elem)
return stack
기능개발 (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/42586
# 이해
# progresses의 원소는 100%를 달성하면 배포된다.
# 매일 speeds의 원소만큼 progress가 진행된다.
# 가장 앞에 있는 원소가 100%를 달성한 순간에, 100%를 달성한 모든 원소를 배포한다.
# 풀이
# progresses의 각 원소를 100에서 빼고, 그 값을 speeds로 나누어 남은 일자를 계산한다. remain_days: [Int]
# remain_days를 탐색하며, 내림차순으로 정렬된 경우 tmp에 더하고,
# 내림차순이 깨진 순간 tmp를 answer에 append하고, tmp를 초기화 한다.
# answer를 return한다.
import math
def solution(progresses, speeds):
answer = []
remain_days = [math.ceil((100 - progress) / speed) for progress, speed in zip(progresses, speeds)]
current_max_day = remain_days[0]
count = 0
for day in remain_days:
if day <= current_max_day:
count += 1
else:
answer.append(count)
current_max_day = day
count = 1
answer.append(count)
return answer
`zip()` 함수는 여러 개의 iterators를 인자로 받아, 인덱스를 기준으로 짝 지은 튜플을 반환하는 함수이다.
위 코드에서 math.ceil()는 필수적이지 않다. `-((progress - 100) // speed)`의 형태로 작성해도 같은 결과이다.
3. 올바른 괄호 (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/12909
나의 풀이
# 이해
# 괄호가 올바르게 짝지어지면 True
# 하나라도 틀리면 False
# 풀이
# "("인 경우
# stack이 비었으면 추가한다.
# stack에 원소가 있다면, stack의 top이 "("이라면 추가. ")"이라면 return False
# ")"인 경우
# stack이 비었으면 return False
# stack에 원소가 있다면, stack의 top이 "("이라면 stack.pop(), ")"이라면 return False
def solution(brackets):
stack = []
for bracket in brackets:
if bracket == "(":
if not stack:
stack.append(bracket)
else:
if stack[-1] == "(":
stack.append(bracket)
else:
return False
else: # bracket == ")"
if not stack:
return False
else:
if stack[-1] == "(":
stack.pop()
else:
return False
return True if not stack else False
더 쉬운 풀이
def is_pair(s):
wt = 0
for c in s :
if c == '(' :
wt += 1
elif c == ')':
wt -= 1
if wt < 0:
return False
return wt == 0
스택에 성질을 활용하면 `나의 풀이`처럼 모든 케이스를 대응할 필요가 없다.
4. 프로세스 (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/42587
나의 풀이
# 이해
# priorities 배열을 우선순위에 따라 pop() 할 때,
# location 위치에 있는 원소가 몇 번째로 pop() 되는지 return
# 풀이
# max_value = max(priorities)
# priorities_with_hash = [[i, hash(i)] for i in priorities]
# max_value_hash = priorities_with_hash[location][1]
# order = 0
# while len(priorities_with_hash) >= 0:
# current = popleft()
# current[0] >= max_value,
# if current[1] == max_value_hash:
# return order
# order += 1
# current[0] < max_value:
# priorities_with_hash.append(current)
from collections import deque
import random
def solution(priorities, location):
order = 1
priorities_with_hash = deque([[priorities[i], i] for i in range(len(priorities))])
max_value = max(priorities)
target_hash = priorities_with_hash[location][1]
while len(priorities_with_hash) >= 0:
current = priorities_with_hash.popleft()
if current[0] >= max_value:
if current[1] == target_hash:
return order
max_value = max([elem[0] for elem in priorities_with_hash])
order += 1
else: # current[0] < max_value
priorities_with_hash.append(current)
return order
더 나은 풀이
def solution(priorities, location):
queue = [(i,p) for i,p in enumerate(priorities)]
answer = 0
while True:
cur = queue.pop(0)
if any(cur[1] < q[1] for q in queue):
queue.append(cur)
else:
answer += 1
if cur[0] == location:
return answer
`any()`: 인자로 받은 iterators 중에 하나라도 True이면, 전체를 True로 반환한다.
5. 다리를 지나는 트럭 (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/42583
# 이해
# bridge_length는 다리에 올라갈 수 있는 트럭 수. 동시에 트럭이 이동해야 하는 길이.
# weight는 다리가 버틸 수 있는 무게. 트럭의 개수가 bridge_length보다 적어도, 무게 기준을 만족해야 한다.
# 모든 트럭이 다리를 건너는 데까지 걸리는 시간을 return
# 풀이
# 정석적인 원형 큐로 풀이해보자
# bridge = deque([])
# bridge.append(truck_weights[0])
# bridge_sum += truck_weights[0]
# time = 0
# while True:
# time += 1
# out_truck = bridge.popleft()
# bridge_sum -= out_truck
# if out_truckt > 0 and len(truck_weights) == 0:
# return time
# if bridge_sum + truck_weights[0] < weight:
# in_truck = truck_weights.popleft()
# bridge.append(in_truck)
# bridge_sum += in_truck
# else:
# bridge.append(out_truck)
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque([0] * bridge_length)
truck_weights = deque(truck_weights)
bridge_sum = 0
time = 0
while truck_weights or bridge_sum > 0:
time += 1
out_truck = bridge.popleft()
bridge_sum -= out_truck
if truck_weights and bridge_sum + truck_weights[0] <= weight:
in_truck = truck_weights.popleft()
bridge.append(in_truck)
bridge_sum += in_truck
else:
bridge.append(0)
return time
`if truck_weights and bridge_sum + truck_weights[0] <= weight:` 이러한 방식이 좋다.
반복할 때마다 판단해야 하는 조건이 있다면, if이든 while이든 조건문에 포함시키자.
6. 주식가격(Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/42584
나의 풀이 (큐)
from collections import deque
def solution(prices):
queue = deque(prices)
answer = []
while queue:
price = queue.popleft()
sec = 0
for q in queue:
sec += 1
if price > q:
break
answer.append(sec)
return answer
복잡할 것이 없는 풀이이다.
그러나 30분 동안 고민했다.
주어진 배열의 길이가 10 ** 5이어서, O(N ** 2)은 시간 초과가 발생할 수 있다고 판단했기 때문이다.
실제로는 시간 초과가 발생하지 않았다.
계속해서 queue의 크기를 줄여나가기 때문인 듯하다.
실제로 코테에서도 웬만한 크기(10 ** 4 ~ 10 ** 5)라면 일단 완전탐색으로 풀이하자.
그렇게 부분 점수 먼저 확보해 놓고, 시간복잡도를 개선하는 것이 훨씬 현실적인 코테 접근법이다.
더 나은 풀이 (스택)
# 이해
# 배열의 각 원소가 오름차순이 지속되는 길이를 각각 return
# 다음 원소와 비교하여, 값이 작아지지 않을 때마다 += 1
# 일단 지속 시간을 1초 증가시키고, 그 뒤에 오름차순 여부를 판단한다.
# 마지막 원소는 0초이다.
# 풀이
# 일단 이중 반복문으로 풀자
from collections import deque
def solution(prices):
length = len(prices)
answer = [i for i in range(length - 1, -1, -1)]
stack = [0]
for i in range(1, length):
while stack and prices[stack[-1]] > prices[i]:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
https://velog.io/@soo5717/프로그래머스-주식가격-Python
위 블로그 글을 참고한 풀이이다.
'Dev > PS' 카테고리의 다른 글
| [Python] 프로그래머스 코딩테스트 고득점 Kit - 정렬 (0) | 2024.04.13 |
|---|---|
| [Python] 프로그래머스 코딩테스트 고득점 Kit - 힙 (0) | 2024.04.13 |
| [Python] 프로그래머스 코딩테스트 고득점 Kit - 해시 (0) | 2024.04.11 |
| [Swift 알고리즘] EquiLeader - Codility (0) | 2024.03.01 |
| [Swift 알고리즘] Dominator - Codility (0) | 2024.03.01 |