옥상 정원 꾸미기 썸네일형 리스트형 [백준] 6198 옥상 정원 꾸미기 / 자바(Java) 문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 해설 각 빌딩별 오른쪽에 있는 자신보다 크거나 같은 빌딩과의 사이에 있는 빌딩의 수들의 합을 구하는 문제입니다. 각 빌딩별로 오른쪽을 탐색하면 확인하는 과정을 거친다면 O(n^2)의 시간복잡도를 가져 시간초과가 날 수 있습니다. 발상의 전환으로 각 빌딩별 자신을 볼 수 있는 빌딩의 수를 구한다면? 각 빌딩기준 왼쪽에 자신보다 큰 빌딩의 수를 구한다면 O(n)으로 해결이 가능하다 생각되.. 더보기 이전 1 다음
