20250311

 

 

 

코딩테스트

프로그래머스

 

배열의 값이 의미하는 건 다음과 같습니다.

예를 들어 배열이 [1, 3, 4, 6] 이라면:

• 인덱스는 음식의 종류를 나타냅니다. (0번 음식은 항상 물입니다.)
• 각 값은 그 음식이 준비된 개수입니다.

즉,

인덱스음식준비된 개수

0	물	1개 (항상 1)
1	1번 음식 (가장 낮은 칼로리)	3개
2	2번 음식 (중간 칼로리)	4개
3	3번 음식 (가장 높은 칼로리)	6개

---

음식 배치 과정 이해하기 (예시 [1, 3, 4, 6])

• 음식을 가운데 물(0)을 기준으로 양쪽으로 대칭적으로 배치합니다.
• 두 선수가 같은 양의 음식을 같은 순서로 먹어야 하므로, 각 음식은 반드시 짝수 개를 써야 합니다. (양쪽이 같으려면 2의 배수로 나눠서 좌우로 나눠주기 때문입니다.)
• 따라서 각 음식의 개수를 짝수로 맞춘 뒤 남는 음식은 쓰지 못합니다.

음식준비된 개수사용할 수 있는 개수선수A(왼쪽)물(가운데)선수B(오른쪽)남는 음식

1번 음식	3개	2개 (짝수로 최대한 맞춘 개수)	1개	물	1개	1개 남음
2번 음식	4개	4개	2개	물	2개	0개 남음
3번 음식	6개	6개	3개	물	3개	0개 남음

• 왼쪽 선수는 낮은 칼로리부터 차례대로 먹음 (1, 2, 2, 3, 3, 3)
• 오른쪽 선수는 그 반대 순서로 먹음 (3, 3, 3, 2, 2, 1)

가운데 물(0)을 넣으면 최종 배치는:

복사편집

1 2 2 3 3 3 | 0 | 3 3 3 2 2 1

→ 최종적으로 "1223330333221"이 되는 것입니다.

---

정리하자면

• 주어진 배열의 값은 음식의 개수이며,
• 각 음식을 양쪽 선수에게 공평하게 배분하고,
• 가운데에 항상 물을 배치하고,
• 낮은 칼로리부터 배치해서 결과 문자열을 만드는 것입니다.

 

 

 

 

코드 핵심 아이디어

• 각 음식의 개수를 2로 나눈 몫 만큼만 좌우에 배치할 수 있습니다.
• 왼쪽 선수가 먹을 음식 배열을 만든 후,
  (왼쪽 음식) + (물 0) + (왼쪽 음식의 역순) 으로 붙여주면 쉽게 해결할 수 있습니다.

---

알고리즘 순서

1. 배열을 왼쪽에서 오른쪽으로 순회하며 각 음식의 개수를 2로 나눈 몫만큼 문자열로 이어 붙입니다.
   • 예) [1,3,4,6]의 경우
     • 1번 음식: 3 ÷ 2 = 1개 → "1"
     • 2번 음식: 4 ÷ 2 = 2개 → "22"
     • 3번 음식: 6 ÷ 2 = 3개 → "333"
   • 결과 → "122333"
2. 가운데 물("0")을 붙입니다.
   • 결과 → "1223330"
3. 마지막으로 1에서 만든 문자열을 뒤집어서 오른쪽 음식을 만듭니다.
   • "333221"
4. 이 세 가지를 연결하면 최종 결과가 됩니다.
   • "1223330" + "333221" → "1223330333221"

class Solution {
    public String solution(int[] food) {
        StringBuilder left = new StringBuilder();

        // 0번은 물이므로 1부터 시작합니다.
        for (int i = 1; i < food.length; i++) {
            int count = food[i] / 2; // 두 선수에게 공평히 나눠줌
            for (int j = 0; j < count; j++) {
                left.append(i);
            }
        }

        // 오른쪽 음식은 왼쪽 음식을 뒤집은 것입니다.
        String right = left.reverse().toString();
        
        // reverse()가 원본을 바꾸므로, 다시 원상복귀 후 연결해야 함
        left.reverse(); 

        // 최종 결과 조합
        return left.toString() + "0" + right;
    }
}