연습문제 > 햄버거 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/133502?language=javascript

프로그래머스

 

1 2 3 1 이 연속되면 그 배열에서 재료 4개 날리고

다시 검사하는 식의 while 무한루프를 만들면 되는데

1 2 3 1 이 연속될 때 i++; 식으로 구현했다가 범위 오버 문제도 있고 참조 문제도 있어서

ingredient.length - 4 (초과하는 오버 범위를 빼기) 

식으로 구현해주는게 좋고

 

while의 조건을 그 전과 비교해 감소했는지 여부를 체크하는 플래그형식으로 구현하는게 좋다

let burgerCount = 0; 로 초기화 해준 다음에

while (ingredient.length !== burgerCount) 의 조건으로 

버거재료의 길이와 0 은 당연히 다르니까 while문을 탄다

 

이때 중요한건 

 

burgerCount = ingredient.length; 로 현재의 버거재료들의 길이를 갱신해줄 필요가 있다

while문의 끝에 다다르면

버거 재료가 10개라고 가정했을 때

1 2 3 1 연속된 조건문을 탈 경우

ingredient.splice(i, 4);  // 시퀀스 발견 위치에서 4개의 원소를 제거

로 버거재료는 감소하게 되고 burgerCount는 감소하지 않으니

 

ingredient.length !== burgerCount

6 !== 10 으로 while문을 또 타게 된다

여기서 다시 갱신 해주면서

burgerCount = ingredient.length;

버거카운트는 10에서 6으로 바뀐다

 

이제 조건문을 못타게 된다면 6 !== 6 이 아니므로 while 문 탈출!

 

 

 

근데 이 문제도 효율성 체크를 한다

 

현재 시간 복잡도는 while문과 for 문의 중첩으로

최악의 경우 O의 n제곱이 되는데

이렇게 해도 

 

 

실패한다

 

2번 테스트 실패의 경우 마지막 3개가 햄버거 재료로서 완성되는 경우인데

어쨋든 시간초과가 나니까 또 다른 방법을 찾아야 한다

도저히 모르겠어서

지피티나 클로드도 잘 못풀길래 잘 다독여주면서 설명 차근차근했더니

클로드가 선수쳤다

 

스택으로 먼저 push 하고

그 스택의 길이가 4개 이상이고 (4개를 제거해야할 수도 있으므로) 그 값이 1 2 3 1 일 경우 

연속된 4개를 제거 하고 카운트를 증가시키는 식으로 함

 

기발하다

지피티가 너무 서운해할까봐 해당코드 설명좀 해달라고 했다 

 

제시된 코드는 스택(stack)을 사용하여 문제를 해결하는 접근 방식을 취하고 있습니다. 이 접근 방법은 배열에서 특정 패턴을 찾고 제거하는 과정을 효율적으로 처리할 수 있도록 설계되었습니다. 다음은 코드의 주요 부분을 분석한 것입니다:

1. 스택의 사용: 함수는 stack이라는 이름의 배열을 사용하여 입력 배열 ingredient의 원소를 하나씩 처리합니다. 스택은 선입후출(LIFO)의 원리를 따르며, 이 문제에서는 패턴 매칭을 확인하기 위해 사용됩니다.
2. 원소의 삽입: ingredient 배열의 각 원소를 순회하면서 스택에 원소를 추가합니다. 이는 입력 배열을 처음부터 끝까지 순차적으로 확인하기 위한 과정입니다.
3. 패턴 매칭 확인: 스택에 원소가 추가될 때마다, 스택의 마지막 네 원소가 특정 패턴 [1, 2, 3, 1]과 일치하는지 확인합니다. 이를 위해 stack.slice(-4)를 사용하여 스택의 마지막 4개 원소를 가져오고, every 함수를 사용하여 패턴과 일치하는지 검사합니다.
4. 패턴 제거 및 카운트 증가: 만약 스택의 마지막 4개 원소가 목표 패턴과 일치하면, 해당 원소들을 스택에서 제거(splice(-4, 4))하고, 패턴 매칭 카운트(count)를 1 증가시킵니다.
5. 결과 반환: 모든 원소의 검사가 끝난 후, 매칭된 패턴의 총 개수를 반환합니다.

성능 분석

이 접근 방법의 장점은 입력 배열을 단 한 번만 순회한다는 것입니다. 스택을 사용하기 때문에, 중간에 배열을 조작할 필요 없이 효율적으로 원하는 패턴을 찾고 제거할 수 있습니다. every 함수와 slice 함수를 사용하는 부분은 비교적 간단한 연산이므로 큰 성능 저하를 일으키지 않습니다.

하지만, 스택에서의 splice 연산은 해당 위치에서 원소를 제거하고 나머지 원소를 이동시키므로, 매 패턴 매칭마다 최악의 경우 O(n)의 시간 복잡도를 가질 수 있습니다. 따라서, 패턴이 자주 발견될수록 성능 저하의 원인이 될 수 있습니다.

개선 방안

이 코드는 이미 매우 효율적으로 작동하지만, 스택에서의 원소 제거를 최소화하거나 다른 자료구조를 사용하여 패턴 매칭 후의 원소 이동을 줄일 수 있는 방법을 모색할 수 있습니다. 예를 들어, 실제로 원소를 제거하지 않고 스택에서의 위치만을 조정하는 방식으로 최적화할 수 있습니다.

전체적으로 이 방법은 문제의 요구사항을 잘 충족시키며, 일반적인 사용 사례에서 충분히 빠른 성능을 보여줄 것입니다.

 

 

다른사람들의 풀이도 봐봤음

비슷하게 스택으로 풀었는데

스택의 후입선출 특성을 활용하여 끝에서부터 자료구조를 탐색함