📘 TIL — 슬라이딩 윈도우 문제 풀이 & 웨이브 조기 종료 보상 페이즈 처리
코딩 테스트 — 할인 행사 문제 풀이 (슬라이딩 윈도우)
문제
XYZ 마트에서는 10일 동안 회원 할인이 적용되며 하루에 하나의 할인 품목만 구매할 수 있다.
정현이는 자신이 원하는 상품과 수량이 연속된 10일 동안의 할인 목록과 정확히 일치하는 시작 날짜에 회원가입하려 한다.
주어지는 정보
want: 원하는 상품 목록number: 각 상품의 필요한 수량discount: 날짜별 할인 상품
목표
- 연속된 10일 구간에서 원하는 상품과 수량이 정확히 일치하는 시작 날짜의 개수를 구하는 것
제약 조건
discount최대 길이 : 100,000want최대 길이 : 10number합 : 10
초기 접근
처음에는 다음과 같은 방식으로 접근하였다.
want에 있는 각 상품에 대해discount에서 해당 상품이 등장하는 날짜 인덱스 목록을 저장- 각 상품의 인덱스 리스트를 기준으로
- 10일 범위 안에 포함되는 날짜만 남기며 검사
- 필요한 수량과 일치하면 카운트
문제점 분석
이 접근 방식에는 몇 가지 문제가 있었다.
시작 날짜 기준 판단이 어려움
문제의 핵심은 다음과 같은 연속 구간 검사이다.
discount[s] ~ discount[s+9]하지만 상품 등장 날짜 기준으로 접근하면
- 시작일 기준 구간 판단이 어려워지고
- 여러 상품의 날짜 리스트를 교집합처럼 맞춰야 하는 구조가 된다.
멀티셋(상품 개수) 처리 복잡
예를 들어
banana 3
apple 2같은 경우 단순히 등장 여부가 아니라
10일 구간 안에서 정확한 개수를 만족해야 한다.
날짜 리스트 방식은 개수 관리가 매우 복잡해지는 문제가 있었다.
구현 대비 성능 이득 없음
discount 최대 길이는
100000하지만 검사 대상은 10일 구간이다.
따라서
100000 * 10 = 1,000,000정도의 연산이면 충분하다.
즉 복잡한 구조 없이도 해결 가능하다.
해결 방법
이 문제는 슬라이딩 윈도우 + 빈도 맵 패턴으로 해결할 수 있다.
핵심 아이디어
연속된 10일 구간을 하나의 윈도우로 유지윈도우를 한 칸씩 이동시키면서
빠지는 상품 제거
새로 들어오는 상품 추가하여 현재 구간의 상품 개수를 관리한다.
알고리즘 흐름
원하는 상품 정보 저장
need[상품] = 필요한 개수현재 윈도우 상품 개수 관리
cur[상품] = 현재 할인 구간에 등장한 개수첫 10일 초기화
discount[0] ~ discount[9]구간의 상품 개수를 cur에 기록
윈도우 이동
다음 날짜로 이동할 때
discount[i-10] 제거
discount[i] 추가조건 검사
모든 want 상품에 대해
cur[item] == need[item]이면 조건 만족
시간 복잡도
윈도우 이동
O(N)검사
O(want)최종
O(N * want)최대 연산량
100000 * 10 = 1,000,000충분히 빠르게 해결 가능하다.
구현 코드
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(vector<string> want, vector<int> number, vector<string> discount) {
int answer = 0;
unordered_map<string, int> need;
for (int i = 0; i < want.size(); i++) {
need[want[i]] = number[i];
}
unordered_map<string, int> cur;
auto add = [&](const string& item, int delta) {
int next = (cur.count(item) ? cur[item] : 0) + delta;
if (next == 0) cur.erase(item);
else cur[item] = next;
};
auto isMatch = [&]() {
for (int i = 0; i < want.size(); i++) {
int have = cur.count(want[i]) ? cur[want[i]] : 0;
if (have != need[want[i]]) return false;
}
return true;
};
if (discount.size() < 10) return 0;
for (int i = 0; i < 10; i++) {
add(discount[i], 1);
}
if (isMatch()) answer++;
for (int i = 10; i < discount.size(); i++) {
add(discount[i - 10], -1);
add(discount[i], 1);
if (isMatch()) answer++;
}
return answer;
}코딩 테스트 패턴 정리
다음과 같은 키워드가 등장하면 슬라이딩 윈도우를 먼저 고려하는 것이 좋다.
연속 구간
k일
부분 배열
고정 길이 구간고정 길이 구간 문제에서는
- 구현 단순화
- 시간 복잡도 감소
- 안정적인 성능
을 얻을 수 있다.
몬스터 웨이브 조기 종료 시 보상 페이즈 스킵 문제
문제
몬스터 웨이브를 모두 처치했을 때 Night 페이즈가 끝나기를 기다리지 않고 즉시 보상 페이즈(Dawn)로 이동하도록 기능을 추가하였다.
구현 방식
- 몬스터 스포너에서 웨이브 종료 시 Delegate 발생
- GameMode에서 Delegate 수신
- DayNightCycle을 강제로 Dawn으로 이동
하지만 테스트 과정에서 보상 페이즈가 표시되지 않고 바로 Day 페이즈로 넘어가는 문제가 발생하였다.
결과 패널이나 보상 UI가 나타나기 전에 페이즈가 넘어가 보상 페이즈가 스킵된 것처럼 보이는 현상이 발생하였다.
분석
DayNightCycle의 구조를 확인한 결과 각 페이즈는 다음과 같은 방식으로 동작하고 있었다.
EnterX()
→ OnXStarted.Broadcast()
→ SetTimer()로 다음 페이즈 예약예시
EnterDawn()
{
OnDawnStarted.Broadcast();
SetTimer(... EnterDay ...);
}즉 Dawn에 진입하면 자동으로 Day로 넘어가는 타이머가 예약되는 구조였다.
문제 발생 흐름
- 몬스터 스포너가 웨이브 종료 감지
- Delegate로 GameMode에 알림
- GameMode에서
ForceToDawn()호출 EnterDawn()실행- DawnDuration이 짧아 바로 EnterDay() 실행
결과적으로 보상 UI가 표시되기 전에 Day 페이즈로 넘어가면서 보상 페이즈가 스킵된 것처럼 보였다.
해결
기존 DayNightCycle의 자동 진행 구조를 유지하는 방식으로 해결하였다.
수정 내용
- Dawn 페이즈에 별도의 Hold 로직을 추가하지 않음
- DawnDuration 값을 충분히 늘려 보상 페이즈 유지 시간 확보
- 몬스터 스포너에서 웨이브 종료 Delegate 전달
- GameMode에서 Dawn 강제 진입 처리
void APotatoGameMode::HandleRoundFinished(int32 Round)
{
if (Round != CurrentDay) return;
if (DayNightSystem)
{
DayNightSystem->ForceToDawn(true);
}
}결과
시스템 흐름이 다음과 같이 개선되었다.
몬스터 전멸
→ 웨이브 종료 Delegate
→ GameMode 수신
→ Dawn 페이즈 강제 진입
→ DawnDuration 동안 보상 UI 표시
→ 이후 자동으로 Day 페이즈 진행이를 통해
- 몬스터 웨이브 종료 시 즉시 보상 페이즈로 이동
- 보상 UI가 정상적으로 표시
- 기존 DayNightCycle 자동 페이즈 구조 유지
라는 세 가지 목표를 모두 만족할 수 있었다.
