구슬 n개를 둥글게 꿴 목걸이가 있다.
구슬마다 영어 소문자 하나가 새겨져 있고, 목걸이 문자열 S의 i번째 글자가 i번째 구슬이다.
둥근 목걸이라 n번째 구슬 다음에는 다시 1번째 구슬이 온다.
목걸이에서 이어진 구슬 몇 개를 끊어 내어, 문자열 T에 있는 글자를 T에 나온 개수 이상씩 모두 가지려 한다.
끊어 내는 구슬은 어떤 구슬에서 시작해 번호가 커지는 쪽(n번째 다음은 1번째)으로 이어진 구슬들이며, 같은 구슬을 두 번 쓸 수는 없다.
끊어 내는 구슬의 수가 가장 적게 하라.
그런 방법이 여럿이면 시작하는 구슬의 번호가 가장 작은 것을 고른다.
시작하는 구슬의 번호와 끊어 내는 구슬의 수를 빈칸으로 나눠 한 줄에 출력하라.
어떻게 끊어도 안 되면 -1을 출력한다.
입력
첫 줄에 S, 둘째 줄에 T가 주어진다. 둘 다 영어 소문자로만 된 문자열이다. 1 ≤ S의 길이 n ≤ 100,000, 1 ≤ T의 길이 ≤ 100,000
출력
시작하는 구슬의 번호와 구슬의 수를 빈칸으로 나눠 한 줄에, 또는 -1
예시 1 · stdin
cabbad
dc
stdout
6 2
예시 2 · stdin
ab
aa
stdout
-1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
두 포인터(미는 창)로 풀어요: 오른쪽 끝을 하나씩 늘리며 글자마다 '더 있어야 하는 수'(need)를 줄이고, 모자란 구슬이 없어지면(missing == 0) 왼쪽 끝 구슬이 남아도는 동안 왼쪽을 당겨요. 두 끝 모두 앞으로만 가니 O(n)이에요. 둥근 목걸이는 두 바퀴를 이어 붙인 줄로 보면 돼요 — 자리 i의 구슬은 S[i % n]이라 문자열을 실제로 붙이지 않아도 돼요. 함정 하나: 두 바퀴로 보면서 창 길이를 n개로 막지 않으면 같은 구슬을 두 번 세요 — 둘째 예시 "ab"에서 "aba"는 a가 둘처럼 보이지만 구슬 a는 하나뿐이라 -1이에요. 함정 둘: 한 줄로만 보면 첫 예시처럼 마지막 구슬(d)과 첫 구슬(c)이 이어진 창(6번에서 시작해 2개)을 놓쳐요. 함정 셋: 길이가 같을 때 <=로 바꾸면 마지막에 찾은 창이 남아요 — 창은 시작이 앞선 차례로 나오니 <일 때만 바꿔요(시작 자리가 n 이상인 창은 앞 바퀴의 같은 창이라 빼요). 함정 넷: T의 글자 종류만 보면 틀려요 — "aab"는 a가 두 개 있어야 해요. 글자를 0~25 번호로 바꾸는 법이 언어마다 달라요: Python ord(ch) - 97, JavaScript·TypeScript s.charCodeAt(i) - 97, Java·C#·C·C++는 문자가 정수처럼 계산돼서 ch - 'a', 크레이콘은 s[i]가 한 글자 문자열이라 글자.코드(s[i]) - 97이에요. C는 scanf("%100001s", s)처럼 폭을 정해 읽고, 크레이콘은 콘솔.줄읽기().공백제거()로 줄을 받아요. 개수 표는 26칸이라 크레이콘 목록 한도와 상관없고, 문자열은 10,000,000글자까지라 100,000글자도 괜찮아요.
Pythonmain.py · 34 줄
import syslines = sys.stdin.read().split()s, t = lines[0], lines[1]n = len(s)need = [0] * 26 # 글자마다 더 있어야 하는 수for ch in t: need[ord(ch) - 97] += 1missing = len(t) # 창 안에서 아직 모자란 구슬 수(모두 더한 것)best_start, best_len = -1, n + 1left = 0# 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다)for right in range(2 * n - 1): c = ord(s[right % n]) - 97 if need[c] > 0: missing -= 1 need[c] -= 1 if right - left + 1 > n: # 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 d = ord(s[left % n]) - 97 need[d] += 1 if need[d] > 0: missing += 1 left += 1 if missing == 0: # 왼쪽 끝 구슬이 남아도는 동안 줄인다 while need[ord(s[left % n]) - 97] < 0: need[ord(s[left % n]) - 97] += 1 left += 1 if left < n and right - left + 1 < best_len: # 같은 길이면 먼저 찾은(시작이 앞선) 것 best_start, best_len = left, right - left + 1print(f"{best_start + 1} {best_len}" if best_start >= 0 else -1)
JavaScriptmain.js · 27 줄
const [s, t] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i) => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need = new Array(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
TypeScriptmain.ts · 29 줄
import { readFileSync } from "node:fs";const [s, t] = readFileSync(0, "utf8").trim().split(/\s+/);const n = s.length;const code = (i: number): number => s.charCodeAt(i % n) - 97; // 두 바퀴 붙인 줄의 i번째 구슬(0~25)const need: number[] = new Array<number>(26).fill(0); // 글자마다 더 있어야 하는 수for (const ch of t) need[ch.charCodeAt(0) - 97]++;let missing = t.length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)let bestStart = -1, bestLen = n + 1;let left = 0;for (let right = 0; right < 2 * n - 1; right++) { const c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 const d = code(left++); if (++need[d] > 0) missing++; } if (missing === 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } }}console.log(bestStart >= 0 ? `${bestStart + 1} ${bestLen}` : "-1");
JavaMain.java · 41 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String s = in.readLine().trim(); String t = in.readLine().trim(); int n = s.length(); int[] need = new int[26]; // 글자마다 더 있어야 하는 수 for (char ch : t.toCharArray()) need[ch - 'a']++; int missing = t.length(); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s.charAt(right % n) - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = s.charAt(left % n) - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s.charAt(left % n) - 'a'] < 0) { // 왼쪽 끝 구슬이 남아도는 동안 줄인다 need[s.charAt(left % n) - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } System.out.println(bestStart >= 0 ? (bestStart + 1) + " " + bestLen : "-1"); }}
C#Main.cs · 45 줄
using System;class Program{ static void Main() { string s = Console.ReadLine().Trim(); string t = Console.ReadLine().Trim(); int n = s.Length; var need = new int[26]; // 글자마다 더 있어야 하는 수 foreach (char ch in t) need[ch - 'a']++; int missing = t.Length; // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; // 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 { int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) // 왼쪽 끝 구슬이 남아도는 동안 줄인다 { need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < bestLen) // 같은 길이면 먼저 찾은(시작이 앞선) 것 { bestStart = left; bestLen = right - left + 1; } } } Console.WriteLine(bestStart >= 0 ? $"{bestStart + 1} {bestLen}" : "-1"); }}
C++main.cpp · 37 줄
#include <array>#include <iostream>#include <string>int main() { std::string s, t; std::cin >> s >> t; const int n = static_cast<int>(s.size()); auto code = [&](int i) { return s[i % n] - 'a'; }; // 두 바퀴 붙인 줄의 i번째 구슬(0~25) std::array<int, 26> need{}; // 글자마다 더 있어야 하는 수 for (char ch : t) need[ch - 'a']++; int missing = static_cast<int>(t.size()); // 창 안에서 아직 모자란 구슬 수(모두 더한 것) int bestStart = -1, bestLen = n + 1; int left = 0; for (int right = 0; right < 2 * n - 1; right++) { int c = code(right); if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { // 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 int d = code(left++); if (++need[d] > 0) missing++; } if (missing == 0) { while (need[code(left)] < 0) need[code(left++)]++; // 왼쪽 끝 구슬이 남아도는 동안 줄인다 if (left < n && right - left + 1 < bestLen) { // 같은 길이면 먼저 찾은(시작이 앞선) 것 bestStart = left; bestLen = right - left + 1; } } } if (bestStart >= 0) std::cout << bestStart + 1 << " " << bestLen << "\n"; else std::cout << -1 << "\n";}
Cmain.c · 44 줄
#include <stdio.h>#include <string.h>#define MAXL 100000static char s[MAXL + 2], t[MAXL + 2];int main(void) { scanf("%100001s %100001s", s, t); int n = (int)strlen(s), k = (int)strlen(t); int need[26] = {0}; /* 글자마다 더 있어야 하는 수 */ for (int i = 0; i < k; i++) need[t[i] - 'a']++; int missing = k; /* 창 안에서 아직 모자란 구슬 수(모두 더한 것) */ int best_start = -1, best_len = n + 1; int left = 0; /* 목걸이를 두 바퀴 붙여 놓은 줄에서 창 [left, right]를 민다(자리는 % n으로 돌린다) */ for (int right = 0; right < 2 * n - 1; right++) { int c = s[right % n] - 'a'; if (need[c] > 0) missing--; need[c]--; if (right - left + 1 > n) { /* 구슬 하나를 두 번 셀 수는 없다: 창은 n개까지 */ int d = s[left % n] - 'a'; left++; if (++need[d] > 0) missing++; } if (missing == 0) { while (need[s[left % n] - 'a'] < 0) { /* 왼쪽 끝 구슬이 남아도는 동안 줄인다 */ need[s[left % n] - 'a']++; left++; } if (left < n && right - left + 1 < best_len) { /* 같은 길이면 먼저 찾은(시작이 앞선) 것 */ best_start = left; best_len = right - left + 1; } } } if (best_start >= 0) printf("%d %d\n", best_start + 1, best_len); else puts("-1"); return 0;}
Craykonmain.cray · 60 줄
// 두 바퀴 붙인 줄의 i번째 구슬을 0~25 번호로구슬(s, i){ 돌려주기 글자.코드(s[i % s.길이]) - 97;}s = 콘솔.줄읽기().공백제거();t = 콘솔.줄읽기().공백제거();n = s.길이;need = 새목록(26, 0); // 글자마다 더 있어야 하는 수각각 (ch 에서 t){ need[글자.코드(ch) - 97] += 1;}missing = t.길이; // 창 안에서 아직 모자란 구슬 수(모두 더한 것)bestStart = -1;bestLen = n + 1;left = 0;반복 (right = 0; right < 2 * n - 1; right++){ c = 구슬(s, right); 만약 (need[c] > 0) { missing -= 1; } need[c] -= 1; 만약 (right - left + 1 > n) { d = 구슬(s, left); left += 1; need[d] += 1; 만약 (need[d] > 0) { missing += 1; } } 만약 (missing == 0) { 동안 (need[구슬(s, left)] < 0) { need[구슬(s, left)] += 1; left += 1; } 만약 (left < n && right - left + 1 < bestLen) { bestStart = left; bestLen = right - left + 1; } }}만약 (bestStart >= 0){ 콘솔.쓰기(bestStart + 1 + " " + bestLen);}아니면{ 콘솔.쓰기(-1);}