문제

https://programmers.co.kr/learn/courses/30/lessons/42588

코드

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public int[] solution(int[] heights) {
    Stack<Tower> st = new Stack<>();
    int[] answer = new int[heights.length];

    for (int i = 0; i < heights.length; i++) {
        Tower tower = new Tower(i + 1, heights[i]);
        int receiveIdx = 0;

        while (!st.isEmpty()) {
            Tower top = st.peek();

            if (top.height > tower.height) {
                receiveIdx = top.idx;
                break;
            }

            st.pop();
        }

        st.push(tower);
        answer[i] = receiveIdx;
    }

    return answer;
}

class Tower {
    int idx;
    int height;

    public Tower(int idx, int height) {
        this.idx = idx;
        this.height = height;
    }
}

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

흐름

  1. 탑의 index와 높이를 저장 할 Tower class 생성
  2. 탑의 개수만큼 반복
  3. 1 번쨰부터 시작되야하므로 현재 index에서 +1 한 index와 현재 높이를 갖는 tower를 생성
  4. tower가 저장된 stack이 비었는지 체크
  5. 비어 있지 않다면 stack의 맨 위를 가져와서 현재 tower의 높이와 비교함
  6. stack에 저장된 stack이 더 크다면 현재 타워에 전파를 받을 타워이므로 index를 receiveIdx 변수에 할당
  7. 크지 않다면 stack에 저장된 tower를 pop함
  8. stack에 현재 tower를 push
  9. answer에 아까 저장한 receiveIdx를 저장
  10. answer return
  11. 끝

결과

번호 속도
테스트 1 통과 (1.89ms, 50.7MB)
테스트 2 통과 (1.84ms, 52.6MB)
테스트 3 통과 (1.96ms, 52.3MB)
테스트 4 통과 (2.04ms, 52.5MB)
테스트 5 통과 (2.02ms, 50.8MB)
테스트 6 통과 (2.28ms, 52.7MB)
테스트 7 통과 (1.78ms, 52.6MB)
테스트 8 통과 (2.06ms, 52.1MB)

테스트 케이스

1
2
3
assertArrayEquals(new int[] {0,0,2,2,4}, test.solution(new int[] {6,9,5,7,4}));
assertArrayEquals(new int[] {0,0,0,3,3,3,6}, test.solution(new int[] {3,9,9,3,5,7,2}));
assertArrayEquals(new int[] {0,0,2,0,0,5,6}, test.solution(new int[] {1,5,3,6,7,6,5}));