SWEA [D1] 중간값 찾기 - 2063 JAVA

링크텍스트

설명

풀이 흐름 설명

우선 입력으로 주어지는 수의 개수 T는 항상 홀수이고 값은 양수라고 가정할 수 있었다. 그래서 배열을 만들 때 크기를 T + 1로 잡고 인덱스 1번부터 값을 저장하였다.

값을 모두 입력받은 뒤에는 Arrays.sort()를 사용해 배열을 오름차순으로 정렬하였다. 중앙값은 정렬된 상태에서 정확히 가운데에 있는 값이므로 T / 2 + 1번째 값을 출력하면 된다.

여기서 +1을 한 이유는 배열을 0번 인덱스부터 사용하지 않고 1번 인덱스부터 사용했기 때문이다. 예를 들어 T = 9라면 중앙 위치는 5번째 값이고 식으로는 9 / 2 + 1 = 5가 된다. 따라서 정렬 후 arr[T / 2 + 1]을 출력하면 중앙값을 구할 수 있었다.

다만 이 방식은 입력값이 양수라는 조건이 있기 때문에 가능했다. 배열의 0번 인덱스에는 기본값 0이 들어가는데 입력값들이 모두 양수라면 정렬 후에도 0이 맨 앞에 남아서 실제 값들의 순서를 방해하지 않는다. 그래서 인덱스 1부터 값을 저장하는 방식으로도 중앙값을 올바르게 구할 수 있었다.
시간복잡도: O(T), 공간복잡도: O(1)

회독

• [ x ] 1회
• 2회
• 3회

코드

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.Arrays;

class Solution
{	
	public static void main(String args[]) throws Exception
	{
		
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		int [] arr = new int[T+1];
 		for(int test_case = 1; test_case <= T; test_case++)
		{
			arr[test_case] = sc.nextInt();
		}
        
        Arrays.sort(arr);
        
        System.out.println(arr[T/2+1]);
	}
}