문제

탑

풀이

문제가... 왜이렇게 골드가 쉽지... 했지만 역시나 시초납니다. 뭔가 이상하다 했다..

//틀린코드
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
	int index = i;
	while (index >= 0) {
		if (arr[index] > arr[i]) {
			sb.append(index).append(" ");
			break;
		}
		index--;
	}
	if (index < 0) {
		sb.append(0).append(" ");
	}
}

갑자가 포스트 하다가 키보드가 빠져서;; 차후 설몀믄 나줌메 ....;;;;
코드 만 밀단 곰개 함다

StringBuilder sb = new StringBuilder();
Stack<int[]> s = new Stack<>();

for (int i = 1; i <= n; i++) {
	while (!s.isEmpty()) {
		if (arr[i] < s.peek()[1]) {
			sb.append(s.peek()[0]).append(" ");
			break;
		}
		s.pop();
	}
	if (s.isEmpty()) {
		sb.append(0).append(" ");
	}
	s.push(new int[] {i, arr[i]});
}

기존코드메서 조금만 고치면 되는 건데 믄근히 생각해내기 힘들머따;;

키보드 부착하고 옴..

이 문제는 이전에 있었던 값들 중에 제일 큰 값이 현재값보다 크면 그 값을 출력하기만 하면 되는 문제이다. 그리고 만약 출력할 값이 없다면 현재 값이 제일 큰 경우이기 때문에 0을 출력해준다.

스택인 이유는 현재 데이터가 바로 이전에 있었던 값을 중에 제일 큰 값만 비교해주면 되기 때문에
6다음 9가 출력되었을때 그 다음값인 5는 6과 비교해줄 필요가 없기 때문이다. 이런 경우 작은 값이 들어올때 바로 pop()해주어 비교대상에서 바로 제거 할 수 있다. 하지만 이것만으로는 스택이어야 한 이유가 충분하진 않다. 결정적인 이유는 현재값을 push()해주는 내용 때문인 것 같다.

문제에서 주어진대로 현재 탑에서 가장 가까우면서 현재탑보다 큰 탑이 송전탑이 되기 때문이다. 이렇게 하면 다음에 비교대상으로 올 현재 탑이 가장 가까운 데이터들 부터 비교하여 연산을 적게 할 수 있을 것이다.
문제는 언제나 답을 주고 있는데 놓칠 수 있는 정보들중에도 단서가 있다.

전체 코드

전체 코드