< 프로그래머스 C++ > 푸드 파이트 대회

문제 설명

수웅이는 매달 음식을 빨리 먹는 푸드 파이트 대회를 개최한다. 대결은 두 선수가 1대 1로 진행하며, 음식들을 일렬로 배치한 뒤 한 선수는 왼쪽에서 오른쪽으로, 다른 선수는 오른쪽에서 왼쪽으로 먹는 방식이다. 중앙에는 물(0)을 배치하고, 물을 먼저 먹는 쪽이 승리한다.

대결의 공정성을 위해 두 선수가 먹는 음식의 종류와 양, 순서가 모두 같아야 한다. 음식의 양이 홀수개 있으면 짝을 맞출 수 없으므로 그 한 개는 사용하지 않는다.

음식의 양이 칼로리가 적은 순서대로 주어졌을 때, 대회를 위한 음식의 배치를 문자열로 반환하면 된다.

food = [1, 3, 4, 6]
result = "1223330333221"

food = [1, 7, 1, 2]
result = "111303111"

food[0]은 물이고, food[1]부터가 칼로리 순으로 나열된 음식이다.

---

문제 해석

food = [1, 3, 4, 6]일 때 결과를 가운데 0을 기준으로 나눠보면

왼쪽: "122333"    가운데: "0"    오른쪽: "333221"

 

왼쪽 부분은 어떻게?

각 음식 인덱스 i(1부터)에 대해, food[i] / 2개만큼 i를 반복해서 이어붙이면 된다.

인덱스 i	food [i]	food [i] / 2	결과
1	3	1	"1"
2	4	2	"22"
3	6	3	"333"

이걸 모두 이어붙이면 왼쪽 부분

"122333"

이 된다. food[i]가 홀수여도 / 2는 정수 나눗셈이라 자동으로 절반(소수점 버림)만 사용된다.

 

사용 도구

• to_string
• <algorithm>의 reverse함수

---

문제 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<int> food) {
    string answer = "";
    string left = "";
    
    for(int i = 1; i < food.size(); ++i)
    {
        for(int j = 0; j < food[i] / 2; ++j)
        {
            left += to_string(i);
        }
    }
    
    string right = left;
    reverse(right.begin(), right.end());
    
    answer = left + "0" + right;
    
    return answer;
}

 

핵심 포인트

1. to_string

to_string 은 숫자(int, float 등)를 문자열로 변환하는 함수이다. <string> 헤더에 있다.

문자열 연결 시 숫자를 직접 쓸 수 없기 때문에 변환이 필요하다.

// 안 됨 - int와 string은 + 연산 불가
string s = "Hello" + 123;

// to_string으로 변환
string s = "Hello" + to_string(123);   // "Hello123"

// 이번 문제처럼 사용
left += to_string(i);

 

2. 이중 반복문 구조

for(int i = 1; i < food.size(); ++i)        // 음식 종류 순회
{
    for(int j = 0; j < food[i] / 2; ++j)    // 그 음식의 절반만큼 반복
    {
        left += to_string(i);
    }
}

바깥 반복문은 음식 종류를 순회하고, 안쪽 반복문은 해당 음식을 몇 개 놓을지 결정한다.

 

인덱스0은 물이기 때문에 가운데에만 들어가므로 인덱스 1부터 시작해야한다.

 

food[i] / 2는 정수 나눗셈이다. C++에서 int끼리의 나눗셈은 소수점이 자동으로 버려진다. 5 / 2 = 2, 7 / 2 = 3이 되어 홀수일 때 자동으로 짝을 맞춘 개수만 만들어진다.

 

3. reverse함수

reverse는 컨테이너의 일정 구간을 뒤집는 함수이다. <algorithm> 헤더에 있다.

문자열 전체를 뒤집을 때는 begin()과 end()를 넘긴다.

reverse(시작_iterator, 끝_iterator);

 

 

특정 구간만 뒤집을 수도 있다.

reverse(s.begin(), s.begin() + 3);   // 앞 3글자만 뒤집기

 

이번 문제에서는 left를 복사한 후 통째로 뒤집어서 right를 만들었다.

string right = left;            // 먼저 복사
reverse(right.begin(), right.end());   // 그 다음 뒤집기

 

reverse는 원본을 변경하는 함수라서, left를 그대로 뒤집으면 left 자체가 바뀐다.

원본을 보존하려면 반드시 복사한 후 뒤집어야 한다.

 

4. 문자열 연결

C++의 string은 + 연산자로 연결할 수 있다.

answer = left + "0" + right;

 

여러 개의 문자열을 한 번에 이어붙일 수 있어 코드가 간결해진다.

 

+= 연산자도 같은 맥락이다.

left += to_string(i);

---

정리

이 문제의 핵심은 결과 문자열의 대칭 구조를 알아채는 것이다.

 

처음 봤을 때는 두 선수가 양쪽에서 먹는다는 설명이 복잡해 보이지만, 실제로는 왼쪽 + "0" + 뒤집은 왼쪽 형태의 단순한 팰린드롬 구조이다.

• 왼쪽 부분만 만들어서 한 번 뒤집어 붙이면 끝
• to_string으로 int  >> string 변환
• reverse는 원본을 바꾸기 때문에 복사본을 만들어 사용