백준 STACK 풀이

2 minute read

백준에서 stack 풀이 만을 모아놓았다. 예전에 푼 것은 수정하기가 귀찮아서 그냥 올렸는데 앞으로 푸는 것은 풀이 과정도 정리해서 올릴 예정이다.

사용언어는 Python이다.

TOC를 통해 바로가기를 해보자.

10828 스택

문제보기
풀이보기
풀이법
- 탑의 배열을 준비한다.
- 배열을 iteration하며 stack에 집어넣는다.
- 만일 stack에 있는 탑의 높이가 현재 iteration 탑의 크기보다 작다면, stack에 있는 탑은 절대 신호를 수신하지 못하므로 pop해서 비교한다.

처음에는 바보처럼 탑 배열을 stack으로 넣고 pop하며 크기를 비교하느라 O(N^2)의 시간이 걸렸다. stack에 대한 이해가 부족하다는걸 느꼈다. 바보처럼 짠 코드는 다음과 같다.

while에서 탑의 배열을 한 번, 크기 비교를 위해 남는 stack에서 한 번, 총 2번의 iteration을 도는 것을 확인할 수 있다.

문제보기
풀이보기
풀이법:
길이를 넣다가 더 작은게 들어오면 pop해서 그때 계산하는 방법. 이러려면 idx를 통해 가로길이를 세야 함.
0: stack: [(0, 2)]. 처음엔 그냥 넣음.
1: stack: [(0, 2)]. (1, 1).
- 2 > 1 이므로,
  - 2를 pop. 넓이: 2 x (1 - 0) = 2.
  - (1, 1)은 pop된 데이터의 idx로 바꿔줌. (0, 1)append.
2: stack: [(0, 1)].
- 1 < 4 이므로 그냥 append.
3: stack: [(0, 1), (2, 4)].
- 4 < 5 이므로 그냥 append.
4: stack: [(0, 1), (2, 4), (3, 5)].
- 5 > 1 이므로
  - 5를 pop. 넓이: 5 * (4 - 3)
- 4 > 1 이므로
  - 4를 pop. 넓이: 4 * (4 - 2)
- (4, 1)은 pop된 데이터의 idx로 바꿔줌. (2, 1) append.
……
문제점:
- 내림차순으로 들어오면 큰 것들은 이미 pop했기 때문에 계산이 안됨. 따라서 마지막으로 pop한 (히스토그램에선 맨 앞) 자리에 값을 넣어줘야 함.
- 마지막은 iteration이 안돌아감. 따라서 배열에 [0]을 넣어줌.
- max(area)에서 런타임 에러 발생. 길이가 0인 경우를 못봄.

그냥 생으로 풀면 O(N^2) 나오므로 잘 생각해야 한다. 만약 코딩테스트에서 이런 문제를 봤다면, regular expression으로 풀었을 거 같은데, 이 경우에도 시간초과가 발생한다.

따라서 다음 방법으로 풀었었는데, kO(N) 정도가 되서 역시 실패하였다.

여기서의 실책은 while을 쓰느라고 reverse와 slice로 시간 복잡도를 증가한 것이다. 잘 기억해뒀다가 써먹으면 좋을 것 같다.

문제점: input부터 FIFO구존데? 뒤로 쓸 수 있나? -> for문으로 하면 FIFO가능 어떻게 합치지? extend는 부담스럽고, 또 앞에다가 더하는건 어떻게 하지? -> print(end=’‘)를 통해 한 줄로 이어서 출력이 가능.