728x90
반응형
문제 설명
문제 분석
- 햄버거 가게에서 일하는 상수는 정해진 순서(아래서부터 빵-야채-고기-빵)로 쌓인 햄버거를 포장해야 합니다.
- 재료가 순서대로 들어올 때마다 햄버거를 만들 수 있는지 확인하고, 만들 수 있다면 포장합니다.
- ingredient 배열에는 1(빵), 2(야채), 3(고기)의 값이 담겨있습니다.
- 상수가 포장할 수 있는 햄버거의 개수를 반환해야 합니다.
첫 번째 접근: 문자열 조작(O(n²) ) (시간 초과)
function solution(ingredient) {
const hamburger = '1231'
let answer = 0
ingredient = ingredient.join('')
while(ingredient.includes(hamburger)) {
ingredient = ingredient.replace(hamburger, '')
answer += 1
}
return answer
}
- 매번 전체 문자열에서 패턴을 검색하는 includes()와 호출할 때마다 새로운 문자열을 생성하는 replace()를 사용했습니다.
- 긴 재료 목록에서 시간 복잡도가 O(n²)에 가까워지게 되며 해당 코드는 시간 초과를 야기합니다.
두 번째 접근: Stack (O(n))
function solution(ingredient) {
const hamburger = '1231'
let answer = 0
return ingredient.reduce((a, c, i) => {
a.str.push(c)
if(a.str.slice(-4).join('') === hamburger) {
a.str.splice(-4, 4)
a.answer += 1
}
return a
}, {answer: 0, str: []}).answer
}
개선 사항
- 전체 문자열을 매번 검사하지 않고, 최근 추가된 4개의 재료만 확인합니다.
- 불필요한 문자열 변환과 검색 작업을 제거했습니다.
728x90
반응형
'자료구조 및 알고리즘 > JavaScript Practice' 카테고리의 다른 글
[프로그래머스] 숫자 짝꿍 (1) | 2025.01.01 |
---|---|
[프로그래머스] 체육복 (0) | 2024.12.31 |
[프로그래머스] 해시 - 완주하지 못한 선수 (0) | 2024.12.28 |
[프로그래머스] 로또의 최고 순위와 최저 순위 (0) | 2024.12.28 |
[프로그래머스] [1차] 다트 게임 (0) | 2024.12.26 |