[SWEA] 일곱 부하의 평균

문제 정보

• 문제 링크
• 난이도: D3

풀이

접근 방식

문제에서 제공하는 사라진 부하의 키를 구하기 위한 정보는 다음과 같다.

• 남아 있는 여섯 부하보다 키가 더 크다. (같거나 작지 않다.)
• 모든 부하의 키는 cm 단위로 양의 정수이다.
• 모든 부하의 키의 평균 역시 cm 단위로 양의 정수이다.

즉, 사라진 부하의 키는

1. 입력 받는 값들 중 최댓값보다도 더 크고
2. 입력 받는 값들에 더했을 때, 그 결과가 7의 배수가 되도록 해야 한다.

처음에는 while문을 이용해 입력값들 중 최댓값에서 1씩 증가시키며 총합이 7의 배수인지 확인하는 식으로 풀려고 했다.

그런데 생각해보니 그렇게 하지 않아도 될 것 같았다.

사라진 부하의 키를 output, 입력값들 중 최대값을 max, 입력값들의 총합을 sum이라고 해보자.

$\text{sum}+\text{output}$이 7의 배수가 되어야 한다. 그런데 $\text{output}>\text{max}$이므로, 7의 배수 중에서 $\text{sum}+\text{max}$를 넘는 가장 작은 배수를 구한 뒤, 거기서 $\text{sum}$을 빼면 된다.

결과적으로, $\text{output}=(\lfloor (\text{sum}+\text{max})÷7\rfloor +1)\times 7-\text{sum}$만 계산하면 사라진 부하의 키를 구할 수 있다.

코드

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int T = Integer.parseInt(sc.nextLine());
 
	for (int i = 0; i < T; i++) {
		int[] height = Arrays.stream(sc.nextLine().split(" "))
		.mapToInt(Integer::parseInt)
		.toArray();
 
		int max = Arrays.stream(height).max().getAsInt();
 
		int sum = Arrays.stream(height).sum();
 
		int output = ((sum + max) / 7 + 1) * 7 - sum;
 
		System.out.println(output);
	}
}

문제점

위 코드로 통과하긴 했다.

그런데 다른 사람의 코드를 보니, 처음에 생각했던 단순 반복문이 더 빠르고 사용하는 메모리가 적었다. 위 코드가 비효율적인 이유는 다음과 같았다.

1. 입력: int height[] = Arrays.stream(sc.nextLine().split(" ")).mapToInt...
   • split()은 문자열을 잘라 새 String 객체를 반환한다. (이 문제의 경우 6개)
   • 또 각각의 String 객체에 대해 Integer.parseInt()가 호출된다.
2. max와 sum구할 때
   • 단순하게 말해서, height[]를 한 번만 스캔하고 끝낼 수 있는데 위 코드의 경우 Arrays.stream()을 각각 호출하므로 height[]를 두 번 스캔한다.
3. 여러 차례의 임시 객체·배열
   • `int height[] = Arrays.stream(sc.nextLine().split(” “)).mapToInt().toArray();
     • sc.nextLine()
       • String객체 생성
     • split(" ")
       • 문자열을 잘라 새 String 객체 생성 후 이를 담은 새 String[] 배열 반환
     • Arrays.stream(String[])
       • 스트림 객체 생성
   • Arrays.stream(height).max().getAsInt()
     • 스트림 객체 생성
   • Arrays.stream(height).sum()
     • 스트림 객체 생성
   • ⇒ GC(Garbage Collection)의 횟수가 늘어나면서 실행 시간이 길어짐

수정 후 코드

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
 
	for (int i = 0; i < T; i++) {
		int[] height = new int[6];
		int max = 0;
		int sum = 0;
 
		for (int j = 0; j < 6; j++) {
			height[i] = sc.nextInt();
			sum += height[i];
			if (height[i] > max)
				max = height[i];
		}
 
		int output = ((sum + max) / 7 + 1) * 7 - sum;
 
		System.out.println(output);
	}
}