1. 스택구현하기
- 문제
스택에서 정수를 제거
스택의 size 출력
스택이 비어있는지 여부 출력
스택의 꼭대기 값 출력
class Stack:
def __init__(self) :
self.myStack = []
def push(self, n) :
self.myStack.append(n)
def pop(self) :
if self.empty()==1:
return
else:
self.myStack.pop()
def size(self) :
return len(self.myStack)
def empty(self) :
if self.size()==0:
return 1
else:
return 0
def top(self) :
if self.empty()==1:
return -1
else:
# result = self.myStack.pop()
return self.myStack[-1]
return result- 아직 2%씩 완성도가 부족하다...
2. 큐 구현하기
- 큐에서 정수를 제거
큐의 size 출력
큐가 비어있는지 여부 출력
큐의 head 값 출력
큐의 rear 값 출력
class Queue:
def __init__(self) :
self.myQueue = []
def push(self, n) :
self.myQueue.append(n)
# 제거하는 함수 pop
def pop(self) :
if self.empty() ==1:
return
del self.myQueue[0]
def size(self) :
return len(self.myQueue)
def empty(self) :
if self.size() == 0:
return 1
else:
return 0
def front(self) :
if self.empty() == 1:
return -1
return self.myQueue[0]
def back(self) :
if self.empty() == 1:
return -1
return self.myQueue[-1]
# 어차피 조건에 맞으면 return에서 종료되기때문에 나머지는 필요 없다는 생각!3. 올바른 괄호인지 판단하기
- 문제파악
1.아직 완성되지 않은 여는 괄호들이 있을 때, 나중에 등장한 여는 괄호는 항상 먼저 등장한 여는 괄호보다 일찍 완성된다.
2.닫는 괄호를 처리할 때, 닫을 수 있는 여는 활호가 존재하지 않은 경우는 올바르지 않은 경우이다.
3.모든괄호들을 처리하고 나서, 여는 괄호가 남김없이 모두 완성된 경우가 올바른 경우이다.
class Stack:
def __init__(self) :
self.myStack = []
def push(self, n) :
self.myStack.append(n)
def pop(self) :
if self.empty() == 1:
return
self.myStack.pop()
def size(self) :
return len(self.myStack)
def empty(self) :
if self.size()==0:
return 1
else:
return 0
def top(self) :
if self.empty()==1:
return -1
return self.myStack[-1]
def checkParen(p) :
st = Stack()
for c in p:
if c == '(':
st.push(c)
else:
if st.empty() == 1:
return "NO"
# st.push(c)와 짝을 이룰 시 제거한다.
st.pop()
if st.empty()==1:
return "YES"
else:
return "NO"
x = input()
print(checkParen(x))3-1. 계산순서 정하기
class Stack:
def __init__(self) :
self.myStack = []
def push(self, n) :
self.myStack.append(n)
def pop(self) :
if self.empty() == 1:
return
self.myStack.pop()
def size(self) :
return len(self.myStack)
def empty(self) :
if self.size()==0:
return 1
else:
return 0
def top(self) :
if self.empty()==1:
return -1
return self.myStack[-1]
def find_order(p) :
# 스택 class 를 가져온다.
s= Stack()
# 입력값 만큼의 빈 배열 선언
result = [0] * len(p)
# count 변수 선언
cnt = 1
# 숫자 세는 for문
for i in range(len(p)):
if p[i] == '(':
s.push(i)
else:
index = s.top()
s.pop()
result[index] = cnt
result[i] = cnt
cnt += 1
return result4. 스택으로 수열 만들기
- 문제
1부터 N까지의 모든 정수를 한 번씩 스택에 입력하고, 출력합니다.
이 때, 무조건 작은 수는 큰 수보다 먼저 입력되어야 합니다.
예를 들어 1보다 3이 먼저 입력되는 경우는 없습니다.
주어진 수열을 만들 수 있는지 없는지 알아보는 프로그램을 작성해봅시다.
예를 들어 [2, 1, 4, 3]은 위 규칙으로 만들 수 있는 예시입니다.
1넣기 -> 2넣기 -> 2뽑기 -> 1뽑기 -> 3넣기 -> 4넣기 -> 4뽑기 -> 3뽑기의 과정으로 만들 수 있기 때문입니다.
그러나 [3, 1, 2, 4]는 만들 수 없는 예시입니다. - 코드
def is_stack_sequence(nums) :
# 1을 push 하는것이 항상 먼저다.
stack = [1]
current = 0
for i in range(2, len(nums)+1):
while len(stack) > 0 and stack[-1] == nums[current]:
stack.pop()
current += 1
if len(stack) == 0 or stack[-1] < nums[current]:
stack.append(i)
else:
return "No"
return "Yes"5. 메모장
- 문제
L : 커서를 왼쪽으로 한 칸 이동, 커서가 맨 왼쪽인 경우 아무 변화가 없음
R : 커서를 오른쪽으로 한 칸 이동, 커서가 맨 오른쪽인 경우 아무 변화가 없음
D : 커서 왼쪽에 있는 문자 하나 삭제, 커서가 맨 왼쪽인 경우 아무 변화가 없음
P s : 임의의 알파벳 sss를 커서 왼쪽에 추가 - 입력
첫 번째 줄에 메모장에 처음 저장되어 있는 문자열 s를 입력합니다.
두 번째 줄에 메모장에 입력할 명령어의 개수인 정수 n을 입력합니다.
세 번째 줄부터 n개의 줄에 걸쳐서 명령어가 각각 입력됩니다. - 코드
def notepad(s, commands) :
left = list(s)
# 왜냐면 처음에 비어있으니까
right = []
for line in commands:
command = line.split()
action = command[0]
if action == "L":
if len(left)>0:
right.append(left.pop())
elif action == "R":
if len(right)>0:
left.append(right.pop())
elif action == "D":
if len(left)>0:
left.pop()
elif action == "P":
left.append(command[1])
result = left + right[::-1]
return "".join(result)6. 주문처리하기
-
문제
processOrder(orders) 함수는 사용자가 입력한 주문 정보 orders가 처리되는 순서를 리스트로 반환합니다.
주문 정보는 orderInfo 클래스를 통해 사용됩니다.
일반 주문보다 VIP 고객의 주문의 우선순위가 높습니다.
예를 들어 3분이 걸리는 일반 주문과 4분이 걸리는 VIP 주문이 있을 경우에는 4분이 걸리는 VIP 주문을 먼저 처리한 후 3분이 걸리는 일반 주문을 처리합니다.
주문을 처리하고 있는 도중에 어떠한 주문이 들어오더라도 하던 일을 끝내고 다음 주문을 처리합니다. -
입력
첫 번째 줄에 주문의 수를 나타내는 정수 n이 입력됩니다. (1≤n≤150000)
두 번째 줄 부터 n줄에 걸쳐 a b c가 공백으로 구분되어 입력됩니다.
a: 고객이 방문하는 시간
b: 주문을 처리하기 위해 걸리는 시간
c: VIP 여부 (0: 일반, 1: VIP)
(a 순으로 정렬되어 입력, 동일한 시간에 2개이상의 주문은 없다고 가정) -
코드
class Queue:
def __init__(self) :
self.myQueue = []
def push(self, n) :
self.myQueue.append(n)
# 제거하는 함수 pop
def pop(self) :
if self.empty() ==1:
return
del self.myQueue[0]
def size(self) :
return len(self.myQueue)
def empty(self) :
if self.size() == 0:
return 1
else:
return 0
def front(self) :
if self.empty() == 1:
return -1
return self.myQueue[0]
def back(self) :
if self.empty() == 1:
return -1
return self.myQueue[-1]
class orderInfo:
def __init__(self, t, d, v):
self.time = t
self.duration = d
self.vip = v
def selectQueue(normalQueue, vipQueue, time, orders):
normalIndex = normalQueue.front()
vipIndex = vipQueue.front()
if vipIndex == -1:
return normalQueue
if normalIndex == -1:
return vipQueue
# 둘다 없는 경우 이땐 더 빨리 온 주문을 처리한다.
if time < orders[normalIndex].time and time < orders[vipIndex].time:
# 크거나 같은 이유는 vip가 더 빠르니까
if orders[vipIndex].time <= orders[normalIndex].time:
return vipQueue
else:
return normalQueue
# 노말에만 있는경우
if time >= orders[normalIndex].time and time < orders[vipIndex].time:
return normalQueue
# 우리가 밀린 작업이 vip에만 있는 경우
if time >= orders[vipIndex].time and time < orders[normalIndex].time:
return vipQueue
# 밀린작업이 노말과 vip 동시에 있다면 무조껀 vip가 우선이니까
return vipQueue
def processOrder(orders) :
result = []
normalQueue = Queue()
vipQueue = Queue()
jobEndTime = 0
curTime = -1 #절대로 존재할 수 없는 값을 초기값으로 설정해두어야 좋음
for i in range(len(orders)):
curTime = orders[i].time
if orders[i].vip == 0:
normalQueue.push(i)
else :
vipQueue.push(i)
while jobEndTime <= curTime and not(normalQueue.empty()==1 and vipQueue.empty()==1):
# 주문이 많이 밀려있는 경우
# 노말 큐 또는 vip큐를 선택하는 타켓 큐
targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
# 우리가 처리할 주문 번호를 가져온다.
index = targetQueue.front()
# 주문을 처리한다. =jobEndTime을 증가시킨다.
# jobEndTime 이 order[index].time 보다 큰 경우:
#주문이 밀려있어서 이전 작업을 끝내자마자 바로 다음 작업을 시작한 경우
# order[index].time이 jobEndtime 보다 큰 경우:
# 주문이 밀려있지 않아서 이전 작업을 끝내고 여우가 있는 경우.
# 다음 작업이 들어온 시점에 처리를 한다.
jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
result.append(index + 1)
targetQueue.pop()
while not(normalQueue.empty()==1 and vipQueue.empty()==1):
targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
index = targetQueue.front()
jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
result.append(index + 1)
targetQueue.pop()
return result6-1. 주문처리하기(2)
- 코드
from queue import Queue
class orderInfo:
def __init__(self, t, d, v):
self.time = t
self.duration = d
self.vip = v
def selectQueue(normalQueue, vipQueue, time, orders):
normalIndex = -1 if len(normalQueue.queue) == 0 else normalQueue.queue[0]
vipIndex = -1 if len(vipQueue.queue) == 0 else vipQueue.queue[0]
if vipIndex == -1:
return normalQueue
if normalIndex == -1:
return vipQueue
if time < orders[normalIndex].time and time < orders[vipIndex].time:
if orders[vipIndex].time <= orders[normalIndex].time:
return vipQueue
else:
return normalQueue
if time >= orders[normalIndex].time and time < orders[vipIndex].time:
return normalQueue
if time >= orders[vipIndex].time and time < orders[normalIndex].time:
return vipQueue
return vipQueue
def processOrder(orders) :
result = []
normalQueue = Queue()
vipQueue = Queue()
jobEndTime = 0
curTime = -1
len(normalQueue.queue)
for i in range(len(orders)):
curTime = orders[i].time
if orders[i].vip == 0:
normalQueue.put(i)
else :
vipQueue.put(i)
while jobEndTime <= curTime and not(normalQueue.empty() and vipQueue.empty()):
targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
index = targetQueue.queue[0]
jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
result.append(index + 1)
targetQueue.get()
while not(normalQueue.empty() and vipQueue.empty()):
targetQueue = selectQueue(normalQueue, vipQueue, jobEndTime, orders)
index = targetQueue.queue[0]
jobEndTime = max(jobEndTime, orders[index].time) + orders[index].duration
result.append(index + 1)
targetQueue.get()
return result7. 요세푸스 순열
- 문제
1번부터 N번까지 번호를 가진 N명의 사람들이 있습니다.
1번부터 순서대로 K번째 사람을 원에서 제거합니다.
원을 이루고 있는 사람들이 모두 제거되었을 때,
제거된 사람들의 번호를 순서대로 나열한 것을 요세푸스 순열이라고 합니다.
두 정수N과 K가 주어졌을 때의 요세푸스 순열을 리스트로 반환하는 함수 josephus_sequence를 작성하세요. - 코드
from queue import Queue
def josephus_sequence(n, k) :
# n명의 사람들을 큐로 표현한다.
q = Queue()
result = []
for i in range(1, n+1):
q.put(i)
# 요세푸스 순열 알고리즘에 의해서 큐에서 한명씩 사람이 빠지는데
# 사람이 다 빠지면 반복문 종료.
while not q.empty():
#(0~k-1)
for i in range(k):
num = q.get() # like pop임
if i == k-1:
result.append(num)
else:
q.put(num)
return result
智(지)! 德(덕)! 體(체)!