03/12 알고리즘 공부(68) - 햄버거 만들기

조건

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

제한조건

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

입출력 예

ingredient	result
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

알고리즘 예상

1. ingredient를 String로 바꾸어 ingredientString에 저장한다.
2. do~while문을 이용하여 아래와 같은 과정을 반복한다
   1. string에 1231이 포함되어있는지 확인
   2. 포함되어있다면 반복문 변수 count와 answer에 1을 추가후 replace를 이용해 1231제거
   3. count가 0이면 반복문 종료

 

초기 코드

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        return answer
    }
}

 

내 코드

//테스트 케이스 통과, 출력크기 초과로 인해 실패
class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var ingredientString = ingredient.map { it.toString() }.joinToString("")
        println(ingredientString)
        
        do{
            var count = 0
            if (ingredientString.contains("1231")){
                count ++
                answer ++
                ingredientString = ingredientString.replace("1231", "")
            }
        }while (count != 0)
        
        return answer
    }
}

String타입으로 바꾸어 replace를 이용해 내부 값을 바꾸는 방법을 이용했다. print문으로 인해 출력크기 초과가 나오는것같다.

print문을 지웠는데도 실패가 발생했다. replace를 이용하는 과정에서 나오는 1231을 모두 바꾸는데 answer는 1만 올라서 발생하는 것 같다.

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var ingredientString = ingredient.joinToString("")
        
        do{
            var flag = 0
            if (ingredientString.contains("1231")){
                flag ++
                val ingredientString2 = ingredientString.replace("1231", "")
                answer += (ingredientString.length - ingredientString2.length)/4
                ingredientString = ingredientString2
            }
        }while (flag != 0)
        
        return answer
    }
}

찾아보던 도중 실패의 원인으로 예상되는 문제를 찾았다. 12312311과 같이 앞의 재료부터 햄버거를 만드는 것보다 뒤에 있는 재료로 버거를 먼저 만들 때 더 많은 버거를 만들 수 있을 때를 내 코드가 검사하지 못하는 것 같다.

위 반례를 만든사람과 나는 문제를 잘못 이해했던것 같다. 재료가 한번에 들어오는 것이 아니라 인덱스가 낮은 순서부터 차례로 들어온다. 내 코드의 반례는

[1, 1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1]

이며 처음 배열에 존재했던 1231을 쪼개서 사용하는 부분에서 문제가 발생했다.

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        var ingredientString = ingredient.joinToString("")

        do{
            var flag = 0
            if (ingredientString.contains("1231")){
                flag ++
                val ingredientString2 = ingredientString.replaceFirst("1231", "")
                answer += (ingredientString.length - ingredientString2.length)/4
                ingredientString = ingredientString2
            }
        }while (flag != 0)
        return answer
    }
}​

기존 통과하지 못했던 케이스는 통과했지만 실행시간이 압도적으로 늘어났다.

변수의 값을 바꿀 때마다 새로 데이터를 넣는거라 리소스도 많이 잡아먹었다.

처음부터 설계를 바꿀 필요가 있어보인다.

처음에 스택, 스트링, 스트링빌더를 고민했는데 나머지 두 방법중 하나로 해결해야겠다.

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        val ingredientSB = StringBuilder()
        
        for (i in ingredient) {
            ingredientSB.append(i.toString())
            if (ingredientSB.length >= 4){
                if(ingredientSB.substring(ingredientSB.length - 4) == "1231"){
                ingredientSB.delete(ingredientSB.length - 4, ingredientSB.length)
                answer++
                }
            }
        }
        
        return answer
    }
}

스택풀이의 경우 스택에서 역순으로 4번 pop해야 하는 과정이 있을 것 같아서 StringBuilder를 사용했다.

다른 사람의 풀이

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        val sb = StringBuilder()
        for(item in ingredient) {
            sb.append('0'+item)
            if(sb.length >= 4 && sb.substring(sb.length-4) == "1231") {
                sb.setLength(sb.length-4)
                answer++
            }
        }
        return answer
    }
}

import java.util.*

class Solution {
    fun solution(ingredient: IntArray): Int {
        return ingredient.fold(Stack<Int>()) { acc, i ->
            acc.push(i)
            if (acc.size > 3 && acc[acc.lastIndex] == 1 && acc[acc.lastIndex - 1] == 3 && acc[acc.lastIndex - 2] == 2 && acc[acc.lastIndex - 3] == 1) {
                repeat(4) { acc.pop() }
                acc.insertElementAt(-1, 0)
            }
            return@fold acc
        }.count { it == -1 }
    }
}

개선점 또는 배운점

1. 같은 StringBuilder를 이용해 풀었지만 나는 delete를, 풀이는 setLength라는 메서드를 사용했다. 또한 나는 중첩 조건문을 사용했지만 풀이에서는 조건문 내부에 조건식을 두개 사용했다.
2. 아래 경우에는 fold를 사용한게 신기해서 가지고 와봤다.

 

개선된 코드

class Solution {
    fun solution(ingredient: IntArray): Int {
        var answer: Int = 0
        val ingredientSB = StringBuilder()
        for (i in ingredient) {
            ingredientSB.append(i.toString())
            if (ingredientSB.length >= 4 && ingredientSB.substring(ingredientSB.length - 4) == "1231") {
                ingredientSB.setLength(ingredientSB.length - 4)
                answer++
            }
        }
        return answer
    }
}