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

https://school.programmers.co.kr/learn/courses/30/lessons/134240?language=swift

프로그래머스

 

문제 정리

1. 문제 요구사항 정의
2명의 선수들이 대회에서 책상 양쪽에서 가운데를 향해 음식을 먹는 대결을 함.
승리 조건: 중앙에 있는 물을 먼저 먹는 선수
환경: 두 선수가 먹는 음식의 종류와 양이 같아야 함.
환경: 두 선수가 음식을 먹는 순서도 같아야 함.
환경: 칼로리가 낮은 음식을 먼저 먹을 수 있게 배치.
환경: 수웅이가 준비해온 음식 중 몇개는 대회에 사용하지 못함.
=> 구할 것: 음식의 배치 string값

2. 제약사항
2 ≤ food의 길이 ≤ 9
1 ≤ food의 각 원소 ≤ 1,000
food에는 칼로리가 적은 순서대로 음식의 양이 담겨 있습니다.
food[0]은 수웅이가 준비한 물의 양이며, 항상 1입니다.
food[i]는 i번 음식의 수입니다.
정답의 길이가 3 이상인 경우만 입력으로 주어집니다.

3. 메모리 및 시간복잡도 확인
표기상으로는 메모리 및 시간 제한 없음

4. 풀이방법

0의 왼쪽 반 구하기 + "0" + 0의 왼쪽.reverse

0의 왼쪽 반 구하는 방법: food 배열을 순회하며 2로 나눈 값만큼 result 배열에 더하기

 

5. 복잡도보고 다시 풀이 고민

생략

6. 엣지 확인

생략

 

풀이 1.

import Foundation

func solution(_ food:[Int]) -> String {
    var result = ""
    
    for i in 1..<food.count {
        if food[i] >= 2 {
            for re in 0..<food[i] / 2 {
                result += String(i)
            }
        }
    }
    
    return result + "0" + result.reversed()
}

 

 

시간초과가 나서 어디서 오래걸렸을까 다시 봤는데, 반복문 내부에서 String(i)를 food[i] / 2 만큼하고 있었던게 문제가 아니었을까 싶었다. food[i]에 1000이 들어갈 수 있으니 2를 나누면 500번이고, food 개수만큼 그 외부에서 반복하니 최대 500*9 = 4500번을 형변환하는 것이다. ㅎㅎ,ㅎㅎ 형변환하고 더하고~ 형변환하고 더하고~

 

알고리즘 자체를 다시 생각해볼까 하다가 쉽게 접근해서 형변환만 한 번 하도록 수정해서 테스트했다.

 

풀이 2. 형변환 수정

func solution(_ food:[Int]) -> String {
    var result = ""
    
    for i in 1..<food.count {
        let strI = String(i)
        for re in 0..<food[i] / 2 {
           result += strI
        }
    }
    
    return result + "0" + result.reversed()
}

결과값이 전체적으로 줄어든게 아니라 더 길어진것도, 더 짧아진 것도 있지만, 모두 0.80ms 내외로 통과했다.

 

풀이 3.

사실 처음에 반복문으로 result를 업데이트하는게 아니라 String의 repeat관련한 메서드를 찾아보고 싶었는데, 아는 걸 바탕으로 해보자!는 마음으로 반복문을 썼고, 문제는 해결했으니 문자열을 반복하여 초기화하는 메서드를 더 찾아보았다.

 

String(repeating: "OK" count: 5) 

찾아보니 이러한 초기화 메서드가 있었다. 

Array의 초기화 방식에도 유사한게 있었는데, String에도 있었던 것이다.

func solution(_ food:[Int]) -> String {
    var result = ""
    
    for i in 1..<food.count {
        if food[i] >= 2 { 
            result += String(repeating: String(i), count: food[i]/2) 
        }
    }
    
    return result + "0" + result.reversed()
}

 

전체적으로 시간이 줄어든 걸 알 수 있다 ! !

이제부터 애용할게요 !

 

비교

복잡하고 어려운 문제는 아니었지만, 비교만 해보고 끝내야겠다.

1) 반복문 내부에서 형변환하며 업데이트, 2) 형변환한 값으로 반복하여 업데이트, 3) String(repeating: count:) 활용하여 초기화 및 업데이트

드라마틱하진 않아도 대부분 3번이 조금씩 시간이 적게 소요되는 걸 알 수 있다.

 

결론은 String(repeating: "OK" count: 5) 알아두자 ! 는 말이다.

언젠간 유용하게 쓸 것이다 :)