[백준] 18310 - 안테나 (JAVA)

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

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

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

2. 사고과정

우선 가장 먼저 든 생각은 가운데 값을 찾는 것이었다. 그런데 다시 생각해보니 반례가 있을 것 같았다. 그래서 우선 보류해 두고 이분탐색을 고려했다.

이분탐색을 고려했었지만 이분탐색으로는 풀기 어려움을 깨달았다. 여기서 문제의 난이도가 실버 3임을 인지하고 쉽게 생각하기로 마음먹었다. 그래서 처음의 생각인 중앙값을 찾는 것의 반례가 있을까 직접 극단적인 좌표를 생각해보고 그려봄으로써 중앙값을 찾는 것에서 반례가 없음을 알았다.

그래서 최종적으로 solution . 중앙값을 찾는다.

3. 풀이과정

1. 자료들을 정렬한다.
2. 자료의 개수가 홀수개라면 arr[arr.length/2] 를 출력
   (자료가 3개라면 , arr[3/2] = arr[1] 으로 중앙값이다 )
3. 자료의 개수가 짝수개라면 arr[arr.length/2-1]를 출력
   (자료가 4개라면, arr[4/2-1] = arr[1] 으로 중앙값이다. -1 을 해준 이유는
   단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.
   라는 조건 때문이다. )

시간 복잡도는 자료를 정렬하는데에 O(nlogn) 이고, n은 200,000 이다. 제한시간이 1초이므로 시간은 충분하다.

4. 소스코드

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

public class Main {

	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());
		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);
		
		if(arr.length%2!=0) {
			System.out.println(arr[arr.length/2]);
		}
		else {
			System.out.println(arr[arr.length/2-1]);
		}
		
		
		
	}
}

5. 결과

6. 회고

테스트케이스에만 있는 것으로 판별하려 하지 말자. 직접 테스트케이스를 만들어 봄으로써 반례를 생각하고 사고하는 힘을 키우자.

(~ 한계. ) 결국 문제의 난이도를 보고 난이도에 따라서 solution을 생각한 것.. 코테에서 이건 실버 문제에요! 이건 골드 문제에요 ! 알려주는 것도 아닌데 좀 안일한 것 같다.

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