해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 34일차(20241130) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.
문제 출처) https://school.programmers.co.kr/learn/courses/30/lessons/133502
문제해결에 활용한 핵심포인트!
이 문제에서 주목해야할 부분은 다음과 같다.
1. 주요조건
-
아래서부터, 빵 – 야채 – 고기 - 빵으로 쌓인 햄버거만 포장을 한다.
-
예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.
=> 결국 조건에 맞는 재료구성이면 햄버거를 포장하고, 나머지 재료들 중 또 조건과 순서에 맞는 재료 구성이면 햄버거를 포장하는 구조이다.
2. 입력
-
재료의 정보를 나타내는 정수 배열 ingredient (단, 1 ≤ ingredient의 길이 ≤ 1,000,000)
-
ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미한다.
3. 출력
- 상수가 포장하는 햄버거의 개수를 return
풀이방향
(1) 어떤 구조가 풀이에 적합할지 고려한다.
-
특정 패턴을 탐색한 후, 재탐색을 이어나간다는 것에 초점을 두었다.
-
특정 패턴을 찾아 이를 제거하면, 나머지 앞뒤끼리 자동으로 붙는 배열같은 구조가 뭐일지 생각했다.
=> StringBuilder 클래스 활용
=> 특정 인덱스범위로 패턴 검색(sb.substring(idx1, idx2))도 가능
=> 동적배열이어서, 특정 인덱스 범위로 패턴 제거(sb.delete(idx1, idx2)시, 남은 앞뒤끼리 자동으로 붙어 패턴의 재탐색에 유리하다고 생각했다.
(2) 반복문 종류 결정 및 실행 조건 고려
-
특정 패턴 검색 후 재탐색이 핵심이므로, for문 대신 while문을 선택하였다.
=> 인덱스 i가 sb.length() - 4 일 때까지 진행 (찾고 있는 패턴길이가 4이므로) -
인덱스 i를 활용하되, 특정 패턴 발견 후, 이를 제거하면 i-3으로 돌려 재탐색을 진행한다.
=> "i-3"의 의미 : 현재 인덱스(i)까지 포함해서 i-3~i까지는 특정패턴이 발견되지 않은 상태였다.
=> 특정 패턴을 발견해서 지웠으므로, 이제 "i에서 3개 이전 ~ i이후 1개 패턴"이 우리가 찾는 패턴인지 부터 다시 탐색을 시작해야한다.
=> 단, 인덱스는 기본적으로 0이상이어야하므로, i = Math.max(0, i-3)을 통해 i를 다시 설정하고 반복문을 진행시킨다. -
패턴을 발견하지 못하면 i++을 통해 다음 루프로 진행한다.
