[BOJ] 백준 2493 탑 (JAVA)

스택!

📑 문제

 

백준 2493 탑

---

🌱 아이디어

수열의 오른쪽 끝에서 왼쪽으로 탐색하면서 두 수를 비교하면서 스택에 push, pop을 한다!

 

이 문제를 풀기 위해서 공식을 총 2가지로 단순화했다

 

1. 왼쪽 숫자보다 오른쪽 숫자가 크다면 -> 스택에 push

2. 왼쪽 숫자보다 오른쪽 숫자가 작다면 -> 스택에 pop

 

하지만 출력조건은 레이저를 수신한 탑의 인덱스를 출력하기 때문에 스택에는 인덱스 번호에 해당하는 숫자가 아닌

숫자에 해당하는 인덱스 번호를 입력한다. 즉 arr1 [i]가 아니라 'i'를 스택에 입력을 해야 한다.

---

🌱 코드 및 풀이

1. 왼쪽 숫자보다 오른쪽 숫자가 크다면 -> 스택에 push

   stk.push(i)를 통해 인덱스 번호 입력

2. 왼쪽 숫자보다 오른쪽 숫자가 작다면 -> 스택에 pop

   while을 통해 현재 arr1 [i] 보다 stk.peek가 작거나 같다면  ans 배열에 스택에 저장된 인덱스 번호로 지정하고 i를 입력한다.

   조건에 부합하지 않을 때까지 반복한다

---

🌱 느낀 점

전에는 분명 풀어도 시간초과 나게 구현했을 텐데 자료구조와 구현을 틈틈이 공부를 했기 때문에

가볍게 해결할 수 있었던 것 같다 ㅎㅎ 그리고 이런 유형의 문제들을 자주 풀어본 게 도움이 되었다