2024. 5. 2. 22:14ㆍCS/코딩연습문제
스택/큐
같은 숫자는 싫어
문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,
- arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
- arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
제한사항
배열 arr의 크기 : 1,000,000 이하의 자연수배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
리턴할 리스트를 스택으로 잡고, 스택의 가장 위 데이터를 peek하여 같으면 넘어가고 다르면 push해주는 간단한 코드를 작성하면 된다.
def solution(arr):
stack = []
for item in arr:
if not stack:
stack.append(item)
if stack[-1] != item:
stack.append(item)
return stack기능개발
문제 설명
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
제한 사항
작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.작업 진도는 100 미만의 자연수입니다.작업 속도는 100 이하의 자연수입니다.배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.
이 문제는 스택/큐 자료구조를 안 쓰고 풀었다. 각 progress가 완성되려면 며칠이 걸리는지는 쉽게 계산할 수 있으며, 각 progress에 대한 이 값을 days라는 리스트에 저장했다.
문제가 작동하는 방식이, 특정 days가 있으면 이후에 그 값보다 작은 days값들은 모두 한 번에 처리된다. 더 큰 days 값이 나오면 이제까지 쌓여왔던 progress 개수를 세서 answer에 append 하면 될 것이다. 따라서 비교를 위한 임시 변수 comp와, 쌓이는 days의 개수를 저장할 변수 count를 정의하여 아래와 같이 작성하였다.
import math
def solution(progresses, speeds):
days = []
for i in range(len(progresses)):
days.append(math.ceil((100-progresses[i])/speeds[i]))
answer = []
count = 0
comp = 0
for i in range(len(days)):
if days[i]>comp:
if i:
answer.append(count)
comp = days[i]
count = 1
else:
comp = days[i]
count += 1
else:
count+=1
answer.append(count)
return answer올바른 괄호
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어"()()" 또는 "(())()" 는 올바른 괄호입니다.")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
문자열 s의 길이 : 100,000 이하의 자연수문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
스택 문제를 푼다면 거의 단골처럼 나오는 유형의 문제이다!! 지난 번 백준에서 동일한 문제를 풀었으므로(https://cascade.tistory.com/61) 설명은 이전 게시물을 참고하길 바란다. 간단히 요약하자면, 스택을 하나 잡고 '('가 나오면 push, ')'가 나오면 stack을 peek하여 '('라면 pop하면 된다.
def solution(s):
answer = True
stack = []
for item in s:
if item == '(':
stack.append(item)
elif item == ')':
if not stack:
return False
if stack[-1] == '(':
stack.pop()
if stack:
return False
return True프로세스
문제 설명
운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.
현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.
제한사항
priorities의 길이는 1 이상 100 이하입니다.
priorities의 원소는 1 이상 9 이하의 정수입니다.
priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.
프로세스가 저장되어 있는 큐에서 데이터를 뽑아 우선순위가 가장 높다면 실행하고 아니면 다시 넣는 문제이다. 우선순위가 가장 높지 않은 경우 이 데이터는 삭제되지 않고 다시 큐에 들어가게 되는데, 이를 구현할 아주 좋은 자료구조는 원형 큐(circular queue) 이다. 단순히 인덱스 하나만 옮기면 되기 때문이다. 하지만, python 기본 내장 모듈 중 원형 큐가 직접적으로 구현되어 있지는 않으므로, deque을 이용해서 풀었다. 인덱스가 들어가는 덱과 priority가 들어가는 덱을 각각 따로 잡아서, 완전히 똑같이 작동하도록 아래와 같이 구현하였다.
from collections import deque
def solution(priorities, location):
deq_i = deque(range(len(priorities)))
deq_p = deque(priorities)
count = 0
execute = None
while execute != location:
if deq_p[0] == max(deq_p):
execute = deq_i.popleft()
deq_p.popleft()
count+=1
else:
deq_i.append(deq_i.popleft())
deq_p.append(deq_p.popleft())
return count다리를 지나는 트럭
문제 설명
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
제한 조건
bridge_length는 1 이상 10,000 이하입니다.weight는 1 이상 10,000 이하입니다.truck_weights의 길이는 1 이상 10,000 이하입니다.모든 트럭의 무게는 1 이상 weight 이하입니다.
다리를 일반적인 리스트로 만들면, 다리의 길이를 반영할 수 있는 방법이 없기 때문에, 길이만큼의 인덱스 수를 가진 리스트로 다리를 정의했다. 그리고 컨베이어 벨트처럼 1초가 지나면 트럭을 1칸씩 이동시키는 방법으로 코드를 작성했다. 이때 주의할 점은, 다리의 무게를 넘으면 안된다는 점인데, 꽉 찬 다리에서 새로운 트럭이 올라가면 다리에 가장 먼저 올라온 트럭은 내려야 하므로 이를 제외하고 전체 무게를 계산해 주어야 한다. 따라서 아래와 같이 코드를 작성하였다.
def solution(bridge_length, weight, truck_weights):
bridge = [0 for _ in range(bridge_length)]
count = 0
while truck_weights or sum(bridge):
bridge.pop(0)
if truck_weights:
if sum(bridge)+truck_weights[0]>weight:
bridge.append(0)
else:
bridge.append(truck_weights.pop(0))
else:
bridge.append(0)
count+=1
return count
그러나, 이렇게 작성 시 하나의 테스트 케이스에 대해 시간 초과가 났다. list.pop(0)이 시간을 많이 잡아먹는 것으로 판단하고, bridge의 자료형을 list가 아닌 deque로 바꾼 뒤 truck_weights가 비었을 때 처리 속도를 빠르게 바꾸어 다시 시도해보았으나 역시 시간초과가 났다.
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque([0 for _ in range(bridge_length)])
count = 0
while truck_weights or sum(bridge):
bridge.popleft()
if truck_weights:
if sum(bridge)+truck_weights[0]>weight:
bridge.append(0)
else:
bridge.append(truck_weights.pop(0))
else:
count+=bridge_length
break
count+=1
return count
위 코드에서 시간을 많이 잡아먹는 부분은 아래와 같은 상황이다. 대기열에 있는 트럭을 다리에 올리면 무게 초과가 되지만, 다리가 무지 길어 iteration을 여러 번 돌아야 하는 경우이다. 이때 앞에 있는 0의 개수만큼 반복문을 돌고 90을 다리에서 내려야 비로소 5을 올릴 수 있다.
이러한 부분을 한 번에 처리하기 위해, 앞에 0이 x개 몰려있으면 이걸 한꺼번에 없애고 뒤에 x개의 0을 추가하며, count는 한 번에 x만큼 올리는 식으로 가속화하는 코드를 넣어 주었다. 최종적으로 아래와 같이 작성하여 시간초과 없이 정답처리되었다. 이때 슬라이싱을 썼는데 deque은 슬라이싱 기능이 없으므로 다시 리스트로 바꾸었다.
def find_zeros(deq):
for i in range(len(deq)):
if deq[i]!=0:
return i
def solution(bridge_length, weight, truck_weights):
bridge = [0]*bridge_length
count = 0
while truck_weights or sum(bridge):
bridge.pop(0)
if truck_weights:
if sum(bridge)+truck_weights[0]>weight:
bridge.append(0)
x = find_zeros(bridge)
bridge = bridge[x:]+[0]*x
count+=x
else:
bridge.append(truck_weights.pop(0))
else:
count+=bridge_length
break
count+=1
return count주식 가격
문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다.
이 문제는, 특정 시간의 주식 가격에서부터 출발하여 오른쪽으로 값을 조회해 나가면서 두 가지 조건을 처리해 주어야 한다. 첫째는 조회하는 데이터의 인덱스이고, 둘째는 조회하는 데이터의 크기이다. C언어의 do-while 문이 있었다면 인덱스를 하나 옮기고 값을 비교하는 것이 가능했겠지만, python에는 while문만 있으므로 조건을 아래와 같이 두 개로 나누어 넣어 주었다.
def solution(prices):
answer = []
for idx, price in enumerate(prices):
j=idx
if j == len(prices)-1:
answer.append(0)
break
while price<=prices[j]:
j+=1
if j == len(prices)-1:
break
answer.append(j-idx)
return answer'CS > 코딩연습문제' 카테고리의 다른 글
| [프로그래머스 코테] 해시, 정렬 전문항 해설 (1) | 2024.04.22 |
|---|---|
| [백준] 집합과 맵 연습문제 (1764번, 10815번, 14425번, 7785번) (0) | 2024.04.13 |
| 큐 vs 덱 (백준 2164) (feat. 요세푸스 문제) (0) | 2024.04.13 |
| 프로그래머스 코딩테스트 연습문제 : 추억 점수 (0) | 2024.04.06 |
| 스택구조 문제풀이 (백준 28278번, 4949번, 12789번) (0) | 2024.03.26 |