SWEA) 중간값 찾기

문제 출처: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5QPsXKA2UDFAUq&categoryId=AV5QPsXKA2UDFAUq&categoryType=CODE&problemTitle=%EC%A4%91%EA%B0%84%EA%B0%92&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

사실 문제 자체는 그렇게 어렵지 않다. D1 문제이기도 하고 그냥 Arrays.sort(배열) 넣고 배열의 N/2번째 원소가 정답이 되는 식인데 다른 접근법을 배워 정리할 겸 포스팅을 한다.

코드는 다음과 같다

import java.util.Scanner;

public class 중간값찾기 {
	static int[] num; // 
	static int sum, ans;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
			int N = sc.nextInt();
			num = new int[N];
			
			for (int i = 0; i < N; i++) {
				num[sc.nextInt()]++;
			}
			
			sum = 0;
			ans = 0;
			
			for (int i = 0; i < N; i++) {
				sum += num[i];
				if(sum > N / 2) {
					ans = i;
					break;
				}
			}	
			System.out.println(ans);
		}
	
}

그냥 정렬해서 푸는 방법 입력받은 수 갯수만큼의 배열에 수를 입력받은뒤 정렬하여 2/n인덱스의 값이 정답이 된다.

-새로운 접근법-

이 접근법의 핵심은 우선 빈도수를 센다 그래서 input으로 1이 1번, 2가 5번, 3이 1번, 4가 1번, 5가 1번, 6이 1번 나왔다고 해보자. 중간값은 2가 될 것이다. 그럼 sum이라는 변수를 생성하여 sum+= 1번째 인덱스의 수를 더한다. 그러니까 sum 변수는 1이 몇번 나왔나가 된다. 그리고 이 sum을 2/n와 비교하여 크다면 정답을 i로 잡고 아니라면 2번 인덱스로 간다. 2번 인덱스의 값과 sum의 값을 더하면 6이 되겠다. sum은 1과 2가 나온 횟수를 센 변수이다. 그러니까 1과 2가 나온 횟수를 합하면 총 6번이라는 얘기다. 2/n와 비교한다. 2/n 보다 크다. 그러니까 중간값은 2가 된다.

이게 처음 들었을 떄는 뭔소린가 싶은데 계속 생각하다보면 이해가 된다. 그러니까 정렬해서 푸는 방법은 배열을 정렬한 뒤 0부터 2/n 까지 하나하나 세면서 가는거고 저거는 1 몇번 나왔고 2 몇번 나왔고 ... i번 몇번 나왔고 이걸 다 더해주다가 어? 2/n 넘었네? 그럼 i번째가 중간값이구나 하게 되는거다. 정렬된 배열을 나온 수대로 더하며 건너뛴다고 생각하면 되려나? 

이렇게 건너뛰면서 sum변수에 나온 횟수를 저장한다 그런 다음 2/n과 비교하는거

느낀 점: 접근법은 굉장히 다양하고 블로그 포스팅은 어려우며 아이패드 사고싶다.