[백준] 2212 - 센서 (JAVA)

1. 소요시간 : 30분
2. 문제 사이트 : 백준
3. 문제 수준 : 골드5
4. 문제 유형 : 그리디 알고리즘, 정렬
5. 다른 사람의 풀이를 참고 했는가 ? : O
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2212
8. 푼 날짜 : 2023.03.15

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘, 정렬을 사용했다.

2. 풀이과정

1. n개의 센서들의 위치를 오름차순으로 정렬한다.
2. 이제 센서들의 각 위치의 차를 오름차 순으로 정렬한다.
3. n-k만큼 센서들의 위치의 차의 값을 더해준다.

3. 소스코드

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

public class Main {
	static HashSet<Integer> set=new HashSet<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		StringTokenizer st;

		
		int N=Integer.parseInt(br.readLine());
		int K=Integer.parseInt(br.readLine());
		
		st=new StringTokenizer(br.readLine());
		int arr[]=new int[N];
		for(int i=0;i<arr.length;i++){
			arr[i]=Integer.parseInt(st.nextToken());
		}
		Arrays.sort(arr);
		
		

		int diff[]=new int[arr.length-1];
		
		for(int i=0;i<diff.length;i++) {
			diff[i]=arr[i+1]-arr[i];
		}
		Arrays.sort(diff);
		int sum=0;
		for(int i=0;i<N-K;i++) {
			sum+=diff[i];
		}
		System.out.println(sum);






	}

}

4. 결과

5. 회고

센서들의 위치를 정렬하고, 센서들의 위치의 차를 정렬한다는 것 까지는 도달했는데 거기에서 어떤 기준으로 문제를 풀어야 할지 모르겠어서 아... 이렇게 푸는게 아니고 다른 방법으로 푸는건가? 라고 생각했었다... 결국 25분 째에 다른사람 풀이를 봤는데 보자마자 5분만에 그냥 풀어버렸다. 이거 그냥 내 생각으로만 해서 풀었으면 희열감 엄청났을 것 같은데 아쉽다!

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212