[LV.3] 연습문제 > 푸드 파이트 대회

문제

https://school.programmers.co.kr/learn/courses/30/lessons/134240

프로그래머스

---

문제 설명

• 두 선수는 음식들을 양쪽에서 동시에 먹기 시작하고, 중앙에 있는 물(0번 음식)을 먼저 먹는 선수가 승리
• 음식은 칼로리가 낮은 순서대로 준비되어 있고, 같은 종류, 같은 양의 음식을 같은 순서로 먹어야 함
• 일부 음식은 규칙에 맞게 나눌 수 없어 사용되지 않을 수 있음
  • 예: [1, 3, 4, 6] → "1223330333221"
    (1번 1개, 2번 2개, 3번 3개씩만 사용)
• 제한사항)
  2 ≤ food의 길이 ≤ 9
  1 ≤ food의 각 원소 ≤ 1,000
  food에는 칼로리가 적은 순서대로 음식의 양이 담겨 있음
  food[i]는 i번 음식의 수
  food[0]은 수웅이가 준비한 물의 양이며, 항상 1
  정답의 길이가 3 이상인 경우만 입력으로 주어짐

---

정답 코드

def solution(food):
    answer = ''
    
    for i, cnt in enumerate(food):
        answer += str(i) * (cnt//2)

    return answer + "0" + answer[::-1]

---

코드 설명

• answer = ''
  • 왼쪽 선수가 먹는 음식 순서를 저장할 문자열
• for i, cnt in enumerate(food):
  • 음식 리스트 food를 순회하면서:
    • i는 음식 번호 (0번은 물)
    • cnt는 해당 음식의 총 개수
• answer += str(i) * (cnt // 2)
  • 각 음식의 절반 개수만큼만 사용해야 하므로 cnt // 2개를 선택
  • str(i) * n → 음식 번호 i를 문자열로 바꿔서 n번 반복
    • 예: 음식 2번이 4개 → '2' * (4 // 2) = '22'
  •  i = 0 (물)은 어차피 cnt // 2 = 0이므로 무시됨 (음식의 총 개수가 1개인 것도 무시됨)
• return answer + "0" + answer[::-1]
  • 최종 문자열 구성:
    • 왼쪽 선수 음식: answer
    • 중앙 물: "0"
    • 오른쪽 선수 음식: answer[::-1] (왼쪽 순서의 반대)

---

개선점

문자열 반복/덧셈의 성능	+=는 문자열마다 새로운 메모리 할당이 일어나므로, 반복이 많을수록 느려짐 (특히 입력이 클 때)
answer와 answer[::-1] 중복	역순 문자열 만들기 위해 전체를 다시 저장해야 함 → 메모리 낭비 가능
음식 번호 0번도 무의미하게 계산	어차피 0번 음식은 물이고, cnt // 2 = 0이라 생략해도 됨

---

개선된 코드

def solution(food):
    left = []

    # 음식 번호 1부터 시작 (0은 물이라 무시)
    for i in range(1, len(food)):
        left.append(str(i) * (food[i] // 2))

    # 좌우 대칭 + 중앙에 물 '0' 배치
    return ''.join(left) + '0' + ''.join(reversed(left))

---

코드 설명

• left = []
  • 좌측 선수의 음식 순서를 담을 리스트
  • 문자열 덧셈 대신 리스트에 모아두면 성능이 더 좋음 (join() 사용 예정)
• for i in range(1, len(food)):
  • i는 음식 번호 (1부터 시작)
  • food[0]은 물이므로 무시
  • food[i]는 해당 음식의 총 개수
• left.append(str(i) * (food[i] // 2))
  • food[i] // 2: 해당 음식을 반으로 나눈 개수 → 각 선수가 가져갈 양
  • str(i) * ...: 음식 번호를 문자열로 만들어 필요한 개수만큼 반복
    • 예: i=2, food[2]=4 → '2' * 2 = '22'
  • 만들어진 문자열을 리스트 left에 추가
• ''.join(left)
  • left 리스트 안에 문자열들이 들어 있음
    • 예: ['1', '22', '333']
  • 이를 하나의 문자열로 합침 → '122333'
  • 이게 좌측 선수의 먹는 순서
• ''.join(reversed(left))
  • left를 거꾸로 뒤집어서 오른쪽 선수의 음식 순서를 만듦
  • reversed(left)는 ['333', '22', '1']
  • join()하면 '333221'

---

첫 번째 시도 (실패)

def solution(food):
    answer = ''
    step = ''
    
    for i, cnt in enumerate(range(1, len(food)+1)):
        answer.append(i * (cnt//2))
        step.append(i * (cnt//2))

    answer.append(0)
    answer.append(step[::-1])
    
    return answer

---

문제점

enumerate(range(...))	range(1, len(food)+1)는 그냥 1~N 숫자
append() 사용	answer와 step이 문자열인데, 문자열에는 append() 못 씀 → 리스트로 바꾸거나 += 사용해야 함
i * (cnt//2)	i는 0, 1, 2,...인데 음식 번호로 쓰는 건 1부터 시작이니까 혼동 생김
answer.append(0)	문자열에 정수 append 불가 → "0"처럼 문자열로 넣어야 함
step[::-1] 붙이기	문자열 연결할 땐 += 또는 join() 사용해야 함

---

두 번째 시도 (실패)

def solution(food):
    answer = ''
    step = ''
    
    for i, cnt in enumerate(food):
        answer += i * (cnt//2)
        step += i * (cnt//2)

    answer += "0"
    answer += step[::-1]
    
    return answer

---

문제점

answer += i * (cnt // 2)

• i는 정수, cnt // 2도 정수이기 때문에 i * (cnt // 2)는 숫자 결과 → answer +=로 문자열에 더하려고 하면 오류남

---

세 번째 시도 (성공)

def solution(food):
    answer = ''
    step = ''
    
    for i, cnt in enumerate(food):
        answer += str(i) * (cnt//2)
        step += str(i) * (cnt//2)

    answer += "0"
    answer += step[::-1]
    
    return answer

• step은 사실 answer랑 동일하니까, 별도 변수 없이도 가능 (코드 간결하게 바꿔보기)