[내일배움캠프 16일차 TIL] 백준 10828 스택 with python

항상 프로그래머스로 문제 풀다가 백준으로 하니까 적응이 어렵다... 프로그래머스는 그냥 함수만 제출하면 되는데 백준은 input값을 넣어야 하고,,, 테스트케이스에 대한 정보도 없고,,, 아직 적응해나가는중이지만 차차 적응하겠지...!

---

스쿼드 숙제 중 하나인 문제였다! 사실 파이썬에서는 리스트를 사용해서 스택 문제를 풀면 아주 쉽게 풀리지만

 

 

뭐가 문제인지 python3로 제출했다가 자꾸 시간초과가 떠서 pypy3로 제출해서 통과했다....

그러면 코드에는 문제가 없다는 말 같은데... 혹시나 리스트를 사용해서 문제가 생기는건가 싶어 스택을 클래스로 직접 구현해서 문제를 풀어보기로 했다!

 

 

강의 내용을 떠올려가며,,, 사실 컨닝도 좀 했다

스택의 구현에 필요한 Node와 Stack 클래스를 만들었다

Node 클래스에는 value와 next 어트리뷰트를 가지고,

Stack 클래스에는 push, pop, size, empty, top 메소드를 작성해야 한다.

 

사실 스택 강의를 들으면서 강사님이 구현하는걸 봤을 땐 나도 할 수 있을 것 같았는데 아니었다...

클래스를 작성하면서 얼마나 많은 에러를 만났는지 모르겠다...

 

노드의 next가 다음 노드를 가르킨다는걸 머리로는 이해했는데 실제로 구현하고 작동시키려하니 어려웠다,,

이미지도 이전에 작성한 스택과는 좀 다른 느낌이었다.

실제로 스택을 구현하고 사용하면서 든 생각은 아래 이미지같았다

 

 

이런 느낌으로 생각을 하니 조금 더 이해가 되는 듯 했다.

pop을 하면 가장 밖의 테두리가 없어지고 그 다음이 Top이 되는 방식?

 

 

하지만 클래스로 스택을 구현하고 나서도 여전히 시간초과라는 결과를 얻었다...

물론 같은 코드를 pypy3로 제출하면 통과를 했다

 

그래서 결국 구글링을 통해 알아낸 결과

입력 받을 때 input을 사용해서 런타임 에러가 나는 것이라고 한다....

진짜 너무 허무했다.....

 

 

input 대신에

sys.stdin.readline()을 사용하면 된다고 한다...

다만 input 대신 sys.stdin.readline을 사용하면 숫자가 아닌 문자열로 입력을 받는 경우에 줄바꿈까지 입력으로 받는다고 한다!

 

그렇게 다시 시도한 결과!

 

시간이랑 메모리 둘 다 단축된 것을 확인할 수 있었다!!!

백준 10828번 제출 코드 링크

 

 

---

스택이랑 큐를 리스트, 파이썬 라이브러리인 deque를 이용해서 문제를 푸는 것은 어렵지 않지만 개념만 알고 사용해서 푸는거랑 직접 스택을 구현하고 구현한 스택을 이용해서 문제를 푸는 것은 정말 천지차이였다,,,,,

코딩이 아무리 오픈북이라곤 하지만 컨닝하지 않고도 혼자서 스택 구현할 수 있도록 노력해야지..!

 

 

구현한 스택으로 문제가 풀려서 신나! 만세!