[BOJ] 1337 올바른 배열 - JAVA

1. 문제

1337번: 올바른 배열

올바른 배열이란 어떤 배열 속에 있는 원소 중 5개가 연속적인 것을 말한다. (연속적인 것이란 5개의 수를 정렬했을 때, 인접한 수의 차이가 1인 것을 말한다.)

예를 들어 배열 {6, 1, 9, 5, 7, 15, 8}은 올바른 배열이다. 왜냐하면 이 배열 속의 원소인 5, 6, 7, 8, 9가 연속이기 때문이다.

배열이 주어지면, 이 배열이 올바른 배열이 되게 하기 위해서 추가되어야 할 원소의 개수를 출력하는 프로그램을 작성하시오.

---

2. 풀이

처음 생각한 버전

1.  정렬된 배열을 하나씩 탐색한다.

2.  prev에 arr[start]를 저장하고 start+1부터 최대 네번 탐색하는데, 추가한 개수(cnt)와 현재 인덱스(i)의 합이 start+5보다 크면 안된다. 문제에서 원소 다섯개만 연속적인 수가 존재하면 된다고 했기 때문이다.

3.  만약 현재 인덱스가 N과 같다면 끝요소까지 온 것이므로 5에서 뺀 나머지를 cnt에 더하고 끝낸다.

4.  만약 prev +1 값이 arr[i]와 다르다면 prev+1과 arr[i]의 차이만큼을 cnt에 더한다.

5.  반복할 때마다 prev를 arr[i]로 교체한다.

6.  start부터 최대 네 번 탐색이 끝났다면 min을 cnt와 비교해 더 작은 값으로 바꾼다.

7.  모든 배열을 탐색한 후 min을 출력한다.

import java.io.*;
import java.util.*;
 
public class BOJ_1337_올바른배열 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] arr = new int[N];
      for(int i=0;i<N;i++) arr[i] = Integer.parseInt(in.readLine());
      Arrays.sort(arr);
 
      int prev, cnt;
      int min = 4;
      for(int start = 0;start<N;start++){
         prev = arr[start];
         cnt = 0;//추가해야하는 개수
         //반복 : 추가한 개수(cnt)+i까지 합해서 start+5넘으면 안됨
         for(int i = start+1; i+cnt<start+5;i++){
            if(i == N){
               //끝 요소까지 왔으니 그 나머지 싹 더하고 끝
               cnt+= 5-(N-start);
               break;
            }
            else if(prev+1 != arr[i]){
               //다르다면 그 차이만큼 더하기
               cnt += arr[i]-prev-1;
            }
            //교체
            prev = arr[i];
         }
         min = Math.min(min,cnt);
      }
 
      System.out.println(min);
   }
}

 

간단해진 버전

1.  list에 담고 정렬한다.

2.  list 요소를 하나씩 탐색한다. item+1부터 item+4까지 binarySearch 메서드를 이용해서 list에 그 요소가 없다면 tmp++한다. tmp는 현재 탐색시도에서 추가해야하는 개수다.

3.  answer와 tmp중에 더 작은 걸 저장해서 마지막에 answer을 출력한다.

import java.io.*;
import java.util.*;
 
public class BOJ_1337_올바른배열2 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      ArrayList<Integer> list = new ArrayList<>();
      for(int i=0;i<N;i++) list.add(Integer.parseInt(in.readLine()));
      Collections.sort(list);
 
      int answer = 4;
      int tmp;
      for(int item:list){
         tmp = 0;
         for(int j=item+1;j<item+5;j++){
            if(Collections.binarySearch(list,j) < 0) tmp++;
         }
         answer = Math.min(answer, tmp);
      }
 
      System.out.println(answer);
   }
}

---

3. 결과

다른 사람들이랑 차이가 너무 많이 나서 이 문제를 맞고나서도 세 번 더 풀었는데, 그냥 백준 사이트 내의 java 11과 java 8 속도가 차이나는 것 같다.

끝 코드가 서로 똑같은데 속도가 1/3정도 줄어들었다..!