[JAVA] BOJ 백준 2461번 - 대표 선수

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

분명 시간초과가 날 거 같은데 for문을 사용하는 거 밖에 생각이 안 나서, 투포인터 알고리즘이라는 것만 참고하고 풀었다.

입력받은 값을 한 줄에 정렬하고, 각각의 값이 몇 반인지를 알고 있기만 하면 투포인터를 사용할 수 있다.

 

아래는 반과 값을 담은 Tuple이라는 오브젝트를 List에 담아서 정렬하는 코드이다.

List<Tuple> list = new ArrayList<>();

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());

    for (int j = 0; j < M; j++) {
        list.add(new Tuple(i, Integer.parseInt(st.nextToken())));
    }
}

Collections.sort(list, new Comparator<Tuple>(){
    @Override
    public int compare (Tuple t1, Tuple t2) {
        return Integer.compare(t1.number, t2.number);
    }
});

 

이제 정렬된 값에 투포인터인 start 변수와 end 변수를 사용해 최소값, 최대값을 업데이트시켜 주면 된다.

end 변수는 항상 증가시켜 주면서, start 변수 값은 구간 안에 동일한 반이 존재하면 안 된다. 따라서 map에 투포인터 구간 안에 가진 반 개수를 카운팅 시킨 값을 확인해 주면 된다. 이해가 안 된다면, 아래 코드를 통해 이해해 보자.

int result = Integer.MAX_VALUE;
int start = 0;
int end = 0;

Map<Integer, Integer> map = new HashMap<>();

while (end < N*M) {
    Tuple e = list.get(end);

    map.put(e.idx, map.getOrDefault(e.idx, 0)+1);
    while (map.get(list.get(start).idx) > 1) {
        map.put(list.get(start).idx, map.get(list.get(start).idx)-1);

        if (map.get(list.get(start).idx) == 0) map.remove(list.get(start).idx);
    }

    if (map.size() == N) result = Math.min(result, e.number - list.get(start).number);

    end++;
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2461.java

import java.io.*;
import java.util.*;

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

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

            List<Tuple> list = new ArrayList<>();

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < M; j++) {
                    list.add(new Tuple(i, Integer.parseInt(st.nextToken())));
                }
            }

            Collections.sort(list, new Comparator<Tuple>(){
                @Override
                public int compare (Tuple t1, Tuple t2) {
                    return Integer.compare(t1.number, t2.number);
                }
            });

            int result = Integer.MAX_VALUE;
            int start = 0;
            int end = 0;

            Map<Integer, Integer> map = new HashMap<>();

            while (end < N*M) {
                Tuple e = list.get(end);

                map.put(e.idx, map.getOrDefault(e.idx, 0)+1);
                while (map.get(list.get(start).idx) > 1) {
                    map.put(list.get(start).idx, map.get(list.get(start).idx)-1);

                    if (map.get(list.get(start).idx) == 0) map.remove(list.get(start).idx);
                    start++;
                }

                if (map.size() == N) result = Math.min(result, e.number - list.get(start).number);

                end++;
            }

            bw.write(result+"");

            br.close();
            bw.flush();
            bw.close();
        }

        public static class Tuple {
            int idx;
            int number;

            public Tuple (int idx, int number) {
                this.idx = idx;
                this.number = number;
            }
        }
    }

---

4. 결과 및 회고

분명 맞는 코드인데 시간초과가 나길래 처음엔 List에 Object를 담아서 그런 줄 알았다. 근데 알고 보니 내가 ArrayList가 아닌 LinkedList로 처음에 선언해 줬던 것이 원인이었다. ㅠㅠㅠ

삽질 좀 했는데,, 다시 한번 기억하고 가자

검색 시 : ArrayList는 O(1)의 시간복잡도를, LinkedList는 O(n)의 시간복잡도를 가짐.

삽입, 삭제 시 : ArrayList는 O(n)의 시간복잡도를, LinkedList는 O(1)의 시간복잡도를 가짐.

 

이 이후로 제대로 선언해서 쓰자.