섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 9. 뮤직비디오(결정알고리즘)

문제

• 지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
• DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
• 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다.
• 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 
• 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
• 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
• 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
• 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

입력

• 첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.
• 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.
• 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

출력

• 첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

입출력 예제

---

풀이방식

이번 문제는 이분검색를(을) 사용하여 푸는 문제이다.

---

이분검색이란 정렬된 데이터를 가지고 자료를 반으로 나누어 검색하는 방식이다.

찾고 싶은 데이터(키 값), 시작 위치에 대한 값, 종료 위치에 대한 값, 중간 위치에 대한 값이 필요하다.

중간 위치의 값을 키 값과 비교하여 같다면 검색 종료, 작다면 왼쪽 데이터를 다시 검사하고 크다면 오른쪽 데이터를 다시 검사한다.

---

설계과정

1. DVD 1장에 들어갈 수 있는 용량의 중간값을 찾는다.

2. 찾은 중간값을 가지고 DVD가 몇 장 나오는지 구한다.

3. DVD의 장 수가 M보다 크다면 탐색 범위를 좁혀서 재탐색한다.

4. DVD의 장 수가 M보다 작다면 결과를 저장하고, 더 좋은 값을 찾기 위해 범위를 좁혀서 재탐색한다.

5. 탐색 범위가 끝날 때까지 반복한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. 결과를 출력할 solution 메소드와 DVD 장 수를 출력할 count 메소드를 선언한다.

 

3. solution 메소드부터 작성해보자.

 

4. 결과값을 저장할 result 변수를 선언하고, 0으로 초기화한다.

 

5. Stream을 이용해서 최대값을 구해서 lt에 넣고, 합산값을 구해서 rt에 넣는다.

• 스트림(Stream)은 자바8부터 추가된 것으로 max, sum, count 등과 같은 계산들을 편하게 할 수 있도록 해준다.
• 스트림은 리덕션 메소드들을 제공해주는데, 이는 최대,최소,합 등 큰 데이터에서 의미있는 값을 찾아내는 것을 말한다.
• max() :  스트림에서 제공되는 메소드로, 최대값을 리턴해준다.
• getAsInt() : max() 는 Optional 이라는 객체 타입으로 리턴하기에 우리가 원하는 정수값(int)을 얻기 위해 사용한다.
• sum() : 스트림에서 제공되는 메소드로, 합산값을 리턴해준다. 단 sum은 변수 설정에 사용한 기본형을 리턴해주므로 getAsInt()를 사용하지 않아도 된다.  (해당 문제에서는 int 로 rt를 선언했으므로 int 형으로 값을 리턴해준다.)
• lt : arr 배열에서 가장 큰 값으로, 예시에서는 ' 9 ' 를 의미한다.
• rt : arr 배열 원소들의 합으로, 예시에서는 ' 45 ' 를 의미한다.

6. lt 가 rt보다 작거나 같을 때 도는 while 문을 작성한다.

• 탐색하는 범위가 배열을 초과하면 멈추도록 한다.

7. lt와 rt를 더한 후에 2로 나눠서 중간값인 mid를 정한다.

• 이분검색을 사용하기 위한 중간값을 설정한다.

8. count() 메소드를 사용해서 M과 비교하며 탐색 범위를 줄인다.

 

9. 위 과정을 위해 count() 메소드를 작성해보자.

 

10. 각 변수를 선언하고 초기화한다.

• cnt : DVD 장 수를 의미하며 무조건 1장은 나와야하므로 1로 초기화한다.
• sum : DVD에 담는 용량의 크기이다.
• capacity : DVD 한 장의 용량이다.

11. sum에 x 를 더한 값이 capacity보다 크면 cnt를 추가하고 sum에 x를 넣는다.

• arr 배열과 x를 하나씩 매칭하며 DVD에 들어간 용량보다 큰지 작은지를 확인하는 작업이다.
• sum에 x를 더한 값이 DVD 1개에 들어가는 용량(capacity)보다 크다면 새 DVD를 추가해야 하므로 cnt++ 을 한다.
• 그 후에 sum에 x 를 더해서 새 DVD에 용량을 넣는다.
• sum에 x 를 더한 값이 capacity보다 작다면 더 들어갈 수 있다는 의미이므로 sum에 x 를 추가로 더해준다.

12. 작성한 count() 메소드를 사용한 결과가 M보다 작거나 같다면 결과값에 추가하고, rt 범위를 줄이고 재탐색한다.

• M보다 작은 값으로도 담을 수 있다는 것을 의미하므로 탐색 범위를 좁혀서 더 좋은 값을 찾아내기 위해서이다.
• 범위가 lt ~ rt 라고 생각하면 된다. lt가 3이고 rt가 6이라고 하면, 12번의 경우에는 더 적은 값으로도 DVD를 만들 수 있기에 rt를 줄여서 맨 끝 범위를 줄인다고 생각하면 된다.

13. M보다 큰 경우에는 lt 범위를 줄여서 재탐색한다.

 

14. 위 과정을 탐색 범위가 끝날때까지 반복한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.