스택 | 탑

🎈문제 풀이

 

송신탑은 뒤에서 차례대로 하나씩 빼주기 때문에 Stack에 적합하다. 그런데 송신탑의 경우 수신탑보다 높이가 큰 것이 나올 때까지 계속 빼줘야 한다.

 

- 뺏던 것을 다시 집어넣어줘서 원상복귀를 시켜주거나(스택 하나만을 사용하는 경우), 송신자가 바뀔 때마다 수신자 스택을 새로 생성해줘야 한다. 

- answer에 위치 값을 저장해줘야 하기 때문에 송신자와 수신자의 위치 정보를 알고 있어야 한다.

 

 

🎈 소스 코드

static int[] solution(int[] heights) {
		Stack<Integer> stack = new Stack<>();
		int[] ans = new int[heights.length];

		for(int n : heights) stack.push(n);

		int sender, receiver;
		for(int i=heights.length-1; i>=0; i--) {
			sender = stack.pop();

			int cntNum = 0;
			while(!stack.isEmpty()) {
				receiver = stack.pop();
				cntNum++;
				if(receiver > sender) {
					ans[i] = i - cntNum + 1;
					break;
				}
			}

			for(int k=i-cntNum; k<i; k++) {
				stack.push(heights[k]);
			}
		}

		return ans;
	}

 

🎈 기억할 것

 

- 하나의 스택을 가지고 push/pop을 하며 원상복귀를 해야 하는 경우, 하나의 기준값 pivot을 가지고 for문을 돌린다.

- 위치 또는 index를 필요로 할 때 index 멤버변수를 가지고 있는 클래스를 만들거나, idx를 저장하는 배열을 만들자!