위에 사진에서는 각 관리인이 보이는 타워를 말하고 그 갯수를 세면 총 5개이다. 문제의 해답이 5라는 것이다.
1번. 2중 for문 풀이
처음에 이문제를 보면 2중 for문 사용해서 자신보다 큰 빌딩이 나오기 전까지의 빌딩의 갯수를 합하면 된다고 생각했지만 문제는 입력의 조건이였다.
빌딩의 갯수가 최대 8만개인데 시간 제한은 1초(1억)이다. 그렇다면 2중 for문으로 시간 복잡도가 O(n2)이 되버리면 보나마나 시간제한이 표시 될 것이다. 때문에 다른 방법이 필요했다
2번. stack 사용
stack을 사용해서 빌딩의 갯수를 확인할 수 있다.
stack을 사용하는 것의 가장 중요한 점은 바로 "언제 값을 push하고 언제 값을 pop하느냐"가 가장 큰 관건이다. 이번 문제도 마찬가지이다.
어떻게 하면 10의 빌딩이 뒤에 빌딩들 중 자신보다 작은 빌딩의 갯수를 잴 수 있을까?
처음에는 2개의 stack을 활용해볼까? 라는 생각을 했지만 이것또한 좋은 생각이 아니다. 공간복잡도에도 좋지 않고 stack을 효과적으로 사용하고 있지 않는다라는 생각이 계속해서 들었다.
그렇다면 stack을 한개만 사용해서 문제를 풀 수 있는 방법이 무엇이 있을까? 관점을 바꾸면 코딩이 쉬워진다
내려다보는 것이 아닌 올려다보는 빌딩 관리자가 보이는 빌딩의 갯수
이 문구가 정말 중요하다.
그렇다면 stack 문제가 아주 간단해지기 때문이다.
코딩의 순서를 말해보자
빌딩의 높이를 받고 자신보다 낮은 건물이 스택에 들어있는지 확인하고 만약 자신보다 낮은 건물이 스택에 들어있다면 모두 스택에서 제외한다.
현재 스택에 남아있는 건물들( 나보다 높은 건물들 )의 갯수를 누적합에 더한다
자신의 건물을 스택에 넣는다.
이걸 그림으로 표현하면 이렇게 된다
높은 애들이 숫자를 말해주는 것이 아닌 낮은애들이 말해주면 되는것이다.
💥 주의!!!
이런 조건이 있다 때문에 최악의 상황에 누적합을 하게 되면 int범위(21억)을 아득히 넘어버리기 때문에 누적합의 수를 long으로 잡아주어야 한다
코드
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Stack<Integer> stack = new Stack<>();
long sum = 0;
for (int i = 0; i < N; i++) {
int target = Integer.parseInt(br.readLine());
while (!stack.isEmpty()) {
if (stack.peek() <= target) {
stack.pop();
} else break;
}
sum += stack.size();
stack.push(target);
}
System.out.println(sum);
}
이 코드에서 가장 중요한것은 누적합을 하는 타이밍이다. 해당 건물의 입장에서 보는 것이기 때문에 빌딩을 스택에 넣고 누적합을 하는것이 아니라 누적합을 먼저 하고 스택에 넣어주어야 한다.
