[LV1] 햄버거 만들기

마침 햄버거를 시킨 참인데 잘 됐다.

문제 설명

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

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

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

---

제한사항

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

---

입출력 예ingredientresult

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

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 상수가 포장할 수 있는 햄버거가 없습니다.

햄버거의 재료가 랜덤으로 주어지고, 그중 빵-야채-고기-빵, 즉 1-2-3-1이 존재한다면 1-2-3-1을 지워버리는 문제였다.

난이도 치고 정답률이 낮아 의심해 봤는데, 역시 나온지 얼마 되지 않아 해결한 사람이 적어서 생긴 현상이었다. 

역시 세상은 나만 빼고 다 똑똑한 사람들..

 

처음에는 split()을 이용했었다. 주어진 숫자가 1, 2, 3 뿐이기 때문에 배열과 배열을 합친 문자열에는 차이가 없었기 때문. 

let arr1 = [1,2,3,4,5]
let arr2 = [6,7,8,9,10]

console.log(arr1.join("") + " / " + arr1[4])
//result = "12345" / "5"
console.log(arr2.join("") + " / " + arr1[4]))
//result = "678910" / "1"

위 코드처럼 두자리 이상의 숫자가 끼어있을 경우, 배열 요소로써는 하나의 숫자지만 문자열에서는 2개 이상의 문자로 나누어지기 때문에 다루기가 조금 까다롭다. 하지만 한자리 숫자만으로 이루어진 경우에는 배열의 인덱스 = 문자열의 인덱스이므로 훨씬 접근이 수월하다.

1. 배열 ingredient를 join("")으로 하나의 문자열로 만듬
2. "1231"을 기준으로 split()한 뒤 다시 join("")
3. while문을 통해 "1231"이 사라질 때 까지 반복
4. 최종 생성된 문자열의 길이와 기존 배열 ingredient의 길이를 비교한 뒤, 차이를 4로 나눔(문자열 4개당 햄버거 1개가 만들어지기 때문)

let len = ingredient.length
//ingredient의 길이를 미리 저장
ingredient = ingredient.join("")
//ingredient를 문자열로 바꿈
while(ingredient.match("1231")){
//ingredient 안에 "1231"이 존재하지 않을 때 까지 반복
    ingredient = ingredient.split("1231").join("")
    //ingredient를 "1231"로 나눈 뒤, 다시 붙임
}
answer = (len  - ingredient.length) / 4

매우 간단했다. 끝!

하지만 이 블로그에 쓰여있다는건 이렇게 호락호락하게 넘어갈 문제가 아니었다는 것을 말하지! 

 

문제, 특히 예시를 잘 읽어보면, 재료가 한번에 주어지는 것이 아니라 순차적으로 쌓인다는 것을 알 수 있다. 한마디로 한번에 2개 이상의 햄버거를 만들 수는 없다는 것이다. 

[1,2,1,2,3,1,3,1,2,3,1,2,3,1] 이라는 배열을 예로 들어보자.

들어온 재료	배열	만들어진 햄버거 수(누적)
0	[]	0
6	[1,2,1,2,3,1]	1
8	[1,2,1,2,3,1,3,1]	2
14	[1,2,1,2,3,1,3,1,2,3,1,2,3,1]	3

정답대로라면, 재료가 순차적으로 들어와 다음과 같은 과정을 통해 햄버거가 총 3개 만들어지는 것을 알 수 있다.

하지만 내가 쓴 코드를 사용하면

반복 횟수	배열	만들어진 햄버거 수(누적)
0	[1,2,1,2,3,1,3,1,2,3,1,2,3,1]	0
1	[1,2,1,2,3,1,3,1,2,3,1,2,3,1]	2
2	[1,2,3,2,3,1]	2

다음과 같이 2개의 햄버거밖에 만들 수 없다. 그렇다면 재료가 순차적으로 들어오는 것을 감안하여 문제를 해결해야 한다. 

 

그러기 위해서는 다음과 같은 메커니즘을 생각해 보았다.

1. 배열의 요소를 4개씩 탐색
2. 만약 4개의 배열이 [1, 2, 3, 1]이라면 배열에서 해당 부분 제거한 뒤 answer에 1을 더함
3. 제거한 배열을 다시 4개씩 탐색

이를 구현하기 위해선 for문보다는 while문이 적합하다고 생각하여 while문을 통해 구현하였다.

먼저 초기값 i를 0으로 초기화한 뒤, i가 ingredient의 길이보다 커지면 반복을 종료하는 것으로 설정했다.

배열 요소를 4개씩 탐색하는 것은, slice()와 join(""), 그리고 match()를 이용했다.

배열을 i부터 i+4까지 slice()한 뒤, join("")으로 이어붙이고 match()를 통해 "1231"과 같은지를 살펴 주었다.

주어진 배열	slice(i, i+4)	join("")	match("1231")
[1,2,1,2,3,1], i = 2	[1,2,3,1]	"1231"	true

ㅁ이렇게 찾은 배열의 요소가 [1,2,3,1]이라면, splice()로 해당 부분을 제거한다.

i가 [1,2,3,1]이 시작하는 인덱스이므로, i부터 i+4까지 삭제해주기 위해  splice(i, 4)를 실행해주면 된다.

주어진 배열	splice(i, 4)	제거 후 배열
[1,2,1,2,3,1], i = 2	[1,2,3,1]	[1,2]

splice에 대한 자세한 설명은 여기

2023.01.15 - [코딩 테스트 공부/Study] - splice()

splice()

그 다음 과정이 중요하다. 제거 후 배열의 처음부터 [1,2,3,1]을 찾아 주어야 한다. 

그러기 위해서는 탐색을 시작할 위치, i를 다시 0으로 바꿔준다.

 

만약 i번째 인덱스부터 탐색한 요소가 [1,2,3,1]이 아니라면??

i에 1을 더해 i+1번째 인덱스부터 다시 탐색을 시작하면 된다.

let i = 0
while(i < ingredient.length){
//i가 ingredient의 길이보다 커지면 반복 종료
    if(ingredient.slice(i, i+4).join("").match("1231")){
    //4개 요소를 탐색하여 [1,2,3,1]이 있으면
        ingredient.splice(i, 4)
        //[1,2,3,1]을 잘라냄
        i = 0
        //i를 0으로 초기화
        answer++
        //answer에 1 더함
    } else {
    //[1,2,3,1]이 없으면
        i++
        //i에 1을 더해 다시 탐색
    }
}

예제는 가볍게 통과했고, 테스트 케이스를 돌려보는데.....

어라라???

내가 가장 싫어하는 '그 반응'!!!!

이는 ingredient의 길이가 무수히 길때! for문을 돌리는 시간이 오래 걸려 시간 초과가 발생하는 것이라 했다!

마치 소수의 개수 문제를 풀 때 와 같다....OTL(옛날사람)

따라서 실행 시간을 최대한 줄여줄 방법이 필요했다.

내가 조정할 수 있는 것은 i의 시작 위치와 [1,2,3,1]을 찾았을 때 탐색을 다시 시작할 위치.

 

먼저 i의 시작 위치는 [1,2,3,1]이 최초로 등장하는 위치로 설정시켰다.

[1,2,1,2,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,3,1] 같은 극단적인 배열이 주어졌을 때, 

0번 인덱스부터 탐색

을 시작한다면 거진 30회가 넘는 불필요한 반복이 발생한다.

이는 런타임을 잡아먹는 커다란 요소중 하나이므로, 이러한 불필요한 반복을 없애주어야 했다.

따라서, 저 배열들 중 [1,2,3,1]이 처음 등장하는 부분을 i 로 설정해 주어야 한다.

indexOf()와 join("")을 사용해 [1,2,3,1]이 처음 등장하는 부분을 찾아주면 된다.

 

배열을 join("")으로 이어붙인 뒤 indexOf("1231")을 실행하면, 가장 처음 등장하는 "1231"의 시작 인덱스가 리턴된다. 해당 인덱스를 i로 설정하면, i는 앞의 불필요한 부분을 건너뛰고 가장 처음 등장하는 "1231"의 시작 인덱스부터 탐색을 시작하는 것이다. 물론 0으로 설정해도 크게 문제는 없다. [1,2,3,1]이 바로 등장하는 경우도 있기에...

let i = ingredient.join("").indexOf("1231")

배열	join("")	indexOf("1231")
[1,2,1,2,1,2,1,2,3,1]	"1212121231"	6

 

그 다음은 [1,2,3,1]을 찾아냈을 때 다음 인덱스가 가야 할 곳이다. 

이 부분은 굉장히 고민을 많이 했는데,  indexOf()와 join("")을 또 사용한다면 불필요한 탐색이 추가될 것 같아 사용하지 않았다. 한참을 고민하다가, 문득 배열 하나가 떠올랐다.

[1,3,1,2,1,2,3,1,3,1]이라는 배열을 보자. [1,2,3,1]을 제거하면 [1,3,1,2,3,1]만 남게 된다. 그러면 또 [1,2,3,1]이 생긴다.

어차피 시작 인덱스 i 이전까지는 [1,2,3,1]이 등장하지 않았다는 말이 되니, 우리는 [1,2,3,1]이 또 다른 [1,2,3,1] 사이에 들어 있는지만 판단해 주면 된다는 것이다!

원래 배열	제거 후
[1,1,2,3,1,2,3,1]	[1,2,3,1]
[1,2,1,2,3,1,3,1]	[1,2,3,1]
[1,2,3,1,2,3,1,1]	[2,3,1,1]

[1,2,3,1] : 최초로 등장한 [1,2,3,1]

[1,2,3,1] : 최초로 등장한 [1,2,3,1]을 제거한 후 등장한 [1,2,3,1]

ex)[1,2,1,2,3,1,3,1] => [1,2,[1,2,3,1],3,1] => [1,2,3,1]

 

[1,2,3,1]이 또다른 [1,2,3,1]의 1과 2뒤에 끼어 있을때만 제거 후에도 [1,2,3,1]이 나타났다. 

[1,2,3,1]이 나타난 인덱스부터 탐색을 시작하므로, 최초 [1,2,3,1]을 제거한 배열에서 [1,2,3,1]이 나타난다면, 다시 해당 인덱스부터 탐색을 재개한다. 이때 최초 [1,2,3,1] 앞에는 제거 후 배열 [1,2,3,1]의 1 또는 1, 2만 존재할 수 있다.

쉽게 말해, [1,2,3,1]이 나타난 인덱스 i의 -1, -2 부분부터 탐색을 재개하면 된다는 것이다.

따라서, i = i - 2로 바꿔 주면 되었다.

 

이 방법을 사용하니 시간이 확실히 줄었다.

function solution(ingredient) {
    var answer = 0;
    let i = ingredient.join("").indexOf("1231")
    while(i < ingredient.length){
        if(ingredient.slice(i, i+4).join("").match("1231")){
            ingredient.splice(i, 4)
            i = i - 2
            answer++
        } else {
            i++
        }
    }
    return answer;
}

시간 초과에 걸리는 문제들이 몇 있는데, 이런 불필요한 반복을 없애는 연습도 많이 해야겠다고 느꼈다.