프로그래머스 [연습문제 / 푸드 파이트 대회](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 푸드 파이트 대회

---

문제 링크: 문제 보기

문제 설명:

각 음식 종류별로 제공 가능한 개수가 주어질 때, 양쪽 선수가 공평하게 음식을 나눠 갖고, 가운데에는 항상 '0'(물)을 배치해야 합니다. 각 음식은 좌우 대칭으로 배치되어야 하며, 음식을 적절히 절반으로 나눈 후 대칭 구조로 정답 문자열을 구성해야 합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

string solution(vector<int> food) {
    string answer = "";
    string r = "";

    // 각 음식의 절반만큼 문자열 생성
    for (int i = 1; i < food.size(); i++) {
        int k = food[i] / 2;
        for (int j = 0; j < k; j++) {
            r += to_string(i);
        }
    }

    // 완성된 음식 문자열 + '0'(물) + 역순 문자열 추가
    answer += r;
    reverse(r.begin(), r.end());
    answer += '0';
    answer += r;

    return answer;
}

---

코드 설명

• 핵심 알고리즘: 각 음식 개수의 절반만큼 문자열을 구성하여 왼쪽 음식 배열을 만들고, 이를 역순으로 복제하여 오른쪽 배열을 만듭니다. 중간에 '0'(물을 의미)을 배치합니다.
• 구현 세부사항:
• food[i] / 2를 통해 양 선수가 가져갈 수 있는 음식 개수를 구함
• reverse 함수를 사용해 대칭되는 문자열을 생성
• 문자열 중앙에는 항상 '0'이 위치
• 시간 복잡도 분석:
• 음식 수 n일 때, 최대 O(n + m), m은 총 음식 수
• reverse 연산: O(m)
• 총 시간 복잡도: O(n + m)

---

결과

이 코드는 음식 배치를 문자열로 구성하여 푸드 파이트 대회의 조건에 맞는 결과를 정확하게 반환합니다. 정렬이나 복잡한 자료구조 없이 문자열 조작만으로 효율적인 해결이 가능합니다.

다른 방법으로는 stringstream을 활용하거나, 미리 크기를 계산하여 문자열 배열에 넣는 방식도 있으며, 성능 차이는 미미합니다.