서로 볼 수 있는 탑 쌍 개수

자바스크립트 코딩테스트 문제로 visible-stack 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today medium visible-stack 함수명: countVisibleTowerPairs 제한 시간: 300ms

일렬로 서 있는 탑들 중 서로 시야가 막히지 않는 탑 쌍이 몇 개인지 구하세요.

문제 설명

정수 배열 heights가 주어집니다. heights[i]는 왼쪽에서 i번째 탑의 높이입니다.

두 탑 i, j가 i < j일 때, 두 탑 사이에 있는 모든 탑의 높이가 Math.min(heights[i], heights[j])보다 크지 않다면 두 탑은 서로 볼 수 있습니다.

서로 볼 수 있는 탑 쌍의 총개수를 반환하는 countVisibleTowerPairs 함수를 작성하세요.

제한사항

1 <= heights.length <= 200,000
1 <= heights[i] <= 1,000,000,000
같은 높이의 탑이 여러 번 등장할 수 있습니다.
두 탑 사이에 두 탑 중 낮은 탑보다 높은 탑이 있으면 서로 볼 수 없습니다.
반환값은 JavaScript의 안전한 정수 범위 안에 들어온다고 가정합니다.

예시

입력: [10, 3, 7, 4, 12, 2] -> 출력: 8
입력: [2, 2, 2] -> 출력: 3
입력: [5, 1, 2, 3, 4] -> 출력: 7
입력: [4, 4, 2, 4] -> 출력: 5
입력: [6] -> 출력: 0

힌트

현재 탑보다 낮은 탑은 현재 탑을 만나면 더 이상 오른쪽의 다른 탑을 가려 주지 못합니다.
같은 높이가 연속해서 스택에 쌓이면 하나씩 저장하지 말고 개수로 압축해 보세요.
현재 탑과 같은 높이 묶음을 처리한 뒤, 왼쪽에 더 높은 탑이 하나 남아 있는지도 확인해야 합니다.

해설

모든 탑 쌍을 직접 확인하면 O(n^2)이 되어 입력이 커질 때 통과하기 어렵습니다.

핵심은 왼쪽에서 오른쪽으로 탑을 보면서, 아직 오른쪽 탑과 볼 가능성이 있는 탑만 스택에 남기는 것입니다. 스택은 높이가 내림차순이 되도록 유지하고, 같은 높이는 { height, count } 형태로 묶어 저장합니다.

현재 높이를 height라고 하겠습니다.

스택 맨 위가 height보다 낮으면, 그 묶음의 탑들은 현재 탑과 모두 볼 수 있습니다. 따라서 count만큼 정답에 더하고 스택에서 제거합니다.
스택 맨 위가 height와 같으면, 같은 높이 묶음의 탑들은 현재 탑과 모두 볼 수 있으므로 그 count를 더합니다. 그리고 현재 탑을 같은 묶음에 합칩니다.
같은 높이 묶음을 합친 뒤에도 스택 왼쪽에 더 높은 탑이 남아 있다면, 그 더 높은 탑 중 가장 가까운 하나와 현재 탑도 서로 볼 수 있으므로 1을 더합니다.
스택 맨 위가 height보다 높기만 하다면, 현재 탑은 그 가장 가까운 높은 탑 하나와만 볼 수 있으므로 1을 더합니다.

예를 들어 [4, 4, 2, 4]를 보면, 양끝의 4 두 개는 가운데에 높이 4보다 큰 탑이 없기 때문에 서로 볼 수 있습니다. 또한 같은 높이 4가 여러 개 있으므로 같은 높이 묶음 개수를 더해야 (0, 1), (0, 3), (1, 3) 같은 쌍을 빠뜨리지 않습니다.

각 탑은 스택에 한 번 들어가고 최대 한 번 제거됩니다. 따라서 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과