Today I learned
2022/01/18
회고록
1/18
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
9장 스택, 큐
1. 이론
- 파이썬과 큐(Queue)
서두에서 설명했지만 가장 먼저 입력 된 데이터가 가장 먼저 출력되는 구조이다. FIFO(First In, First Out)라고 부르기도 하며 반대로 LILO(Last In, Last Out)이라고 설명하기도 한다. 현실세계에서 식당에서 줄을 서는 경우를 큐의 예시로 들 수 있다. 먼저 줄을 선 순서대로 식당에 입장한다.
큐에서 알아두어야 할 용어가 있는데 Enqueue(인큐), Dequeue(디큐)이다.
-. Enqueue : 큐에서 데이터를 입력하는 기능
-. Dequeue : 큐에서 데이터를 꺼내는 기능
추가로 파이썬에서는 queue라는 내장 모듈을 제공한다. 아래 예시로 든 그림을 통해 코드를 작성해보았다. put( )은 큐에 데이터를 넣을 때 사용하는 메서드, get( )은 큐에서 데이터를 꺼내는 메서드이다
<코드>
import queue
#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))
#선언 된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)
#큐 객체에서 입력된 객체 하나씩 꺼내기 :FIFO
print(data.get())
print(data.get())
print(data.get())<결과>
<class 'queue.Queue'>
2
5
8숫자 2,5,8을 순서대로 넣고 get( )을 3번 하면 먼저 입력 된 순서대로 출력된다.
queue 내장 모듈 내에는 기본적인 Queue( ) 클래스 외에도 LifoQueue( ), PriorityQueue( ) 클래스가 존재한다. 여기서 자세히 다루진 않겠지만 LifoQueue( )는 스택과 같은 LIFO 구조, PriorityQueue( ) 는 사용자가 우선순위를 지정한대로 데이터를 꺼낼 수 있는 구조라고 보면 될 것 같다.
- 파이썬과 스택(Stack)
스택은 나중에 입력 된 데이터가 먼저 출력되는 LIFO(Last In, First Out) 자료 구조이다. 반대로 FILO(First In, Last Out)라고 부르기도 한다. 예시로 들만한게 하노이의 탑 게임을 들 수 있다. 하노이의 탑 게임에서는 스택과 같이 원판을 무조건 위에서부터 빼야 한다(마지막에 들어간 원판부터). 중간에서 빼는건 불가능하다.
스택에서는 Push, Pop이라는 용어가 있다.
-. Push : 데이터를 입력하기
-. Pop : 데이터를 꺼내기(마지막으로 입력 된 순서부터)
위 그림을 파이썬으로 구현하려면 리스트를 선언해 append를 통해 데이터를 넣는다.(=Push)
꺼낼 때는 리스트의 pop( ) 함수를 사용하면 된다.
<코드>
#빈 리스트 선언
stack = []
#2,5,8 차례대로 리스트에 추가하기(=Push)
stack.append(2)
stack.append(5)
stack.append(8)
#값이 모두 입력된 리스트 출력하기
print("stack : ", stack)
#리스트 pop함수 통해 마지막으로 입력된 데이터 순 출력
print("첫번째 pop")
print(stack.pop())
print(stack)
print("두번째 pop")
print(stack.pop())
print(stack)
print("세번째 pop")
print(stack.pop())
print(stack)<결과>
stack : [2, 5, 8]
첫번째 pop
8
[2, 5]
두번째 pop
5
[2]
세번째 pop
2
[]위 결과를 보면 알겠지만 pop( ) 한번 실행할 때마다 리스트의 마지막 요소가 출력되고 없어지는 것을 확인할 수 있다.
2. 문제
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc"
Output: "abc"
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Constraints:
1 <= s.length <= 10^4
s consists of lowercase English letters.
https://leetcode.com/problems/daily-temperatures/
3. MySol
import collections
import re
def solution(inputStr):
counter = collections.Counter(inputStr)
stringSet = sorted(set(inputStr))
print('counter : ' + str(counter))
print('sorted(set(inputStr)) : ' + str(stringSet))
result=[]
result.append(inputStr)
for char in stringSet:
result=charOnePreserver(result,char)
print('result : ' + str(result))
result.sort()
print('sorted result : ' + str(result))
res = result[0]
return res
def charOnePreserver(input, char):
result = []
inputStrList = []
# 반복시마다 문자열을 초기값으로 돌려놓음
inputStrList.append(input)
print('==========================CHAR : ' + char)
for _str in input:
idxInInput = []
for m in re.finditer(f'{char}', _str):
idxInInput.append(m.start())
# i 만 살리고 나머지 지우기 로직
for i in range(len(idxInInput)):
# 반복시마다 문자열을 초기값으로 돌려놓음
inputStr = _str
target = idxInInput[i]
print(
'---------------------idxList : ' + str(idxInInput) + ', i : ' + str(i) + ', preserve target : ' + str(
target))
# 만약 inxInInput len이 1이면, break
if len(idxInInput) == 1:
result.append(inputStr)
print('can not delete char : ' + char)
break
find_num = 0
del_helper = 0
# i 번째 문자만 살리고 나머지 삭제하기
for m in re.finditer(f'{char}', inputStr):
print('char!!!! : ' + char + ', inputStr : ' + inputStr + ', find_num : ' + str(
find_num) + ', i : ' + str(i))
if find_num == i:
# 보존
print('preserve : ' + inputStr)
else:
# 삭제
del_idx = m.start() - del_helper
print('del_idx : ' + str(del_idx))
print('before inputStr : ' + inputStr)
inputStr = inputStr[:del_idx] + inputStr[del_idx + 1:]
print('after inputStr : ' + inputStr)
del_helper += 1
find_num += 1
result.append(inputStr)
print('++++++++++++++++++++result :' + str(result))
return result
if __name__ == '__main__':
input = 'ghadedfaih'
result = solution(input)
print('result : ' + result)
4. 배운 점
- 얼핏 보기엔 엄청 쉬운 문제라고 착각할 수 있다.
하지만, 해당 문제는 굉장히 어려웠다. (내 수준에서는)
반복된 문자를 지우는 것 뿐만 아니라 순서도 맞아야 한다.
사전순서가 알맞기 위해서는 고려해야 하는 것들이 많았다.
반복문을 이용하여 반복되는 문자를 하나만 남기고 지우는 모든 경우의 수를 구하는 로직을 구하여, 사전순으로 정렬한 후 출력하였다.
효율성 부분에서 좋지 못해 당연히 위 나의 솔루션은 통과하지 못했으며, 책에 나와있는 해답대로 재귀를 이용하거나, 스택을 이요한 문자 제거가 효율적인 방법이다.
반복문으로 문제를 푸는 습관을 줄이고, 스택과 큐를 이용하여 문제를 풀어야 한다.
5. 총평
스택 훈련을 해야 했으나, 반복문 훈련을 해버렸다.
