[자바] 백준 18310 - 안테나 (java)

 문제 : boj18310

---

 

필요 알고리즘 개념

• 그리디, 정렬
  
  • 그리디로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  처음엔 단순히 평균 구해서 평균과 가장 가까운 집을 선택하면 될 것이라 생각했다. 예제 입력 1도 그렇게 해보니 맞길래 그렇게 하니 당연히 틀렸다. 아래와 같은 경우, 평균으로 구하면 6.8 이므로 가장 가까운건 '6'이다. 그래서 '6'을 골라보면 차이의 합은 14이다. 하지만 실제론 9를 골라야 11로 최소이다. 따라서 평균은 아님을 금방 알 수 있었다. 

5
1 6 9 9 9

 

  그래서 규칙성을 찾아보려고 했는데, 첫번째 지점부터 하나씩 다 들려보면서 생각해봤다. 처음 '1'의 위치에 있을 때 차이의 합은 0 + 5 + 8 + 8 + 8 이다. '2'의 위치에 있다면 1 + 4 + 7 + 7 + 7 이다. '3'의 위치라면 2 + 3 + 6 + 6 + 6 이다. .... '7'의 위치에 있다면 6 + 1 + 2 + 2 + 2 이다. 즉, '1'부터 쭉 진행해보면 현재 위치보다 좌측 지점의 수만큼 +N이 되고, 현재 위치보다 우측 지점의 수만큼 -M이 되는 식이다. 이 때 어떠한 지점이라도 지정할 수 있다면 더 나은 지점을 찾을 순 있겠지만, 이 문제에서는 집이 위치한 곳에만 설치가 가능하다. 따라서 좌우 갯수가 맞춰지는 지점으로 고르면 된다.

 

  즉, 정렬 후 중간에 위치한 값을 출력해주면 된다. 5개라면 3번째 값, 6개라면 3번째 혹은 4번째 값을 출력하면 되는데, '여러 개의 값이 도출될 경우 가장 작은 값' 이라 했으므로 3번째 값을 출력해야 한다. 인덱스로 따지면 (N-1)/2 인덱스의 값을 출력해주면 된다.

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        System.out.println(arr[(n-1)/2]);
    }
}