본문 바로가기
알고리즘 문제/Codeground

[Codeground][74] 버스타기

by 햄과함께 2018. 11. 16.
320x100

문제 : https://www.codeground.org/practice/practiceProblemViewNew




5 3 1 4 3 7 9

을 예로 들어보자.


일단 오름차순으로 정렬한다.

1 3 4 7 9

첫번째 수 1과 같은 버스를 탈 수 없는 바둑 기사같이 탈 수 있는 바둑기사를 나눠보면 다음과 같다.

1 3 4 7 9

차이가 작은 수들이 같은 버스를 탈 수 없다.


따라서 1과 같은 버스를 탈 수 없는 바둑 기사들은 각자 누구와도 같은 버스를 탈 수 없다. (정렬했기 때문에 빨간색 범위 내의 능력차이는 항상 3(4-1)보다 작다.)

즉, 1 3 4는 각자 다른 버스를 타야하고 따라서 적어도 3개의 버스가 필요하다. 나머지 7과 9는 1번이 탄 버스에 같이 타면 되므로 같이 탈 수 없는 바둑 기사의 수만 고려하면 된다.

각 바둑 기사들과 같이 탈 수 없는 바둑 기사들의 수를 구한 뒤 이 중 가장 큰 값이 정답이 된다.


투포인트를 사용하면 정렬하는데 NlogN이 들고 배열을 2N만큼 탐색하므로 시간복잡도는 O(NlogN).




소스코드 : https://gist.github.com/fpdjsns/fd7ad20bc1fb0b6d05568b4c5997d9c7

320x100

'알고리즘 문제 > Codeground' 카테고리의 다른 글

[codeground] 71. 정수 정렬하기  (0) 2019.09.14
[codeground] 31. 프리랜서  (0) 2019.09.13
[codeground] 52. 최대 직사각형  (0) 2019.09.12
[codeground] 8. 블럭 없애기  (0) 2019.09.02
[codeground] 36. 재활용  (0) 2019.06.12

댓글