1. 문제 파악: 점수 조작과 평균 구하기

문제 링크: 백준 1546번 - 평균
작성 코드: 전체 소스 코드 보기 (GitHub)

📌 요구사항 요약

자기 점수 중 최댓값($M$)을 골라, 모든 점수를 아래 수식으로 고친 후 새로운 평균을 구해야 합니다.

단순히 구현만 한다면 쉽지만, 연산의 효율성(시간 복잡도)과 부동 소수점 오차를 고려해야 하는 문제입니다.

🔑 Key Constraints

• 시간 제한: 2초
• 입력 크기($N$): $N \le 1,000$
• 특이 사항: 오차 범위 $10^{-2}$ 이하 허용 (double형 연산 필요)

🔗 Reference

• 문제 바로가기 (BOJ 1546)
• 내 풀이 코드 (GitHub)

---

2. 기존 풀이: List와 Sort를 활용한 구현

처음에는 문제의 흐름을 그대로 코드로 옮기는 절차 지향적인 방식으로 접근했다.
"데이터를 다 받아서 저장하고 -> 정렬해서 1등 찾고 -> 계산하자"는 생각이었다.

💻 작성 코드 (Before)

        // 1. 입력을 받아 String 배열로 저장 (split 사용)
        String[] strNumbers = numbers.split(" ");

        // 2. 리스트에 담기
        List<Integer> intNumbers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            intNumbers.add(Integer.parseInt(strNumbers[i]));
        }

        // 3. 정렬을 통해 최댓값 찾기 (비효율 발생 지점)
        Collections.sort(intNumbers, Collections.reverseOrder());
        int max = intNumbers.get(0);

        // 4. 별도의 리스트에 변환된 점수 저장
        List<Double> adjustedNumbers = new ArrayList<>();
        for (int i =0; i <n; i++) {
            adjustedNumbers.add(intNumbers.get(i) / (double) max + 100);
        }

        // 5. 평균 구하기
        double sum = 0;
        for (int i = 0; i < n; i++) {
            sum += adjustedNumbers.get(i);
        }
        double result = sum / adjustedNumbers.size();

        // 6. 정답 출력
        System.out.println(result);

🤔 아쉬웠던 점

1. 불필요한 메모리 사용: split으로 배열을 만들고, ArrayList를 두 개나 생성해서 데이터를 계속 저장했다.
2. 과도한 연산($O(N logN)$): 단순히 최댓값 하나를 찾기 위해 전체 데이터를 정렬(Collections.sort)했다. 굳이 2등, 3등의 순서까지 맞출 필요가 없었다.
3. 반복문의 중복: 입력, 변환, 합산 과정에서 for문을 3번이나 사용했다.

---

3. 최적화: 스트림 방식과 수학적 접근($O(N)$)

피드백을 통해 데이터를 저장하지 않고 들어오는 즉시 처리하는 방식으로 코드를 개선했다.

💻 수정 코드 (After)

// ... (import 생략)
StringTokenizer st = new StringTokenizer(br.readLine()); // 메모리 효율적인 파싱

double max = 0;
double sum = 0;

for (int i = 0; i < n; i++) {
	double num = Double.parseDouble(st.nextToken());
    
    // 1. 입력과 동시에 합계 누적 (저장 X)
    sum += num;
    
    // 2. 정렬 대신 비교(Scan)로 최댓값 찾기 (O(N))
    if (max < num) {
    	max = num;
    }
}

// 3. 수학적 분배 법칙 적용: (종합 * 100) / 최댓값 / 개수
double result = (sum / max * 100) / n;
System.out.println(result);

---

4. 핵심 배움

1) [설계] 로직 작성 전, 수식부터 최적화하기

무작정 for문 안에 연산 로직을 넣기 전에, 수학적으로 식을 정리하면 연산 횟수를 획기적으로 줄일 수 있다.

• Before: 각 점수마다 (점수 / max * 100)을 계산해서 더함. (연산 횟수 N번)
• After: 수식을 정리해보니 (총합 * 100) / max / N과 결과가 같음. (연산 횟수 1번)

• Insight: 평균, 합계, 비율을 구하는 문제에서는 개별 데이터를 가공하는것 보다, 최종 합계를 구한 뒤 마지막에 한 번만 연산하는 것이 효율적이며 오차도 줄일 수 있다.

2) [알고리즘] 정렬 대신 탐색 선택하기 ($O(N log N)$ vs $O(N)$)

최대값을 구하라는 요구사항을 보고 무의식적으로 정렬(Sort)을 떠올렸으나, 이는 불필요하게 많은 연산을 수행하게 한다.

• 정렬(Sort): 1등부터 꼴등까지 모든 순서를 맞춘다. $O(N log N)$
• 탐색(Scan): 서바이벌 게임처럼 비교하며 1등(Max)만 남긴다. $O(N)$

• Insight: 문제에서 2등, 3등의 정보가 필요 없다면 정렬은 비효율적이다. 내가 필요한 정보(Max)만 얻기 위한 최소한의 연산(Scan)을 선택해야 한다. 데이터가 커질수록 이 차이는 수십 배 이상 벌어진다.

3) [구현] 데이터 스트리밍과 루프 병합

데이터를 어떻게 다룰 것인가에 대한 기준을 세워 메모리와 반복문을 최적화할 수 있다.

• 데이터 보존 여부 (List vs Streaming):
  • 변환된 개별 점수가 나중에 다시 필요한가 $\to$ Yes라면 List 저장
  • 최종 결과값 하나만 필요한가? $\to$ Yes라면 변수에 누적(sum += val)하고 흘려보내는 스트리밍(Streaming) 방식 선택
• 종속성 체크 (Loop Merging):
  • max를 찾는 과정과 sum을 구하는 과정이 서로 방해하는가? $\to$ 독립적임
  • 따라서 두 개의 for문을 돌릴 필요 없이, 하나의 루프 안에서 입력, 집계, 최댓값 갱신을 동시에 처리하여 코드를 간결하게 만들었다.

---

5. 앞으로의 적용 (Action Plan)

이번 문제를 통해 정립한, 코드를 작성하기 전 스스로에게 던질 3가지 질문입니다.

1. 펜을 먼저 들었는가? (수식 최적화)

• 무작정 IDE에 for문부터 적지 않는다.
• Action: 연습장에 수식을 적고, 반복되는 연산을 괄호 밖으로 뺄 수 있는지 딱 1분만 검증한다.

2. 데이터를 다시 볼 것인가? (메모리 최적화)

• 습관적으로 new ArrayList<>()를 선언하지 않는다.
• Action: 최종 결과값(합계, 평균)만 필요하다면, 변수 하나에 누적시키고 데이터는 흘려보낸다 (Streaming).

3. 전체 순서가 정말 필요한가? (시간 복잡도)

• 단순히 최댓값/최솟값이 필요할 때비싼 Sort($N \log N$)를 쓰지 않는다.
• Action: 2등, 3등의 순서가 필요 없다면 if문이나 Math.max를 통한 탐색(Scan, $N$)을 선택한다.