BOJ_2493_탑

1.

구분: 자료구조 - 스택

언어: Java

전략: 

• 왼쪽을 매번 헤매면서 보지 않기 위해서 새로운 기지국을 만날 때 마다 기억을 한다. 
• '기억 공간'에 높이와 자리를 저장한다. 
• 기억이 없으면 0을 나에게 부여한다. 
• 기억이 나보다 작으면, 그 기억을 버리고 내 높이와 번호를 기억 공간에 넣는다.
• 기억이 나보다 크면, 내가 그 기억의 번호를 부여 받고, 내 번호와 높이를 기억 공간에 넣는다. 
• 이 기억 공간을 스택으로 한다 - 내 기준 내 앞에 가장 먼저 신호를 받을 수 있는 곳이어야 하기 때문에
• 입력은 BufferedReader로 받는다. 시간초과를 방지할 수 있다. 

---

2. 코드

처음 ~ 스택, 변수, 배열 등 필요한 것들을 선언 및 생성

핵심 코드

---

3.

1번째 시도 --> 메모리 초과 

- 처음부터 모든 숫자를 스택에 넣고(stack1), 매 round마다 스택을 복사해서 새로 생성(stack2), 뺀 값들을 다시 넣을 스택 생성(stack3), 결과를 넣을 스택 생성(stack4)

- 매 round마다, 해당 순서가 나올때까지, 기지국을 하나하나 다 꺼내고, 그 다음부터는 작은 것들은 stack3에 넣고, 큰게 나오면 해당 번호(이것을 구하기 위해 연산을 또 진행)를 stack4에 넣고, stack3에서 모두 pop하여 stack2에 삽입

-메모리 초과가 날 법도 하다....

 

2번째 시도 --> 시간 초과 

- 1번째 시도와는 다르게 처음에 stack에 넣는 대신, 입력 받(na)은 것을 대상으로 stack이 비어있으면 0을 결과에, 꼭대기가 나보다 크면 그 당시 stack의 사이즈를 결과에 넣고, 나보다 작으면 backup에 pop한 값을 넣는다.

-  na에 대한 결과값이 나오면, na를 stack에 push