미소를뿌리는감자의 코딩
[백준 2024/09/10] 2493번 탑 본문
728x90
1. 문제
https://www.acmicpc.net/problem/2493
2. 접근 방법
2개의 stack을 이용해서 푸는 것이 적절하다고 생각하였다.
쏘기 전의 레이저들을 모아놓은 것을 b_shoot이라고 선언하였다.
또한, [높이, 송신탑 번호] 로 저장해 두어, 추후에 레이저를 쏜 송신탑 번호를 계산하도록 하였다.
b_shoot에서 하나 pop한 후,
a_shoot에 저장된 값의 높이가 pop된 높이보다 작다면, 해당 a_shoot 위에 있는 블록이 b_shoot에서 pop 된 송신탑을 때린다고 생각하면 된다.
따라서, hit = [0] * n 으로 선언된 곳에, hit[b_shoot에서 pop된 송신탑 번호 -1 ] 로 저장하면 된다.
만약, 작다면, break를 한 후, a_shoot에 하나의 새로운 블록을 추가하게 된다. (b_shoot에서 pop 된 블록)
이후, b_shoot에서 새로운 블록을 pop하여 위 과정을 반복한다.
또한, a_shoot에서는, 항상 h가 오름차순으로 쌓이게 된다.
따라서, 하나라도 새로운 높이가 맨 위 블록의 a_shoot이 큰 값을 가진다면 break를 할 수 있는 것이다.
즉, a_shoot의 밑 블록을 확인하지 않아도 만족하지 않을 것임을 알 수 있다.
3. 코드
def laser(n):
hit = [0] * n
b_shoot = []
temp_shoot = list(map(int, input().split()))
for i in range(len(temp_shoot)):
b_shoot.append([temp_shoot[i], i + 1])
a_shoot = []
while b_shoot:
n_h, n_i = b_shoot.pop()
while a_shoot:
if n_h > a_shoot[-1][0]:
o_h, o_i = a_shoot.pop()
hit[o_i - 1] = n_i
else:
break
a_shoot.append([n_h, n_i])
return hit
if __name__ == "__main__":
hit = laser(int(input()))
print(" ".join(map(str, hit)))
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/11] 3190번 뱀 (0) | 2024.09.11 |
---|---|
[백준 2024/09/11] 2504번 괄호의 값 (0) | 2024.09.11 |
[백준 2024/09/10] 1629번 곱셈 (0) | 2024.09.10 |
[백준 2024/09/10] 2630번 색종이 만들기 (0) | 2024.09.10 |
[백준 2024/09/10] 8983번 사냥꾼 (0) | 2024.09.10 |