읽기 전에 알아두면 좋아요
아래 개념이 익숙하면 본문을 바로 읽으세요. 낯선 개념만 링크에서 복습하면 됩니다.
- 슬라이딩 윈도우: 고정 길이 합과 양수 배열의 가변 구간슬라이딩 윈도우는 연속 구간에 새 값을 넣고 이전 값을 빼며 계산을 갱신합니다. 문자 빈도 Map의 증감과 고정 길이 창을 함께 유지합니다.
- JavaScript Map·Set: 값 조회와 중복 제거 실습Map은 이름표인 키로 값을 찾고, Set은 같은 값을 한 번만 보관합니다. 값의 존재 여부·빈도·중복을 Map과 Set으로 관리하는 방법입니다.
개념과 예제는 실행하지 않아도 읽을 수 있습니다. 내 컴퓨터·터미널에서 직접 실행하는 과정은 선택 실습입니다.
과정 위치와 선택 복습 안내
과정 위치: 구간과 탐색 · 문제
과정 위치는 이 글이 속한 묶음입니다. 이 단계의 모든 개념을 먼저 읽을 필요는 없습니다. 위에 연결한 개념 중 낯선 내용만 복습하세요. 문제의 조건·상태·갱신 순서는 익숙한 언어로 설명하면 됩니다.
JavaScript로 문법·실행 복습하기 (선택)
개념 글의 코드는 JavaScript 예시입니다. 문제 화면에서는 JavaScript·Python·Java·C++·C# 중 익숙한 언어의 함수를 작성하세요. 본문의 Node.js 입출력 예시는 로컬 실행을 위한 별도 안내입니다.
두 문자열이 주어지는 아나그램 찾기 문제는 어떤 연속 구간의 개수를 구하나요?
두 문자열을 입력받아 기준 문자열과 문자 구성이 같은 연속 구간의 개수를 구하는 문제입니다. 문자열·빈도·연속 구간의 기본을 준비하고, 아래 입력·반환 계약을 확인해 직접 풀어보세요.
적용 조건·범위: S와 T의 길이를 N과 M, 두 빈도표에 저장되는 문자 종류 수의 상한을 U라 하면 두 Map의 추가 공간은 O(U)입니다. 각 창을 별도 문자열이나 배열로 저장하지 않고, 답은 개수 숫자 하나라 O(1) 출력 공간입니다. 이미 전달된 S·T 문자열의 저장까지 포함하면 전체 공간은 O(N+M+U)입니다. 문자 종류가 작은 고정 범위라는 조건에서만 빈도표를 O(1) 공간으로 단순화할 수 있습니다.
공식 문서 참고: 관련 개념: MDN Map의 조회·갱신·삭제
문제
S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하는 문제입니다.
아나그램 판별 시 대소문자는 서로 다른 문자로 구분되며, 부분문자열은 반드시 연속된 문자열이어야 합니다.
첫 번째 줄에는 문자열 S가 주어지고, 두 번째 줄에는 문자열 T가 주어집니다.
S문자열의 길이는 최대 10,000을 넘지 않으며, T문자열의 길이는 S문자열의 길이보다 작거나 같습니다.
출력은 S단어 안에서 T문자열과 아나그램 관계가 되는 부분문자열의 총 개수를 출력해야 합니다.
예를 들어 S = “bacaAacba”, T = “abc”가 주어졌을 경우,
{bac}, {acb}, {cba} 총 3개의 부분문자열이 아나그램에 해당하므로 정답은 3이 됩니다.
원자료와 확인 범위
2026-10-12에 제공된 학습 자료 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬).pdf의 8쪽 ‘모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)’와 문제 조건·예제를 대조했습니다. 같은 ZIP의 해당 문제 TXT는 풀이 코드 자료입니다. 이 자료의 최초 출제 원문·저자·공개 배포 주소까지 확인한 것은 아닙니다.
이번 대조는 원자료의 문제 조건과 예제 확인입니다. 이 글의 전체 코드를 새로 실행하거나 공식 채점에 제출한 결과를 뜻하지 않습니다. 아래 예제·자가 확인 항목은 직접 실행해 기대 출력과 비교하는 기준입니다.
직접 풀어보기
먼저 선택한 언어의 입력·반환 계약에 맞춰 작성해 보세요. 힌트 받기와 정답과 비교하기는 코드를 실행하지 않는 AI 분석입니다. 해답·해설은 아래에서 필요할 때 펼칠 수 있습니다.
AI 힌트
코드를 실행한 채점 결과가 아닌 AI의 코드 분석입니다.
해답·해설 보기
function solution(s, t) {
const a = Array.from(s), b = Array.from(t);
if (b.length === 0 || b.length > a.length) return 0;
const need = new Map(), window = new Map();
for (const ch of b) need.set(ch,(need.get(ch) || 0) + 1);
let count = 0;
for (let i = 0; i < a.length; i++) {
window.set(a[i],(window.get(a[i]) || 0) + 1);
if (i >= b.length) {
const old = a[i - b.length], value = window.get(old) - 1;
if (value === 0) window.delete(old);
else window.set(old, value);
}
if (i < b.length - 1 || window.size !== need.size) continue;
let same = true;
for (const[ch, value] of need) if (window.get(ch) !== value) {
same = false;
break;
}
if (same) count++;
}
return count;
}
solution(s, t)에 s(문자열), t(문자열)를 전달하고 정수를 반환합니다. 아래 문제의 유효 입력 조건을 따릅니다. 표준 입력과 출력 코드는 작성하지 않습니다.
def solution(s, t):
if not t or len(t) > len(s):
return 0
need, window = {}, {}
for ch in t:
need[ch] = need.get(ch, 0) + 1
count = 0
for i, ch in enumerate(s):
window[ch] = window.get(ch, 0) + 1
if i >= len(t):
old = s[i-len(t)]
window[old] -= 1
if window[old] == 0:
del window[old]
if i >= len(t)-1 and window == need:
count += 1
return count
solution(s, t)에 s(문자열), t(문자열)를 전달하고 정수를 반환합니다. 아래 문제의 유효 입력 조건을 따릅니다. 표준 입력과 출력 코드는 작성하지 않습니다.
import java.util.*;
class Solution {
public int solution(String s, String t) {
int[] a = s.codePoints().toArray(), b = t.codePoints().toArray();
if (b.length == 0 || b.length > a.length) return 0;
Map < Integer, Integer > need = new HashMap < >(), window = new HashMap < >();
for (int ch : b) need.put(ch, need.getOrDefault(ch, 0) + 1);
int count = 0;
for (int i = 0; i < a.length; i++) {
window.put(a[i], window.getOrDefault(a[i], 0) + 1);
if (i >= b.length) {
int old = a[i - b.length], value = window.get(old) - 1;
if (value == 0) window.remove(old);
else window.put(old, value);
}
if (i >= b.length - 1 && window.equals(need)) count++;
}
return count;
}
}
Solution.solution(String s, String t)에 s(문자열), t(문자열)를 전달하고 정수를 반환합니다. 아래 문제의 유효 입력 조건을 따릅니다. 표준 입력과 출력 코드는 작성하지 않습니다.
#include <codecvt>
#include <locale>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <stdexcept>
int solution(const std::string & s, const std::string & t) {
// s와 t는 UTF-8 문자열입니다. C++17 기준입니다.
std::wstring_convert < std::codecvt_utf8 < char32_t >, char32_t > decoder;
auto a = decoder.from_bytes(s), b = decoder.from_bytes(t);
if (b.empty() || b.size() > a.size()) return 0;
std::map < char32_t, int > need, window;
for (char32_t ch : b) need[ch]++;
int count = 0;
for (size_t i = 0; i < a.size(); i++) {
window[a[i]]++;
if (i >= b.size()) {
char32_t old = a[i - b.size()];
if (-- window[old] == 0) window.erase(old);
}
if (i + 1 >= b.size() && window == need) count++;
}
return count;
}
solution(s, t)에 s(문자열), t(문자열)를 전달하고 정수를 반환합니다. 아래 문제의 유효 입력 조건을 따릅니다. 표준 입력과 출력 코드는 작성하지 않습니다. C++17, UTF-8 문자열 기준입니다.
using System;
using System.Collections.Generic;
public class Solution {
public int Solve(string s, string t) {
Func < string, List < int >> points = text => {
var result = new List < int >();
for (int i = 0; i < text.Length; i++) {
result.Add(char.ConvertToUtf32(text, i));
if (char.IsHighSurrogate(text[i])) i++;
}
return result;
};
var a = points(s);
var b = points(t);
if (b.Count == 0 || b.Count > a.Count) return 0;
var need = new Dictionary < int, int >();
var window = new Dictionary < int, int >();
foreach(int ch in b) {
if (! need.ContainsKey(ch)) need[ch] = 0;
need[ch]++;
}
int count = 0;
for (int i = 0; i < a.Count; i++) {
if (! window.ContainsKey(a[i])) window[a[i]] = 0;
window[a[i]]++;
if (i >= b.Count) {
int old = a[i - b.Count];
if (-- window[old] == 0) window.Remove(old);
}
if (i < b.Count - 1 || need.Count != window.Count) continue;
bool same = true;
foreach(var entry in need) {
int value;
if (! window.TryGetValue(entry.Key, out value) || value != entry.Value) {
same = false;
break;
}
}
if (same) count++;
}
return count;
}
}
Solution.Solve(string s, string t)에 s(문자열), t(문자열)를 전달하고 정수를 반환합니다. 아래 문제의 유효 입력 조건을 따릅니다. 표준 입력과 출력 코드는 작성하지 않습니다.
해설
처음 이 문제를 접했을 때, 직접적인 풀이를 떠올리지 못하고 접근 방법에서 막혔습니다.
문자열을 하나하나 잘라 비교하는 방식은 떠올릴 수 있었지만, 시간 복잡도 측면에서 적절한지 판단하기 어려웠습니다.
만약 S의 모든 부분 문자열을 생성해 정렬 후 비교한다면, 문자열 길이가 커질수록 연산량이 급격히 증가합니다.
따라서 이 문제는 단순 구현 문제가 아니라, 자료구조와 알고리즘 선택이 핵심인 문제입니다.
이 지점에서 해시(Map)를 사용해 문자 빈도를 관리하고, 슬라이딩 윈도우를 통해 연속된 구간을 효율적으로 이동시키는 접근이 필요해집니다.
풀이
먼저 문제의 전체 해답 코드를 한 번에 확인한 뒤, 아래에서 단계별 코드와 함께 흐름을 나누어 설명합니다.
한 줄씩 따라가며 이해할 수 있도록 실제 코딩테스트 풀이 순서에 맞게 구성했습니다.
function compareMaps(map1, map2) {
if (map1.size !== map2.size) return false;
for (let [key, val] of map1) {
if (!map2.has(key) || map2.get(key) !== val) return false;
}
return true;
}
function solution(s, t) {
let answer = 0;
let tH = new Map();
let sH = new Map();
for (let x of t) {
tH.set(x, (tH.get(x) || 0) + 1);
}
let len = t.length - 1;
for (let i = 0; i < len; i++) {
sH.set(s[i], (sH.get(s[i]) || 0) + 1);
}
let lt = 0;
for (let rt = len; rt < s.length; rt++) {
sH.set(s[rt], (sH.get(s[rt]) || 0) + 1);
if (compareMaps(sH, tH)) answer++;
sH.set(s[lt], sH.get(s[lt]) - 1);
if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
lt++;
}
return answer;
}
1단계는 기준이 되는 문자열 T의 문자 빈도를 해시(Map)로 만드는 과정입니다.
이후 모든 비교는 이 해시를 기준으로 이루어집니다.
let tH = new Map();
for (let x of t) {
tH.set(x, (tH.get(x) || 0) + 1);
}
아나그램 판별은 문자 종류와 개수가 완전히 같아야 하므로,
문자열 자체가 아니라 빈도 구조를 저장하는 것이 핵심입니다.
2단계는 슬라이딩 윈도우를 시작하기 전, S 문자열에서 미리 윈도우 크기만큼 해시를 구성하는 과정입니다.
윈도우 크기는 항상 T의 길이와 같아야 합니다.
let sH = new Map();
let len = t.length - 1;
for (let i = 0; i < len; i++) {
sH.set(s[i], (sH.get(s[i]) || 0) + 1);
}
이렇게 하면 이후 오른쪽 포인터가 이동할 때마다,
정확히 길이가 T인 구간을 유지할 수 있습니다.
3단계부터 실제 슬라이딩 윈도우가 시작됩니다.
오른쪽 포인터를 이동시키며 새로운 문자를 해시에 추가합니다.
let lt = 0;
for (let rt = len; rt < s.length; rt++) {
sH.set(s[rt], (sH.get(s[rt]) || 0) + 1);
if (compareMaps(sH, tH)) answer++;
sH.set(s[lt], sH.get(s[lt]) - 1);
if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
lt++;
}
이 구간에서 가장 중요한 포인트는 두 가지입니다.
첫째, 해시 비교는 항상 윈도우 크기가 동일할 때만 수행됩니다.
둘째, 왼쪽 포인터에서 빠지는 문자는 반드시 정리해 주어야 합니다.
특히 빈도가 0이 된 문자를 삭제하지 않으면,
해시 크기 비교에서 오답이 발생할 수 있으므로 반드시 처리해야 합니다.
빈도표와 입력·출력 공간
S와 T의 길이를 N과 M, 두 빈도표에 저장되는 문자 종류 수의 상한을 U라 하면 두 Map의 추가 공간은 O(U)입니다. 각 창을 별도 문자열이나 배열로 저장하지 않고, 답은 개수 숫자 하나라 O(1) 출력 공간입니다. 이미 전달된 S·T 문자열의 저장까지 포함하면 전체 공간은 O(N+M+U)입니다. 문자 종류가 작은 고정 범위라는 조건에서만 빈도표를 O(1) 공간으로 단순화할 수 있습니다.
정리
이 문제는 아나그램이라는 개념보다, 연속된 부분 문자열을 어떻게 효율적으로 검사할 것인지가 핵심입니다.
해시와 슬라이딩 윈도우를 함께 사용하면 시간 복잡도를 크게 줄일 수 있으며,
문자열 관련 문제에서 매우 자주 활용되는 패턴입니다.
해시 빈도 집계 풀이를 더 짧게 점검하려면 JavaScript 해시 Map 학급 회장를 먼저 확인해보세요.
슬라이딩 윈도우 풀이 흐름을 더 연습하려면 JavaScript 최대 매출 슬라이딩 윈도우처럼 고정 길이 구간을 다루는 문제와 함께 보면 좋습니다.
QnA
Q. 왜 문자열을 정렬해서 비교하면 안 되나요?
정렬 방식은 구현은 쉽지만, 매번 정렬이 발생해 시간 복잡도가 크게 증가합니다. 이 문제의 입력 크기에서는 비효율적입니다.
Q. Map 대신 객체를 사용해도 되나요?
가능하지만, 키의 개수 관리와 비교 측면에서는 Map이 더 명확하고 안전합니다.
Q. 이 패턴은 어디에 또 사용되나요?
부분 문자열, 연속 구간 합, 빈도 비교 문제 등에서 거의 동일한 구조로 반복 등장합니다.
Q. 면접에서 이 문제를 설명하라고 하면 어떻게 말해야 하나요?
해시로 문자 빈도를 관리하고, 슬라이딩 윈도우로 연속 구간을 유지하며 비교했다고 설명하면 됩니다.
Q. 시간 복잡도는 어떻게 되나요?
S 길이를 N, T 길이를 M, 비교하는 문자 종류 수 상한을 U라 하면 평균 상수 시간 Map 접근 모델에서 O(M + N×U)입니다. U가 고정된 작은 문자집합일 때만 O(N+M)로 단순화할 수 있습니다.
Q. 대소문자 조건은 왜 중요한가요?
문자 자체를 키로 사용하기 때문에 대소문자 구분 여부가 결과에 직접적인 영향을 줍니다.
과정 마무리 실습
이미 푼 문제 한 개를 해설 없이 다시 풀고 경계 입력 세 개를 추가하세요.
완료 기준: 예상 출력과 실제 출력을 비교하고 시간 복잡도 및 다른 풀이의 장단점을 설명합니다.
이어서 공부할 과정: 자료구조 첫 글
이 문제를 푼 뒤 확인하기
길이가 같은 서로 다른 배열의 문자 빈도와 중복 문자가 들어간 창의 빈도 변화를 비교해 보세요.
본문의 예제와 이 반례를 직접 실행해 예상 출력과 비교하고, 결과가 다르면 입력 조건과 반복 범위를 다시 확인하세요.
풀이 함수를 독립 실행해 확인합니다
선수 지식은 배열·조건문·반복문과 위에서 설명한 자료구조입니다. 풀이의 완성 함수 블록 하나를 solution.cjs로 저장하고, 그 아래에 다음 호출을 붙입니다. 앞의 비교용 풀이와 같은 이름의 함수를 함께 붙이지 않습니다. 터미널에서 node solution.cjs로 실행합니다.
console.log(JSON.stringify(solution(...["abcd", "aa"])));이 변형 호출의 기대 JSON 출력은 0입니다. 기존 함수 블록의 console.log가 있으면 그 출력 다음 줄에서 확인합니다.
완성 블록의 compareMaps와 solution을 함께 저장해야 합니다. 여기서는 비어 있지 않은 영문 문자열을 실습합니다. 현재 코드의 T 순회와 S 인덱스 접근은 이모지 등 서로게이트 쌍에 대해 같은 문자 단위를 사용하지 않으므로 일반 유니코드 문자열용 구현으로 간주하지 않습니다.
이 글이 도움이 되었나요?
이어서 공부하기
체크포인트: 해설을 가리고 다시 풀고, 경계 입력을 하나 바꾸어 예상 결과와 실제 결과를 비교하세요. 포인터를 움직여도 답을 버리지 않는 이유와 양수·0·음수의 차이를 설명하세요.
다음 추천 · 알고리즘 개념: 이진 탐색의 불변식: 탐색 구간·중간값·종료 조건
권장 순서는 학습 가이드와 같습니다. 다른 순서는 접힌 참고 목록에서 확인할 수 있습니다. 읽음 표시는 숙달이나 채점 결과가 아닙니다.
원래 과정 목록 순서 (선택)
읽음 기록
읽음 — / 전체 58개 · 필수 58개
새 글 받아보기
RSS 리더에서 BlogFlow의 새 글을 확인할 수 있습니다.
