이분탐색 (1) 썸네일형 리스트형 Codility RectangleBuilderGreaterArea 이 문제는 N이 100,000개 까지 나올 수 있으므로 N^2 이상의 알고리즘으로 풀면 안됩니다. 다행히 펜스의 너비가 같더라도 가로와 세로길이가 다르면, 다른 종류의 펜스로 인정하니 만들수 있는 장대의 길이를 오름차순으로 정렬하여 어떤 index부터 X의 너비이상을 만족하는지 찾으면 N*log(N) 시간에 펜스의 종류를 확인할 수 있습니다. 1. 같은 길이의 장대가 2개 이상인 장대를 list에 할당한다. 2. 장대를 하나 정하고(A) 그 장대로 X너비 이상의 펜스를 만들 수 있는 최소길이의 장대(B)를 찾는다. (이분탐색) 3. 전체 장대길이 - 최소길이의 장대(B) index한 만큼 만들 수 있는 펜스의 종류이므로 이 값을 누적시킨다. 4. A 장대가 4개 이상이면, A장대만으로 펜스를 만들 수 있.. 이전 1 다음
