[프로그래머스] - 탑

문제

 

조건

 

입출력 예제

 

솔루션

1. 스택 자료구조를 사용하였다. 
   • why ?) FILO 형식으로 뒤에서부터 진행하고, 신호가 수신된 탑은 고려할 필요가 없어 스택을 사용하면 다루기가 편할거라 생각.
2. 몇 번째 탑이고, 높이 크기가 얼마나 되는지 관리하기 위해 Top 클래스를 정의한다.
3. idx는 현재 비교하려는 탑이 몇 번째 인덱스인지 현재 위치를 의미하는 변수이다.
4. 스택 두개를 만들어 stack은 입력으로 주어진 탑들을 순서대로 집어넣고 다시 꺼내기 위한 변수이며, wait은 이전 탑보다 높이가 큰 탑들을 담아놓기 위한 스택 (자기보다 높이가 큰 탑이 나올때까지 대기) 이다.
5. stack에 현재 탑 정보를 Top 객체로 만들어 Push() 한다. 그리고 처음 answer에 모두 0으로 초기화 (수신이 되지 않는다면 그대로 0일 것이고, 수신이 된다면 아래 반복문에서 0 -> 수신된 탑 인덱스로 바뀔 것이다) 를 해준다.
6. stack이 빌 때까지 반복문을 수행한다.
   1. stack의 맨 위 탑을 Pop() 하여 wait에 Push() 하고, idx를 1 감소시킨다.
   2. stack이 비었거나 (stack.size() <= 0), stack의 꼭대기 탑의 높이가 wait의 꼭대기 탑의 높이보다 작거나 같다면 (수신하지 못한다), continue해서 다시 루프의 처음부터 수행한다.
   3. 위 조건에 해당되지 않는다면, wait이 비어 있지 않으면서, stack 꼭대기 탑 높이가 wait 꼭대기 탑 높이보다 작거나 같은 탑을 찾을 때까지, wait에 들어있는 탑의 인덱스에 위치하는 answer 배열 (answer[wait.pop().idx]) 에 현재 idx 값을 삽입한다.
7. answer를 반환한다.

 

Code

• 전체 코드 : https://github.com/SubAkBa/Algorithm_Chung_Son/blob/master/Programmers/Solution_top.java

탑의 인덱스, 높이를 저장할 객체를 만드는 Top 클래스

solution 함수

 

결과