글 읽기 - 시간 초과가 발생하는데 어떻게 해결해야 좋을까요?

sth4881 2년 전 0

각각의 집에 대해서 다른 모든 집들과의 거리의 합을 비교해서

거리의 합이 최소값인 집을 구하도록 짰는데 시간 초과가 나네요...

어떤 방식으로 접근하면 좋을지 여쭤보고싶습니다....

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

public class Main{
    public static class House implements Comparable<House> {
        int num; // 집의 번호
        int sum; // 다른 집들 간의 거리의 합

        public House(int num, int sum) {
            this.num = num;
            this.sum = sum;
        }

        @Override
        public int compareTo(House o) {
            if(this.sum != o.sum)
                return this.sum - o.sum;
            else return this.num - o.num;
        }
    }
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int n = Integer.parseInt(br.readLine());
            ArrayList<Integer> list = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                int input = Integer.parseInt(st.nextToken());
                list.add(input);
            }

            PriorityQueue<House> pq = new PriorityQueue<>();

            // 각각의 집에 대해서 다른 모든 집들과의 거리의 합을 비교해서 최소값 구하기
            // 시간복잡도가 O(N^2)이기 때문에 시간초과 발생
            for (int target : list) {
                int sum = 0;
                for (int item : list)
                    sum += Math.abs(target - item);
                pq.offer(new House(target, sum));
            }

            bw.write(pq.poll().num + "\n");
            bw.close();
        } catch (FileNotFoundException e) {
            e.getStackTrace();
        } catch (IOException e) {
            e.getStackTrace();
        }
    }
}

gang7994 2년 전 0

저도 처음에는 그렇게 생각했는데 이 방법 말고 안테나는 집이 위치한 곳에만 설치할 수 있다고 하니까

집의 위치들을 정렬해서 가운데에 위치한 집에 안테나를 설치하는 게 최소 값이 아닐까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과가 발생하는데 어떻게 해결해야 좋을까요?

sth4881 2년 전 0

gang7994 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말