백준 센서 (복습)

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

2212번: 센서

이틀동안 고민했던 문제고 반드시 오답노트를 해야할것같아서 남깁니다. 자바로 풀었습니다.

일단정답입니다. 풀이는 아래 있습니다.

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		//세로 두줄 카로로 n개으로 이루어진 표가 있다.
		//첫째줄의 각칸에는 1,2,...n 이 차례 대로 들어 있고 
		//둘째 칸에는 1아ㅣ상 n이하 정수가 들어 있다.
		//첫쨰줄에서 숫자를 적절히 뽑으면 , 그 뽑힌 정수들이 이루는 집하과 뽑힌 정수들의 바로 밑의 둘쨰 줄에 들어 있는 정수들이 이루는 
		//집합이 일치한다.
		//이러한 조건을 만족시키도록 정수들을 뽑되 최대로 많이 뽑는 방법을 찾아라
		Scanner scan=new Scanner(System.in);
		//N개 센서를 설치하였다.
		int n=scan.nextInt();
		int k=scan.nextInt();
		ArrayList<Integer> lists=new ArrayList<>();
		HashMap<Integer,Integer>maps=new HashMap<>();
		ArrayList<Integer>gap=new ArrayList<>();
		if(k>=n) {
			System.out.println(0);
		}else {
			for(int i=0;i<n;i++)
			{
				int tmp = scan.nextInt();
				lists.add(tmp);
			}
			
			Collections.sort(lists);
			//System.out.println(lists);
			for(int i=0;i<n-1;i++) {
				gap.add(lists.get(i+1)-lists.get(i));
			}
			Collections.sort(gap);
			Collections.reverse(gap);
			//System.out.println(gap);
			int gapsum=0;
			for(int i=0;i<k-1;i++) {
				gapsum+=gap.get(i);
			}
			//System.out.println(gapsum);
			
			int result=lists.get(lists.size()-1)-lists.get(0)-gapsum;
			System.out.println(result);
		}
		
		
	}
}

자 하나 하나 설명할게요

먼저  입력값들 전부 받아줍니다.

int n=scan.nextInt();
int k=scan.nextInt();

for(int i=0;i<n;i++)
{
	int tmp = scan.nextInt();
	lists.add(tmp);
 }

그리고 오름차순으로 리스트들을 정렬해줍니다.

ex)1 6 9 3 6 7 ->   1 3 6 6 7 9

Collections.sort(lists);

정렬된 상태에서 이 센서들간의 차를 구합니다. 

for(int i=0;i<n-1;i++) {
	gap.add(lists.get(i+1)-lists.get(i));
}

당연히 아시겠지만 센서들의 값이 클수록 없애는게 좋겟죠 즉 센터타워의 위치입니다.

여기서 간과한게 센터 타워를 지으려고 했는데 지으면 안되고 거리만 확인하면됩니다.

즉 전체길이- 가장긴 거리 겠죠

이떄 센서 하나를 기준으로 그다음부터 하나씩 제거가 되겠죠 먼저 거리차 가장 큰순으로 내림차순으로 정렬 합니다.

ex) gap 거리차 3 ,2, 2, 1, 0 

Collections.sort(gap);
Collections.reverse(gap);
int gapsum=0;
for(int i=0;i<k-1;i++) {
	gapsum+=gap.get(i);
}

즉 k=2인경우 6은 중복이라 그림에서 제외 

당연히 빨간 부분인 3 크기가 가장 먼저 없어지겠죠 만약에 k가 1이면 6만 제거되니까 사실상 거라차의 값을 뺼필요가 없겟죠 

k=1인경우 6은 중복이라 그림에서 제외 

그렇다면 지금 가장 큰값인 3을 전체길에서 뺴면되겟죠 당연히 list의 가장 뒤에값과 처음값의 차가 전체길이가 되고 

가장 큰값의 누적값을 뺴면 최소거리가 나오겠죠 

int result=lists.get(lists.size()-1)-lists.get(0)-gapsum;