[Python] 자료구조 - 스택 코딩 문제

 

 

이번에는 leetcode에서 스택 문제를 풀어봤습니다.

 

 

원하는 주제의 문제만 푸는 방법은

leetcode에서 이렇게 태그를 지정해주면

스택 문제 지정

 

풀고자하는 개념과 관련된 문제를 풀어볼 수 있습니다.

 

저는 이렇게 스택을 지정해줬습니다.

 

---

 

스택 구현

 

 

아래는 스택을 파이썬을 통해 구현하는

아주 기초적인 방법입니다.

 

stack = list()	리스트를 이용해 스택을 만들어 줍니다.
stack.append()	append 함수를 사용해 스택에 요소를 삽입합니다.
stack.pop()	pop 함수를 사용해 스택의 요소를 삭제합니다.

 

---

 

 

1번 문제

 

https://leetcode.com/problems/baseball-game/submissions/1346427011/

 

 

1번 코드

 

먼저 answer이라는 스택을 만들어줬습니다.

조건에 맞는 것의 추가는 append 그리고 삭제는 pop을 사용하여

코드를 구현해주었습니다.

 

1번 시간복잡도

 

 

2번 문제

 

https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/

 

2번 문제 코드

 

이번 문제는 따로 스택을 만들어줄 필요없이

students 리스트를 스택으로 사용해줘도 되는 문제였습니다.

 

students 리스트에서 append 함수를 사용해 요소를 삽입해주고

pop 함수를 사용해 요소를 삭제해주었습니다.

 

2번 시간 복잡도

 

 

3번 문제

 

https://leetcode.com/problems/clear-digits/description/

 

3번 문제 코드

 

이번에도 answer라는 스택을 만들어주고

요소 삽입에 append와 요소 삭제에 pop을 사용해줬습니다.

 

3번 시간 복잡도

 

 

 

---

 

 

스택의 개념이 매우 간단하여

문제에 적용하는 데 큰 어려움은 없었습니다..

 

다른 사람들이 푼 코드와 비교했을 때

크게 차이가 없는데도 불구하고

시간 복잡도와 공간 복잡도가

안좋게 나왔습니다..

 

어떤 이유인지 아직 파악하지 못했지만..

 

앞으로도 문제를 계속 풀어보며

시간 복잡도와 공간 복잡도를 개선하기 위해

노력해보겠습니다...