2023. 9. 22. 20:00ㆍAlgorithm
1. 올바른 괄호
(문제 설명, 제한사항, 입출력 예)
기호 "("와 ")"로만 이루어진 문자열이 주어졌을 때,
문자열이 올바른 괄호로 짝지어져 있으면 True를, 올바르지 않은 괄호로 짝지어져 있으면 False를 반환하라는 문제이다.
여기서 괄호가 올바르게 짝지어졌다는 것은 "(" 문자로 열렸으면, 반드시 ")" 문자로 닫히는 짝이 이루어져 있어야 한다는 것을 의미한다.
(내가 생각한 풀이 과정)
문자열 s를 반복하면서 괄호를 체크한다.
"("를 만나게 되면 카운트를 1 증가, ")"를 만나게 되면 카운드를 1 감소시켜 최종적으로는 카운트가 0이 되면 True를 반환한다. (-> 열린 괄호와 닫힌 괄호의 수가 같다는 것을 의미)
단, 여기서 추가적으로 열린 괄호가 없을 때 닫힌 괄호가 먼저 오는 경우를 예외처리 해줘야 한다.
-> 괄호가 아직 열리지 않았는데 먼저 괄호가 닫혀버리면, 올바르게 괄호가 짝지어질 수가 없기 때문.
-> 카운트가 0일 때 닫힌 괄호가 오는 경우에는 바로 False 처리를 해줌.
(코드)
💡 내 코드
def solution(s):
open_count = 0
for gwalho in s:
if gwalho == "(":
open_count += 1
else:
if open_count == 0: return False
open_count -= 1
if open_count == 0: return True
else: return False
2. 기능개발
(문제 설명, 제한사항, 입출력 예)
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 배열 progresses와 각 작업의 하루 기준 개발 속도가 적힌 배열 sppeds가 주어질 때, 각 배포마다 몇 개의 기능이 배포될 수 있는지를 나타내는 배열을 구하라는 문제이다.
각 기능은 진도가 100%가 되어야 배포가 가능하다.
또한, 각 기능의 개발 속도는 모두 다르기에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수는 있지만, 뒤에 있는 기능이 배포될 때는 앞에 있는 기능이 배포될 때 함께 배포되어야 한다.
(내가 생각한 풀이 과정)
먼저 time이라는 리스트에, 먼저 배포되어야 하는 작업 순서대로 며칠 후에 배포가 가능한지를 구해 추가한다.
100에서 현재 진도를 빼 작업해야 하는 진도를 구해주고 (100-progresses), 남은 진도를 작업 속도로 나눠주면 며칠 뒤에 배포가 가능한지를 구할 수 있다. 나눠 떨어지지 않는 경우를 대비해서는 무조건 math.ceil() 함수를 이용해서 반올림해줘야 한다. (배포는 하루의 끝에 이루어진다는 제한 사항 마지막에 따라)
time 리스트가 만들어졌다면, 이 리스트를 반복하면서 이전 작업시간과 비교를 해주면 되겠다.
만약 앞 작업시간이 먼저 끝나는 경우에는 answer 리스트에 바로 추가해주면 되고, 뒤 작업시간이 먼저 끝나는 경우에는 같이 배포되어야 하므로 카운트값을 증가시켜서 한 번에 추가해 주면 되는 간단한 원리이다.
(코드)
💡 문제 풀이 코드
import math
def solution(progresses, speeds):
answer = []
# time 리스트에 몇일 후 배포가 가능한지를 담음
time = []
for progress, speed in zip(progresses, speeds):
time.append(math.ceil((100-progress) / speed))
# 배포 시간을 앞과 비교하며, 최종 반환 리스트에 값을 추가하기
count = 1
before = time[0]
for i in range(1, len(time)):
if before < time[i]: # 이전 작업시간이 먼저 끝날 때
answer.append(count)
count = 1
before = time[i]
else: # 이전 작업시간이 현 작업시간보다 오래걸릴 때
count += 1
answer.append(count)
return answer
3. 프로세스
(문제 설명, 제한사항, 입출력 예)
프로세스의 중요도가 순서대로 담긴 배열과, 몇 번째로 실행되는지가 궁금한 프로세스의 위치를 알려주는 정수가 주어진다.
이때, 내가 궁금해했던 프로세스의 실행순서를 구하라는 문제이다.
운영체제에서 프로세스가 실행되는 규칙은 아래와 같다.
1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼낸다.
2. 큐에 대기 중인 프로세스 중, 우선순위가 더 높은 프로세스가 있다면 꺼내놓은 프로세스를 다시 큐에다가 넣는다.
3. 우선순위가 더 높은 프로세스가 없으면, 꺼내져 있는 프로세스를 실행하고 그 프로세스는 실행 대기 큐에 다시 넣지 않는다.
(내가 생각한 풀이 과정)
첫 번째 max값을 지정한다. 그리고 priorities 리스트를 반복하면서 max값과 같은 요소를 만나면, 해당 요소의 인덱스가 내가 찾고자 하는 위치인지를 비교한다.
내가 찾고자 하는 위치가 아니면, 다음 max값을 지정한다. 아까 반복이 멈췄던 그다음 위치부터 다시 반복을 시작한다.
그리고 max와 또 같은 요소를 만나면, 인덱스를 비교하고...쭉쭉쭉 내가 찾고자 하는 위치와 같은 위치인 경우에 반복을 멈추고 return 하고 끝내면 된다.
이 풀이 과정을 구현해주기 위해 해준 사전작업 몇 개가 있다.
첫째. 항상 priorities 리스트 자체를 반복해주면, 처음 요소부터 반복이 시작되기 때문에 "반복이 멈췄던 다음 위치부터 반복을 시작해야한다"는 풀이에 맞게 수행할 수 없었다. -> 그래서 priorities의 길이를 전체 요소 길이만큼 계속 누적 추가해 반복이 이어질 수 있도록 구현했다.
둘째. priorities 리스트를 변형해줬기 때문에 인덱스 값을 찾는 식을 만들어줘야 했다. -> double_priorities의 인덱스 위치 i를 기존 priorities의 길이에 나눈 값의 나머지를 구하면, 그 값이 기존 priorities 리스트에 인덱스가 된다.
셋째. 찾고자 하는 위치가 아닐 때 다음 max값을 지정해 주는 방법 -> priorities의 정렬 리스트를 따로 만들어줬다. 오름차순으로 배치되었기에 처음에는 가장 마지막 인덱스에 있는 값이 max값일 것이고, 만약 다음 반복을 돌려야 하는 경우에는 인덱스를 한 칸 앞으로 당기는 방식으로 max값을 연달아 지정해 줬다.
(코드)
💡 문제 풀이 코드
def solution(priorities, location):
double_priorities = priorities * len(priorities)
queue = sorted(priorities) # 우선순위를 꺼내기 위해 정렬된 priorities 리스트
count = 0 # 반환용 실행순서
idx = len(queue)-1 # 현재 가장 높은 우선순위를 담고 있는 인덱스
high_prior = queue[idx] # 가장 높은 우선순위
for i, q in enumerate(double_priorities):
# 대기중인 프로세스가 가장 높은 우선순위와 일치할 때
if q == high_prior:
count += 1 # 실행 1 증가
idx -= 1
high_prior = queue[idx]
# 내가 알고 싶었던 위치의 프로세스가 꺼내졌을 때
if i%len(priorities) == location:
return count
4. 다리를 지나는 트럭
(문제 설명, 제한사항, 입출력 예)
일차선 다리에 올라갈 수 있는 트럭의 수 (일차선이므로, 트럭의 수는 곧 다리의 길이가 된다.) bridge_length와 다리가 견딜 수 있는 최대 무게 weight값이 주어진다.
그리고 건너야 하는 트럭의 무게가 각각 truck_weights 리스트에 원소로 들어있게 주어졌을 때, 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지(트럭이 다리 길이 1을 지나는 것을 1초라고 정한다.)를 구하라는 문제이다.
(내가 생각한 풀이 과정)
대충 문제를 살펴보면, 먼저 들어온 게 먼저 나가는 선입선출(FIFO)의 구조임을 쉽게 파악할 수 있을 것이다.
대기하는 트럭도 꺼내기 쉽도록 deque 자료형으로, 다리의 길이(bridge_length)만큼 또 다른 deque 자로형(bridge)을 각각 만들어준다.
시간을 1씩 증가시키면서 bridge 위에 트럭을 올려놓을 건데,
pop 되는 bridge위의 요소와, 대기 중인 첫 번째 트럭의 무게가 weight보다 작거나 같을 경우에만 트럭이 다리 위에 올라올 수 있을 것이다.
만약, 클경우에는 0 요소를 bridge deque에 올린다.
이런 식으로 트럭을 다리 위에 올리거나, 0을 다리 위에 올리면서 반복 1회당 시간을 1씩 증가시켜 최종적으로 트럭이 모두 통과된 경우(=len(truck)이 0인 경우 = 대기 중인 트럭이 없는 경우)에 최종 시간값을 반환하면 답을 구할 수 있다.
(코드)
💡 문제 풀이 코드
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0
truck = deque(truck_weights) # 트럭이 대기하는 deque
bridge = deque([0 for _ in range(bridge_length)]) # 다리 길이 만큼의 deque
w = 0
while True:
answer += 1 # 시간이 1 증가
bridgeOut = bridge.popleft()
w -= bridgeOut
# 새로 올라와야 하는 트럭의 무게가 weight보다 큰 경우 -> 트럭이 올라오지 못함
if w+truck[0] > weight:
bridge.append(0)
# 새로 올라와야 하는 트럭의 무게가 weight보다 큰 경우 -> 트럭이 올라오지 못함
else:
w += truck[0]
bridge.append(truck[0])
truck.popleft()
# 모든 트럭이 전부 통과한 경우
if len(truck) == 0:
answer += len(bridge)
return answer
5. 주식가격
(문제 설명, 제한사항, 입출력 예)
초 단위로 기록된 주식가격이 담긴 배열이 주어질 때, 가격이 떨어지지 않은 기간이 몇 초인지를 구하라는 문제이다.
예를 들어, 주식 가격이 [1, 2, 3, 2, 3] 순으로 변했다고 했을 때,
첫 번째 1이라는 가격은 시간이 끝날 때까지 주식 가격이 0이 되지 않았기 때문에 떨어지지 않았다고 판단한다. (두 번째 경우도 마찬가지)
세 번째 3이라는 가격은 바로 다음 시간대에 2로 떨어지는 걸 봐서, 1초 만에 가격이 떨어졌다고 이해할 수 있겠다.
(내가 생각한 풀이 과정)
조금 비효율적일 수도 있지만, 이중 반복을 돌리는 것 외에 다른 방법이 떠오르지 않아 이중 반복문을 사용했다. (런타임 에러는 없었음)
1번째 가격을 예시로 들면, 2번째 가격부터 쭉 전체 prices 리스트를 훑는다.
이때, 가격이 떨어진 경우 혹은 마지막 리스트까지 간 경우에는 최종 반환할 answer리스트에 반복을 돈 카운트 값을 추가하면 되겠다.
가격이 떨어지지 않으면, 그냥 카운트 값만 추가하면 된다.
그리고 반복을 돌 수 없는 마지막 가격은 무조건 시간이 0일 수밖에 없으니, 0을 append 해주고 최종 반환해 주면 되겠다.
(코드)
💡 문제 풀이 코드
def solution(prices):
answer = []
for i in range(len(prices)):
count = 1
for j in range(i+1, len(prices)):
# 가격이 떨어졌거나, 끝까지 가격이 떨 경우
if (prices[i] > prices[j]) or (j == len(prices)-1):
answer.append(count)
break
# 가격이 떨어지지 않은 경우
else:
count += 1
# 가장 마지막 prices는 절대 가격이 떨어지지 않는다.
answer.append(0)
return answer