[백준/JAVA] 2548번: 대표 자연수

🔺 문제

2548번: 대표 자연수

 

 

🔺 코드

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))));
 
        int N = Integer.parseInt((br.readLine()));
 
        int[] arr = new int[N];
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);   // 중앙값 탐색 위해 정렬
 
        // 배열의 길이가 짝수와 홀수인 경우에 따라 중앙값 인덱스가 다르므로 조정
        int mid = (arr.length % 2 == 0) ? arr[arr.length / 2 - 1] : arr[arr.length / 2];
        System.out.println(mid);
    }
}
 

 

 

 

🧩  해결 아이디어

• 정렬, 수학 (중앙값)

- 배열 값들 간 차이의 합을 최소로 하기 위해서는 중앙값을 출력하면 된다. (배열 길이 활용)

- 시간 복잡도 : O(N log N)

 

 

---

🔺 다른 풀이들

- 누적합 + 카운팅 정렬을 활용한 것도..! (시간 복잡도 : O(N + Q)

[자바] 백준 2548 - 대표 자연수 (java)

 

---

💬 느낀 점

이상하게 풀다가 왜 맞았지...?하고 보니까 중앙값을 구하는 것이 맞았던 것이다..ㅎ

 

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

 

(+ 12.21 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        System.out.println(N % 2 == 0 ? arr[N / 2 - 1] : arr[N / 2]);
    }
}
 

 

 

(+ 240219 3회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine() , " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        System.out.println(arr[(N-1) /2]);
    }
}
 

---

(참고)

백준 2548번 : 대표 자연수(Java)