[백준] 알고리즘 분류(그리디 알고리즘,JAVA)2212번, 센서

문제 링크

2212번: 센서

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. N개의 센서는 적어도 1개의 집중국과 통신을 진행해야합니다.

2. 집중국의 수신 길이는 0이상입니다.

3. 모든 좌표는 다를 필요가 없습니다.

4. K개의 집중국을 임의의 위치를 설치할 때 총 수신길이의 최소합을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 좌표를 오름차순 정렬 후 순서대로 차이를 구한 뒤 내림차순 정렬합니다.

 

3. (K-1)번째부터 차이의 합을 구해 결과로 출력합니다. 

※(K-1)번째부터 더하는 이유는 집중국을 설치해서 차이가 큰 값들을 제거하였기 때문입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 6

K : 2

[1, 6, 9, 3, 6, 7]

1

6

9

3

7

 

2. 좌표를 오름차순 정렬 후 순서대로 차이를 구한 뒤 내림차순 정렬합니다.

 

오름차순 정렬

1

3

6

7

9

 

차이 구하기.

2(1 ~ 3)

3(3 ~ 6)

1(6 ~ 7)

2(7 ~ 9)

 

내림차순 정렬

3(3 ~ 6)

2(1 ~ 3)

2(7 ~ 9)

1(6 ~ 7)

 

3. (K-1)번째부터 차이의 합을 구해 결과로 출력합니다. 

 

K-1 = 2 - 1 = 1

 

1번째부터 차이의 합 구하기

2(1 ~ 3) + 2(7 ~ 9) + 1(6 ~ 7) = 5 

 

5을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 좌표에 정보를 띄어쓰기 기준 나누었습니다.
• Collections.sort를 이용하여 좌표는 오름차순, 차이는 내림차순으로 정렬하였습니다.
• (K-1)번째 차이부터 합을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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


public class Main {
    static int N,K, answer = 0;
    static ArrayList<Integer> list = new ArrayList<>();	//좌표 저장 리스트
    static ArrayList<Integer> dif = new ArrayList<>();	//차이 저장 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //좌표값 저장
        for(int i=0;i<N;i++){
            int num = Integer.parseInt(st.nextToken());
            if(!list.contains(num))	//중복 좌표가 아닌 경우
                list.add(num);
        }
        Collections.sort(list);		//좌표 오름차순 정렬
        int curNum = list.get(0);
        //순서대로 좌표의 차이 구하기
        for(int i=1;i<list.size();i++){
            dif.add(list.get(i) - curNum);
            curNum = list.get(i);
        }
        //내림차순 정렬
        Collections.sort(dif,Collections.reverseOrder());
        //(K-1)번째부터 차이의 합 구하기
        for(int i=K-1;i<dif.size();i++)
            answer += dif.get(i);
        bw.write(answer + "");	//최소 수신 영역 거리 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}