1. 문제
올바른 배열이란 어떤 배열 속에 있는 원소 중 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정도 줄어들었다..!
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 15961 회전초밥 - JAVA (0) | 2023.03.30 |
---|---|
[BOJ] 2230 수 고르기 - JAVA (0) | 2023.03.29 |
[BOJ] 7795 먹을 것인가 먹힐 것인가 - JAVA (0) | 2023.03.27 |
[BOJ] 17609 회문 - JAVA (0) | 2023.03.26 |
[BOJ] 2473 세 용액 - JAVA (0) | 2023.03.25 |
댓글