[코드트리/NOVICE MID] 숫자 2배 후 하나 제거하기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
 
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        int minDiff = Integer.MAX_VALUE;
        for(int i = 0 ; i < N ; i++) {
            arr[i] *= 2;    // 하나의 숫자 선택해 2배
 
            for(int j = 0 ; j < N ; j++) {
                int[] remainder = new int[N - 1];   // 하나의 숫자 선택해 제거한 배열
                int cnt = 0;
                for(int k = 0 ; k < N ; k++) {
                    if(k != j) {
                        remainder[cnt++] = arr[k];
                    }
                }
 
                int sumDiff = 0;    // 인접한 숫자간의 차의 합
                for(int k = 0 ; k < N - 2 ; k++) {
                    sumDiff += Math.abs(remainder[k + 1] - remainder[k]);
                }
 
                minDiff = Math.min(minDiff, sumDiff);    // 최솟값 갱신
            }
 
            arr[i] /= 2;    // 2배했던 숫자 원상복구
        }
 
        System.out.println(minDiff);
    }
}

 

 

 

🧩  해결 아이디어

• 중첩 완전탐색

- 배열에서 한 개의 숫자를 선택해 값을 2배로 올린다.

 

- 하나의 숫자를 선택해 제거한 N-1크기의 배열을 만들고, 값을 넣는다.

- N-1 크기의 배열에서 인접한 숫자간의 차의 합을 구하고, 현재 최솟값과 비교해 갱신한다.

 

- 2배했던 값을 원상복구한다.

 

 

 

 

---

💬 느낀 점

중첩 완전탐색은 집중해서....

 

1회독	2회독	3회독	4회독	5회독
V