최대 H 점수 2

문제 개요

N개의 수가 주어지고, 그 중 최대 L개의 서로 다른 원소 값을 1씩 증가시켜 H 점수를 최대화해야 한다.
H 점수란 특정 수 H 이상인 원소가 H개 이상 존재하는 경우를 만족하는 최대의 H를 의미한다.
예를 들어, 수열 [2, 3, 5]에서 H 점수는 2이다.

첫 번째 코드: 배열 복사 및 직접 변형

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int l = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++)
			a[i] = sc.nextInt();

		int ans = 0;
		for (int i = 1; i <= 100; i++) {
			int[] tmp = Arrays.copyOf(a, a.length);
			int cnt = 0;
			for (int j = 0; j < n; j++) {
				if (i - a[j] == 1 && cnt < l) {
					cnt++;
					tmp[j] = i;
				}
			}

			// H 탐색
			int hCnt = 0;
			for (int j = 0; j < n; j++) {
				if (i <= tmp[j])
					hCnt++;
			}
			if (i <= hCnt)
				ans = Math.max(ans, i);
		}

		System.out.println(ans);
		sc.close();
	}
}

• 모든 값을 복사한 뒤, 값이 i-1인 원소 중 최대 L개를 i로 올려 새로운 배열을 만든다.
• 이후 i 이상의 원소 개수를 세어 조건을 만족하면 정답 후보로 고려한다.
• 실제 수열 변형을 시뮬레이션하여 직관적이나, 매 반복마다 배열 복사가 필요하여 상대적으로 비효율적이다.

두 번째 코드: 조건 판단만으로 계산

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 1000;
    
    public static int n, l;
    public static int[] a = new int[MAX_N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력:
        n = sc.nextInt();
        l = sc.nextInt();
        
        for(int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        
        // 모든 답을 일일히 가정해 봅니다.
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            // 정답이 i일 때 가능한지 판단합니다.

            // i - 1인 값은 최대 l개까지 i로 올릴 수 있습니다.
            // cnt : i이상인 숫자의 개수(i - 1인 숫자는 l개까지 카운트)
            // cntl : 지금까지 1 증가시킨 숫자의 개수
            int cnt = 0;
            int cntl = 0;

            for(int j = 0; j < n; j++) {
                if(a[j] >= i)
                    cnt++;
                else if(a[j] == i - 1)
                    if(cntl < l) {
                        cntl++;
                        cnt++;
                    }
            }

            if(cnt >= i)
                ans = i;
        }

        System.out.print(ans);
    }
}

• 실제 수열을 바꾸지 않고, i 이상인 수의 개수를 직접 세는 방식이다.
• 값이 i-1인 경우만 최대 L개까지 조건에 따라 포함시켜 계산한다.
• 별도의 배열 복사 없이도 정확한 판단이 가능하므로 연산량이 적고 효율적이다.

결론: 두 번째 코드가 더 효과적이다

• 두 번째 코드는 배열 복사 없이 조건에 따라 직접 H 점수 계산이 가능하여 메모리와 시간 면에서 더 효율적이다.
• 첫 번째 코드는 문제 이해를 돕기에는 직관적이지만, 매 반복마다 배열을 복사하고 수정하는 방식이 불필요한 연산을 유발한다.