Stack 백준 문제
백준에서 스택부분의 문제를 풀었는데 실버까지만 해도 그냥 push,pop등 이 개념만 가지고도 문제가 풀려서 스택을 이용한 문제가 별로 어렵지 않다고 생각했지만 골드만 가도 스택문제가 어렵다는 것을 느꼈다
2493번 탑
문제는 탑의 크기를 주어졌을 때 오른쪽에서 왼쪽으로 레이저를 쏠 때 가장 먼저 만나는 탑의 인덱스를 출력하는 문제다 문제를 처음 보고 스택 문제인지 파악을 못하고 단순히 입력받은 데이터를 거꾸로부터 반복문을 반복하면서 현재 값보다 크면 해당 탑의 인덱스를 저장하는 방식으로 풀었다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
n = int(sys.stdin.readline())
tower = list(map(int,sys.stdin.readline().split()))
list1 = []
for i in range(n):
if i == 0:
list1.append(0)
else:
for j in range(i, -1,-1):
#print(j)
if tower[i]<tower[j]:
list1.append(j+1)
break
if j == 0:
list1.append(0)
이렇게 코드를 구현했지만 2중 for문을 해서 그런지 시간 초과가 나왔다 여기서 해메면서 스택을 이용한 알고리즘 중 단조 스택을 알게 되었다
단조 스택
단조 스택이란 특정한 순서를 유지하면서 요소를 저장하는 스택이다 오름차순 또는 내림차순의 단조성을 가진다
- 단조 증가 스택: 스택 내부의 값이 오름차순으로 유지
- 단조 감소 스택: 스택 내부의 값이 내림차순 유지
다음 큰 값 찾기, 범위 내 최소, 최대 계산등에 활용 가능한데 다음 큰 값 찾기를 이용할 것이다
그렇다면 위 문제를 이제 스택을 이용해서 다르게 접근해야한다 문제를 보면 탑의 리스트에서 왼쪽 방향으로 자신보다 크고 가장 가까운 값을 찾는 문제이다 왼쪽에서 오른쪽 방향으로 갈거기 때문에 오른쪽값이 더 크면 신호를 받을 수 없다 그래서 그전 탑에서 보낸 신호를 받게 된다
뒤가 더 작으면 push하고 맨앞부터 뒤로 비교를 시작할 때 뒤가 더 크다면 신호를 받을 수 없으므로 pop하고 해당 인덱스에 0을 넣는다 (신호를 받을 수 없기 때문에)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
n = int(input())
arr = list(map(int,sys.stdin.readline().split()))
answer = [0] * n
stack = []
for i in range(n):
if stack:
while stack:
if arr[stack[-1]] < arr[i]:
stack.pop()
else:
answer[i] = stack[-1] + 1 # 인덱스에 수신탑 인덱스 + 1 대입입
break
stack.append(i)
else:
answer[i] = 0
stack.append(i)
print(*answer)
6198번 옥상 정원 꾸미기
이번 문제도 비슷한 문제로 옥상에서 볼 수 있는 다른 건물의 옥상 개수를 구하는 것이다 이전 문제와 다른 점은 인덱스를 구하는것이 아니라 볼 수 있는 옥상의 개수를 구하고 그 방향이 오른쪽 이라는 점이 다른 점이지만 기본 구조는 오른쪽에서 나랑 가까우면서 나보다 큰 숫자를 찾는 문제이다 따라서 스택이 비어 있다면 인덱스를 추가하고 스택의 top 인덱스를 이용해서 지금 빌딩의 크기와 비교한다 만약 지금 빌딩이 더 크다면 pop을하고 (지금 인덱스 - 스택에서 pop한 데이터) 계산을 통해서 사이에 속한 빌딩의 개수를 구 할 수 있다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 처음 전체 입력 개수를 입력하고
import sys
n = int(sys.stdin.readline())
stack = []
ans = [0] * n
tower = []
for _ in range(n):
k = int(sys.stdin.readline())
tower.append(k)
for i in range(n):
while stack:
if tower[stack[-1]] > tower[i]:
stack.append(i)
break
else:
a = stack.pop()
ans[a] = i -a -1
if len(stack) == 0:
stack.append(i)
if stack:
t = stack.pop()
while stack:
f = stack.pop()
ans[f] = t-f
#print(ans)
print(sum(ans))
마지막까지 스택에 남아있다면 마지막 스택값이 제일 작다는 경우라(높이가 6,4,3 이렇게 끝나면 스택에 3개가 남음) 해당 인덱스 사이 개수를 구하면 된다
17298번 오큰수
이번 문제는 리스트를 받아서 오른쪽 데이터 중 가까우면서 큰값을 찾는데 인덱스나 그 사이 개수를 구하는게 아니라 값 자체를 구하는것이다 더큰 값이 없다면 -1을 표시하기 떄문에 응답 리스트를 -1로 초기화한다 그후 왼쪽에서 오른쪽으로 확인하면서 비어있다면 스택에 넣고 스택에 데이터가 있다면 지금 데이터와 크기를 비교한다 크기가 더 작다면 push더 크면 해당 값 자체를 ans[stack[-1]]에 넣으면 된다 마지막에도 스택에 데이터가 남아있다면 내림차순으로 데이터가 들어온것이라 그냥 둔다 ans기본값이 -1로 되어있기 때문에
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
n = int(sys.stdin.readline())
stack = []
ans = [-1] * n
tower = list(map(int,sys.stdin.readline().split()))
for i in range(n):
while stack:
if tower[stack[-1]] < tower[i]:
a = stack.pop()
ans[a] = tower[i]
else:
stack.append(i)
break
if len(stack) == 0:
stack.append(i)
print(*ans)
17299번 오등큰수
이전 문제들과 비슷해서 도전을 해봤다 이런 단조스택 문제는 스택을 이용하는데 값을 비교하는 연산에 따라 문제가 달라지는것 같다 이 문제는 가까우면서 큰수를 찾는데 그 큰수가 값이 아닌 출연 빈도수였다 그래서 난 빈도수를 리스트에 저장하기위해서 리스트의 count()를 사용했는데 거의 2중 for문과 비슷한 속도라서 다른 방법을 찾아야했다
그래서 딕셔너리를 이용했다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys
n = int(sys.stdin.readline())
stack = []
ans = [-1] * n
tower = list(map(int,sys.stdin.readline().split()))
count = {}
for i in tower:
if count.get(i):
count[i]= count[i]+1
else:
count[i] = 1
for i in range(n):
while stack:
if count[tower[stack[-1]]] < count[tower[i]]:
a = stack.pop()
ans[a] = tower[i]
else:
stack.append(i)
break
if len(stack) == 0:
stack.append(i)
print(*ans)