[BOJ] 백준 2548 - 대표 자연수 풀이

1. 문제

https://www.acmicpc.net/problem/2548

2548번: 대표 자연수

 

2. 풀이

실버 3에 해당하는 브루트포스 문제이다. 엄청 쉬운 문제였음에도 도대체 왜 삽질을 했는지..... 아직도 한참 부족하다는 것을 또또또 느낀 문제가 아닌가 싶다.

입력으로 주어지는 자연수의 개수 N과 수들을 각각 변수와 리스트에 할당한다.
그 후 차이 값에 해당하는 numList의 인덱스인 i (=대표 자연수 후보)를 저장할 idxList를 만들고, 수들을 저장할 리스트(앞으로 numList라고 명명하겠다.)를 Two-Point로 돌면서 차이 값을 계산한다.

계산한 차이 값이 old 값보다 클 경우 이는 지금까지 들어온 수 보다 가장 작은 값이므로, idxList를 초기화 한 후 i값에 맞는 numList의 값을 idxList에 넣으며, old 값을 방금 계산한 차이 값으로 갱신한다.

이때 왜 idxList를 초기화하는가 의문이 들 수 있다.
결론부터 말하면 차이 값의 최소값을 갖는 인덱스가 바뀐다면 전에 저장해놨던 것은 더 이상 최소 값이 아니기 때문이다.
최소 값이 바뀐다면 그 전에 최소 값이라고 생각하여 List에 넣어놨던 값은 의미가 없어지기에 초기화를 한 후 새로 계산된 최소 값에 해당하는 값을 넣어줘야 하기 때문이다.

3. 소스 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<Integer> numList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            numList.add(Integer.parseInt(st.nextToken()));
        }

        List<Integer> idxList = new ArrayList<>();
        int old = Integer.MAX_VALUE;
        for (int i = 0; i < numList.size(); i++) {
            int first = numList.get(i);
            int sum = 0;

            for (int j = 0; j < numList.size(); j++) {
                int second = numList.get(j);
                sum += Math.abs(first - second);
            }

            if (old > sum) {
                idxList.clear();
                idxList.add(numList.get(i));
                old = sum;
            } else if (old == sum) {
                idxList.add(numList.get(i));
            }
        }

        Collections.sort(idxList);
        bw.write(Integer.toString(idxList.get(0)));
        bw.flush();
        bw.close();
        br.close();
    }
}