[프로그래머스 Lv.1] 푸드 파이트 대회

풀이 날짜 : 2025.05.01
문제 유형 : 연습문제
문제 제목 : 푸드 파이트 대회
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/134240

Intuition

• 음식의 개수를 좌우 대칭으로 하여 가운데 '0'을 두고 음식 배치를 완성해야 하는 문제이다.
  • 주어진 배열(food)의 인덱스가 음식의 번호, 값은 음식의 개수를 의미한다.
  • 음식의 개수가 2보다 작으면 두 선수가 나눠먹을 수 없으므로 제외해야 한다.
• 문자열 조작 문제라고 볼 수 있다.

Approach

• 0을 기준으로 왼쪽에 배치할 문자열을 누적할 변수(left)를 선언한다.
• food를 순회하면서 left를 만든다.
  • 첫번째 요소는 항상 1이므로 제외하고, 음식의 개수가 2보다 작으면 넘어간다.
  • 나눠줘야할 음식의 수(serving) 만큼 현재 인덱스를 반복하여 left에 누적한다.
• left에 ‘0’과 left를 뒤집은 값을 붙여서 반환한다.

Complexity

• Time complexity : O(n)
  • food의 길이를 n 이라고 할 때, forEach → O(n)
• Splace complexity : O(m)
  • left의 길이를 m이라고 할 때 left와 left를 split, reverse 할 때 m만큼의 추가 공간이 필요하다.
  • 종합적으로는 O(m)이다.

Code (JS)

• 개선할 수 있는 포인트
  • 문자열은 불변(immutable)이어서 매번 새로운 문자열을 생성하게 되어 성능에 영향을 미칠 수 있다.
  • 또한, 결과를 도출할 때 어차피 split 메서드를 사용해 배열로 한 번 변환해야 하는 과정이 있다.

function solution(food) {
    let left = '';

    food.forEach((count, i) => {
        if (i === 0 || count < 2) {
            return;
        }
        const serving = Math.floor(count / 2);
        left += i.toString().repeat(serving);
    })

    return left + '0' + left.split('').reverse().join('');
}

• 성능 최적화한 코드

function solution(food) {
    const left = [];

    food.forEach((count, i) => {
        if (i === 0 || count < 2) {
            return;
        }
        
        const serving = Math.floor(count / 2);
        left.push(...Array(serving).fill(+i));
    });

    return left.join('') + '0' + left.reverse().join('');
}