푸드 파이트 대회

문제 링크

문제 요약

• food[i]는 i번 음식의 개수, food[0]은 항상 1(물)
• 각 음식을 절반씩 나눠서 칼로리 낮은 순서대로 왼쪽에 배치, 중앙에 물, 오른쪽은 대칭으로 배치
• 홀수 개의 음식은 1개를 못 쓰고 버려짐

처음 작성한 코드

import java.util.Arrays;
class Solution {
    public String solution(int[] food) {
        String answer = "";
        int arrLength = 1;
        for (int i = 1; i < food.length; i++) {
            if (food[i] % 2 == 0) {
                arrLength += food[i];
            } else if (food[i] % 2 == 1) {
                arrLength += food[i] / 2 * 2;
            }
        }

        int[] foodLocation = new int[arrLength];
        int start = 0;
        int end = foodLocation.length - 1;

        for (int i = 1; i < food.length; i++) {
            int foodCnt = 0;
            int foodidx = i;
            if (food[i] % 2 == 0) {
                foodCnt = food[i] / 2;
            } else if (food[i] % 2 == 1) {
                foodCnt = food[i] / 2;
            }

            for (int j = 0; j < foodCnt; j++) {
                foodLocation[end] = foodidx;
                foodLocation[start] = foodidx;
                start++;
                end--;
            }

            if (end == start) {
                foodLocation[(end + start) / 2] = 0;
                break;
            }
        }

        for (int num : foodLocation) {
            answer += String.valueOf(num);
        }

        return answer;
    }
}

일단 정답은 맞았지만, 다시 보니 문제가 몇 개 보였다.

문제점 1 — 짝수/홀수 분기가 사실 필요 없었다

홀수면 1개를 버려야 한다는 규칙 자체는 맞다. 근데 그걸 표현하려고 짝수/홀수를 나눠서 각각 다른 식을 쓴 게 중복이었다.

food[i] / 2 * 2에 직접 숫자를 넣어봤다.

• food[i] = 6 (짝수) → 6 / 2 * 2 = 6 → 짝수일 때 그냥 food[i]를 쓰는 것과 결과가 같다.
• food[i] = 7 (홀수) → 7 / 2 * 2 = 6 → 1개가 버려진 결과.

즉 정수 나눗셈(/)이 나머지를 버리는 성질 때문에, 짝수/홀수 상관없이 food[i] / 2 * 2 한 줄이면 두 경우를 다 처리할 수 있었다. if-else로 나눌 이유가 없었다.

foodCnt 계산도 마찬가지였다. 두 분기 다 food[i] / 2로 동일해서 분기 자체를 지웠다.

문제점 2 — answer += String.valueOf(num) 반복

자바 String은 불변 객체라 +=로 계속 이어붙이면 매번 새 객체를 만든다. food 길이가 최대 9라 이 문제에서는 성능에 영향이 없지만, 입력이 컸다면 비효율적인 방식이라 StringBuilder로 바꿨다.

문제점 3 — 배열을 두 번 순회하고 있었다

int[] foodLocation을 채우는 루프, 그걸 다시 순회하며 StringBuilder(혹은 answer)에 옮기는 루프, 이렇게 2단계였다.

char가 자바에서 사실 숫자(유니코드 코드)라는 걸 이용해서 해결했다.

int x = 3;
char c = (char)('0' + x);  // c는 '3'

'0'의 코드값에 숫자를 더하면 그 숫자에 해당하는 문자 코드가 나온다는 원리다. 이걸로 int[] 대신 char[] foodLocation을 쓰고, 숫자를 넣던 자리에 (char)('0' + foodidx)를 넣었다.

그리고 char[]는 new String(char[] value) 생성자로 바로 문자열이 된다는 걸 처음 알았다. (int[]에는 이런 생성자가 없다 — char는 이미 "문자"라는 의미가 있어서 String이 그대로 이어붙일 수 있는 것.) 이 생성자 덕분에 마지막 순회 루프 자체가 없어졌다.

마지막 — 안 쓰는 코드 정리

리팩토링하고 나니 import java.util.Arrays;, StringBuilder sb = new StringBuilder();가 더 이상 안 쓰이는데 그대로 남아 있었다. 둘 다 삭제.

최종 코드

class Solution {
    public String solution(int[] food) {

        int arrLength = 1;
        for (int i = 1; i < food.length; i++) {
            arrLength += food[i] / 2 * 2;
        }

        char[] foodLocation = new char[arrLength];
        int start = 0;
        int end = foodLocation.length - 1;

        for (int i = 1; i < food.length; i++) {
            int foodidx = i;
            int foodCnt = food[i] / 2;

            for (int j = 0; j < foodCnt; j++) {
                foodLocation[end] = (char) ('0' + foodidx);
                foodLocation[start] = (char) ('0' + foodidx);
                start++;
                end--;
            }

            if (end == start) {
                foodLocation[(end + start) / 2] = '0';
                break;
            }
        }

        return new String(foodLocation);
    }
}

배운 점

• 정수 나눗셈(/)은 나머지를 버리는 성질이 있어서, 짝수/홀수를 굳이 분기하지 않아도 같은 식으로 처리되는 경우가 있다.
• 반복문 안에서 String += 은 매번 새 객체를 만드므로 StringBuilder를 쓰는 게 좋다.
• char는 내부적으로 숫자(유니코드 코드값)라서 (char)('0' + n) 형태로 숫자 ↔ 문자 변환이 가능하다.
• String(char[] value) 생성자로 문자 배열을 한 번에 문자열로 만들 수 있다. int[]에는 이런 생성자가 없다.
• 리팩토링 후에는 안 쓰는 import나 변수가 남아있는지 항상 확인하는 습관이 필요하다.