모든 배지가 짝수 번 나온 가장 긴 구간
자바스크립트 코딩테스트 문제로 parity-mask 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
배지 기록 문자열 badges가 주어질 때, A, B, C, D, E 다섯 종류의 배지가 모두 짝수 번 등장하는 가장 긴 연속 구간의 길이를 구하는 longestEvenBadgeWindow 함수를 작성하세요.
배지가 어떤 종류는 한 번도 등장하지 않아도 됩니다. 0번도 짝수로 취급합니다.
제한사항
badges는 길이 0 이상 200,000 이하의 문자열입니다.badges의 각 문자는"A","B","C","D","E"중 하나입니다.- 반환값은 조건을 만족하는 가장 긴 연속 부분 문자열의 길이입니다.
- 조건을 만족하는 구간이 없으면
0을 반환합니다.
예시
- 입력:
"AABBCC"→ 출력:6 - 입력:
"ABCDE"→ 출력:0 - 입력:
"ABCDAEBCDE"→ 출력:10 - 입력:
"AAAA"→ 출력:4
힌트
- 각 배지의 개수를 정확히 세기보다, 홀수인지 짝수인지만 알면 됩니다.
A~E의 홀짝 상태를 5비트 정수 하나로 표현할 수 있습니다.- 어떤 두 위치까지의 홀짝 상태가 같다면, 그 사이 구간에서는 각 배지의 등장 횟수가 모두 짝수 번 바뀐 것입니다.
해설
이 문제의 핵심은 누적 홀짝 상태(prefix parity) 입니다.
문자를 왼쪽부터 읽으면서 A~E의 등장 횟수가 홀수인지 짝수인지만 관리합니다.
예를 들어:
A가 홀수면 1번 비트 ONB가 홀수면 2번 비트 ON- …
- 짝수면 해당 비트 OFF
이렇게 하면 현재까지의 상태를 길이 5의 비트마스크 하나로 표현할 수 있습니다.
어떤 인덱스 i와 j (i < j)에서 누적 마스크가 같다면,
i + 1부터 j까지의 구간에서는 각 배지의 홀짝 변화가 모두 상쇄됩니다.
즉, 그 구간 안에서는 A~E가 모두 짝수 번 등장합니다.
따라서 풀이 순서는 다음과 같습니다.
- 현재 마스크를
0으로 시작합니다. - 마스크
0이 인덱스-1에서 처음 나왔다고 기록합니다. - 문자열을 한 번 순회하며 현재 문자에 해당하는 비트를 토글합니다.
- 지금 마스크를 예전에 본 적이 있다면, 그 첫 위치와 현재 위치 사이 길이로 정답을 갱신합니다.
- 처음 보는 마스크라면 현재 위치를 저장합니다.
예를 들어 "ABCDAEBCDE"를 끝까지 읽으면 마지막 마스크가 다시 0이 됩니다.
초기 위치 -1과 현재 위치 9 사이 전체 길이 10이 조건을 만족하므로 정답은 10입니다.
이 방식은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이고, 가능한 마스크 수는 2^5 = 32개뿐이라 매우 효율적입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.