[백준, Java] 23758번, 중앙값 제거, (그리드)

문제 링크

23758번: 중앙값 제거

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. 문제에서 설명하는 연산을 반복해서 0을 만들어야 합니다.

2. 연산의 대상은 오름차순에서 중간값입니다.

3. 0을 만드는 연산 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 2진수의 개수를 통해서 연산 횟수를 계산합니다.

 

3. 연산 횟수를 결과로 출력합니다.

 

 

연산 횟수 계산(2진수 활용)

 

해당 연산은 중간값을 기준으로 진행하기 때문에 중간값 이후에 값들은 절대 연산 대상이 되지 않습니다.

 

그래서, 처음에 숫자들을 오름차순으로 정렬한 뒤에 중간값 이하의 값들만 연산을 진행하면 됩니다.

 

또한, 중간값을 0으로 만드려면 중간값 이하의 값들이 모두 1이 되어야 합니다.

 

예를 들어,

 

5

6

8

9

연산을 진행되는 과정을 살펴보면

 

5	6	8	9
3	5	8	9
2	3	8	9
1	2	8	9
1	1	8	9
0	1	8	9

 

중간값 이후의 값 { 8, 9 } 는 연산의 대상이 되지 않는 것을 확인하실 수 있습니다.

 

이후 연산을 진행할 때 0이 나오는 순간은 중간값 이하의 값들이 모두 1일 때입니다.

 

즉, 오름차순으로 정렬한 뒤 중간값 이전의 값들의 2진수의 계수가 해당 값을 1로 만드는 연산 횟수입니다.

 

그래서 2진수의 계수를 모두 구해서 나누어졌다고 가정하면 해당 값들은 중간값 이하의 값들이 모두 1이 되는 것입니다.

 

위 예시를 2진수의 계수로 표현하면

 

5	6	8	9
2	2	연산 대상 X	연산 대상 X

 

5를 1로 만들기 위한 연산 횟수 : 2번

 

6을 1로 만들기 위한 연산 횟수 : 2번

 

이후, 1을 0으로 만들기 위한 연산 1번 진행

 

2 + 2 + 1 : 5번의 연산 진행

 

 

정리해서 단계적으로 표현하면

 

1. a[]에 대해서 오름차순으로 정렬한다.

 

2. 중간값 포함 이전에 값들에 대해서 각 2진수의 계수를 구한다.(1을 만들기 위함)

 

3. 모든 2진수 계수의 합 + 1(1 → 0으로 만드는 연산) = 연산 횟수

 

※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 3

 

2021

1127

1400

 

2. 2진수의 개수를 통해서 연산 횟수를 계산합니다.

 

오름차순 정렬

 

1127

1400

2021

 

 

 

중간값 포함 이전에 값들에 대해서 각 2진수의 계수를 구한다.(1을 만들기 위함)

 

1127	1400	2021
10	10	연산 대상 X

 

모든 2진수 계수의 합 + 1(1 → 0으로 만드는 연산) = 연산 횟수

 

10 + 10 + 1 = 21

 

 

 

3. 연산 횟수를 결과로 출력합니다.

 

 

연산 횟수 : 21을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 N개의 자연수 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort을 이용해서 오름차순 정렬을 진행합니다.
• calBinaryCount을 이용해서 중간값 이하의 2진수 계수의 합을 계산합니다.
• 연산 횟수(2진수 계수의 합 + 1)를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• calBinaryCount는 ÷2을 통해서 2진수의 계수를 구합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] a = new int[N+1];
        //입력되는 N개의 자연수 저장
        for(int i=1;i<=N;i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        //오름차순 정렬
        Arrays.sort(a);
        //중간값 index
        int mid = (N+1)/2;
        int result = 0;
        //중간값 이하 2진수의 계수 더하기
        for(int i=1;i<=mid;i++){
            result += calBinaryCount(a[i]);
        }
        //모든 2진수의 계수 합 + 1 : 연산 횟수 BufferedWriter 저장
        bw.write(String.valueOf(result+1));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //2진수의 계수 구하는 함수
    static int calBinaryCount(int val){
        int cnt = 0;
        while(val > 1){
            cnt++;
            val /= 2;
        }
        return cnt;
    }
}