[Algorithm 풀이] 백준 - 22866번 탑 보기

대표적인 Stack 응용 문제인 것 같아서 풀이를 가져왔다! 백준 GOLD 3 문제이며, 처음 풀었던 풀이가 예제는 맞았으나 시간초과가 났다. 그래서 조금 더 효율적인 풀이 방법을 찾아서 정리해본다! 🌟

 

문제

 

입력

첫번째 줄에 건물의 개수 N이 주어진다.

두번째 줄에는 N개의 건물 높이가 공백으로 구분되어 주어진다.

8
3 7 1 6 3 5 1 7

출력

 i(1 <= i <= N)번째 건물에서 볼 수 있는 건물의 개수를 출력한다.

만약 볼 수 있는 건물의 개수가 1개 이상이라면 i번째 건물에서 거리가 가장 가까운 건물의 번호 중 작은 번호로 출력한다.

1 2
0
3 2
2 2
4 4
3 4
4 6
0

 

코드

1. 시간 초과가 났던 코드

처음에 for 문을 두번 돌면서 전체 탑들을 비교하는 방법으로 풀었으나 O(N^2) 시간이 걸렸다. 그래서 생각 끝에 풀이를 참고하게 되었다. 

N = int(input())
buildings = list(map(int, input().split()))

stack = []
cnt_list = []
for i in range(len(buildings)): #start 
    tmp = []
    cnt = 0
    flag = False
    max_h = buildings[i]
    for j in range(i+1, len(buildings)):
        
        if buildings[j] > max_h:
            flag = True
            tmp.append(j+1) # idx 
            cnt += 1
            max_h = buildings[j]
            
    max_h = buildings[i]       
    for k in range(i-1,-1,-1):
        if buildings[k] > max_h:
            flag = True
            cnt += 1
            tmp.append(k+1) # idx
            max_h = buildings[k]
    
    if flag == False:
        cnt_list.append(0)
        stack.append([])
    else:
        cnt_list.append(cnt)
        stack.append(tmp)
    
#출력
for i in range(N):
    prev_num = 100000
    answer = 0
    print(cnt_list[i], end=' ')
    if not stack[i]:
        print('')
    else:
        for num in sorted(stack[i]): #기준 건물과 가장 가까운 건물, 인덱스가 가장 작은 건물 순
            if prev_num > abs(i+1-num):
                answer = num
                prev_num = abs(i+1-num)
        print(answer)

2. 풀이 참고 코드

3가지로 나눠서 생각해 봐야 한다.

1. 각 건물에서 좌측으로 보이는 건물 갯수

2. 각 건물에서 우측으로 보이는 건물 갯수

3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호

일단, '각 건물에서 좌측으로 보이는 건물의 개수'를 어떻게 구할지 생각해본다. 2) i번 건물을 확인할 때 스택에 현재 높이 보다 낮거나 같은 걸 전부 빼버린다. 3) 남은 것(스택의 사이즈)이 현재 건물에서 좌측으로 볼 수 있는 건물의 갯수이다. 4) 스택의 가장 맨 위에 있는 것이 현재 건물과 가까운 건물이다. 이 과정으로 모든 건물에서 좌측으로 보이는 건물의 갯수와, 좌측으로 가장 가까운 건물의 번호를 알 수 있다. 

우측으로 보이는 건물은 위 과정을 반대로 하면 된다. 즉, 스택에 반대 순서로 넣었다 빼면 된다. 그럼 각 건물에서 우측으로 보이는 건물의 개수와, 우측으로 가장 가까운 건물의 번호를 알 수 있다. (가까운 건물의 거리가 동일하면 작은 건물 번호를 출력)

그리고 건물의 높이만이 아니라 건물 번호도 함께 넣는 것을 필요가 있다. 

 

N = int(input())
buildings = list(map(int, input().split()))

stack = []
# 현재 stack에 저장된 값들은 현재 건물에서 좌측 or 우측으로 보이는 건물의 수.
# 마지막 값은 가장 가까운 건물.
cnt_list = [0] * (N+1)
near = [[int(1e9), int(1e9)] for _ in range(N+1)] 
# near[a][0] : a 건물에서 가장 가까운 건물 번호
# near[a][1] : a 건물에서 가장 가까운 건물 거리

#좌측
for idx, v in enumerate(buildings):
    while len(stack) > 0 and stack[-1][1] <= v:
        stack.pop()
    cnt_list[idx+1] += len(stack)
    
    if len(stack) > 0:
        g = abs(stack[-1][0] - (idx+1))
        if g < near[idx+1][1]:
            near[idx+1][0] = stack[-1][0]
            near[idx+1][1] = g
        elif g == near[idx+1][1] and stack[-1][0] < near[idx+1][0]:
            near[idx+1][0] = stack[-1][0]
    stack.append([idx+1,v])

#우측
stack = []
for idx, v in reversed(list(enumerate(buildings))):
    while len(stack) > 0 and stack[-1][1] <= v:
        stack.pop()
    cnt_list[idx+1] += len(stack)
    
    if len(stack) > 0:
        g = abs(stack[-1][0] - (idx+1))
        if g < near[idx+1][1]:
            near[idx+1][0] = stack[-1][0]
            near[idx+1][1] = g
        elif g == near[idx+1][1] and stack[-1][0] < near[idx+1][0]:
            near[idx+1][0] = stack[-1][0]
    stack.append([idx+1,v])
    
for i in range(1, N+1):
    if cnt_list[i] > 0:
        print(str(cnt_list[i]) + ' ' + str(near[i][0]))
    else:
        print(0)