구슬을 한 줄로 꿰는 도안이 있다. 구슬의 색은 영어 소문자 한 글자로 적는다.
도안은 조각을 하나 이상 빈칸 없이 이어 쓴 것이다. 조각은 구슬 하나이거나 묶음이다.
묶음은 k(도안) 꼴로 적으며, 괄호 안의 도안을 k번 되풀이해서 꿴다는 뜻이다.
예를 들어 a2(bc)대로 꿰면 abcbc가 되고, 2(a2(b))대로 꿰면 abbabb가 된다.
도안마다 두 글자 xy가 함께 주어진다. 도안대로 다 꿴 줄에서 x색 구슬 바로 다음에 y색 구슬이 오는 자리가 몇 군데인지 구한다.
첫 줄에 도안의 수 t가 주어진다.
다음 t줄에 한 줄에 하나씩 두 글자 xy와 도안이 빈칸 하나로 띄워 주어진다.
도안마다 자리의 수를 한 줄에 하나씩 출력한다.
입력
1 ≤ t ≤ 20. x와 y는 영어 소문자이고 서로 같을 수도 있다. 도안 길이의 합은 100,000 이하. k는 1 이상 10^9 이하의 정수이고 0으로 시작하지 않는다. 괄호 안의 도안은 비어 있지 않다. 묶음이 겹친 깊이는 3,000 이하. 다 꿴 줄의 구슬은 10^15개 이하
출력
도안마다 x 바로 다음에 y가 오는 자리의 수를 한 줄에 하나씩
예시 1 · stdin
5
ba 3(ab)
ab a2(b)
ab 2(ca)b
ba 2(3(a)b)
aa 12(a)
stdout
2
1
1
1
11
예시 2 · stdin
2
ab 1000000(1000000(ab))
xy 3(x2(y))
stdout
1000000000000
3
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
다 꿴 줄의 구슬이 10^15개까지라서, 도안을 실제로 펼쳐 놓고 세는 것은 어느 언어로도 끝나지 않아요. 대신 묶음마다 세 가지만 기억해요. 안에서 센 자리의 수, 첫 구슬, 끝 구슬이에요. (를 만나면 지금까지 읽던 것을 스택에 넣고 새로 시작하고, )를 만나면 스택에서 꺼내 합쳐요. 안쪽 묶음이 k번 되풀이되면 자리의 수는 k배가 되고, 끝 구슬이 x이고 첫 구슬이 y이면 되풀이 사이의 이음매 k - 1곳이 더해져요. 스택은 Python은 리스트에 튜플을 append·pop하고, JS는 배열에 push·pop해요. TS는 stack.pop()의 타입이 Frame | undefined라서 그대로 쓰면 타입 오류(TS18048)가 나고, as Frame으로 알려 줘야 해요. Java는 ArrayDeque<long[]>의 push·pop, C#은 튜플을 담은 Stack<...>의 Push·Pop을 써요. C는 구조체 배열과 꼭대기 번호 top으로 직접 만들어요. C++의 std::stack은 pop()이 값을 돌려주지 않아서 top()으로 먼저 읽고 pop()해요. 크레이콘은 목록 네 개에 넣기로 쌓고, 맨 뒤 값을 읽은 다음 자리빼기로 빼요. 답이 10^15 가까이 될 수 있어서 Java·C#은 long, C·C++은 long long에 담아요. JS·TS의 number와 크레이콘의 수는 이 범위에서 정확하고, Python의 정수는 크기 제한이 없어요. 함정 하나: 되풀이 사이의 이음매를 빼먹으면 안 돼요. ba 3(ab)는 ababab라서 2인데 0이 나와요. 함정 둘: 묶음 바로 앞의 구슬과 묶음의 첫 구슬도 이웃이에요. ab a2(b)는 abb라서 1인데, 세지 않으면 0이 나와요. 함정 셋: 묶음을 닫으면 끝 구슬은 그 묶음의 끝 구슬이 돼요. 바꾸지 않으면 ab 2(ca)b(cacab)가 1이 아니라 0이 돼요. 함정 넷: 묶음이 묶음으로 시작하면 안쪽 묶음의 첫 구슬이 바깥 묶음의 첫 구슬이에요. 넘겨주지 않으면 ba 2(3(a)b)(aaabaaab)가 1이 아니라 0이 돼요. 함정 다섯: 횟수는 여러 자리일 수 있어요. 마지막 숫자만 남기면 aa 12(a)가 11이 아니라 1이 돼요. 함정 여섯: Java에서 자리의 수를 int에 담으면 둘째 예시의 첫 줄이 1000000000000이 아니라 -727379968이 돼요. 함정 일곱: Python에서 스택 대신 묶음마다 함수를 다시 부르면, 3,000겹으로 겹친 도안에서 RecursionError로 죽어요. 예시에는 드러나지 않아요. 함정 여덟: 크레이콘에서 묶음을 횟수만큼 실제로 되풀이해 읽으면 둘째 예시의 첫 줄에서 '너무 오래 걸려서'라는 말과 함께 멈춰요.
Pythonmain.py · 46 줄
import sysdef count_pairs(x, y, design): """다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수""" stack = [] # 바깥 묶음들: (자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수) count, first, last = 0, "", "" # 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" times = 0 for ch in design: if ch.isdigit(): times = times * 10 + int(ch) elif ch == "(": stack.append((count, first, last, times)) count, first, last, times = 0, "", "", 0 elif ch == ")": in_count, in_first, in_last = count, first, last count, first, last, k = stack.pop() total = in_count * k if in_last == x and in_first == y: # 되풀이 사이의 이음매 k - 1곳 total += k - 1 if last == x and in_first == y: # 묶음 앞 구슬과 묶음의 첫 구슬 사이 total += 1 count += total if first == "": first = in_first last = in_last else: if last == x and ch == y: count += 1 if first == "": first = ch last = ch return countdef main(): lines = sys.stdin.read().split("\n") t = int(lines[0]) out = [] for line in lines[1:t + 1]: pair, design = line.split() out.append(str(count_pairs(pair[0], pair[1], design))) print("\n".join(out))main()
JavaScriptmain.js · 40 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x, y, design) { const stack = []; // 바깥 묶음들: [자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수] let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push([count, first, last, times]); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop(); count = outer[0]; first = outer[1]; last = outer[2]; const k = outer[3]; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
TypeScriptmain.ts · 49 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");// 바깥 묶음 하나: 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수interface Frame { count: number; first: string; last: string; times: number;}// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수function countPairs(x: string, y: string, design: string): number { const stack: Frame[] = []; let count = 0, first = "", last = ""; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 "" let times = 0; for (const ch of design) { if (ch >= "0" && ch <= "9") { times = times * 10 + Number(ch); } else if (ch === "(") { stack.push({ count, first, last, times }); count = 0; first = ""; last = ""; times = 0; } else if (ch === ")") { const inCount = count, inFirst = first, inLast = last; const outer = stack.pop() as Frame; // 도안이 올바르므로 스택은 비어 있지 않다 count = outer.count; first = outer.first; last = outer.last; const k = outer.times; let total = inCount * k; // 10^15 이하라서 number로 정확하다 if (inLast === x && inFirst === y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last === x && inFirst === y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first === "") first = inFirst; last = inLast; } else { if (last === x && ch === y) count += 1; if (first === "") first = ch; last = ch; } } return count;}const t = Number(lines[0]);const out: number[] = [];for (let i = 1; i <= t; i++) { const [pair, design] = lines[i].trim().split(" "); out.push(countPairs(pair[0], pair[1], design));}console.log(out.join("\n"));
JavaMain.java · 49 줄
import java.io.*;import java.util.*;public class Main { // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long countPairs(char x, char y, String design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 0 ArrayDeque<long[]> stack = new ArrayDeque<>(); // {자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수} long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; i < design.length(); i++) { char ch = design.charAt(i); if (Character.isDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push(new long[]{count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long[] outer = stack.pop(); count = outer[0]; first = (char) outer[1]; last = (char) outer[2]; long k = outer[3]; long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine().trim()); StringBuilder sb = new StringBuilder(); for (int i = 0; i < t; i++) { String[] parts = br.readLine().trim().split(" "); sb.append(countPairs(parts[0].charAt(0), parts[0].charAt(1), parts[1])).append('\n'); } System.out.print(sb); }}
C#Main.cs · 59 줄
using System;using System.Collections.Generic;using System.Text;class Program{ // 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 static long CountPairs(char x, char y, string design) { // 바깥 묶음들을 쌓아 두는 스택. 구슬이 아직 없으면 첫 구슬과 끝 구슬은 '\0' var stack = new Stack<(long count, char first, char last, long times)>(); long count = 0, times = 0; char first = '\0', last = '\0'; foreach (char ch in design) { if (char.IsDigit(ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.Push((count, first, last, times)); count = 0; first = '\0'; last = '\0'; times = 0; } else if (ch == ')') { long inCount = count; char inFirst = first, inLast = last; long k; (count, first, last, k) = stack.Pop(); long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == '\0') first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == '\0') first = ch; last = ch; } } return count; } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int i = 0; i < t; i++) { string[] parts = Console.ReadLine()!.Trim().Split(' '); sb.Append(CountPairs(parts[0][0], parts[0][1], parts[1])).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 57 줄
#include <cctype>#include <iostream>#include <stack>#include <string>// 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0struct Frame { long long count; char first, last; long long times;};// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수long long countPairs(char x, char y, const std::string& design) { std::stack<Frame> stack; long long count = 0, times = 0; char first = 0, last = 0; for (char ch : design) { if (std::isdigit(static_cast<unsigned char>(ch))) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack.push({count, first, last, times}); count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long inCount = count; char inFirst = first, inLast = last; Frame outer = stack.top(); // top()은 보기만 하고, 꺼내는 것은 pop()이다 stack.pop(); count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = inCount * k; // int로는 넘친다 if (inLast == x && inFirst == y) total += k - 1; // 되풀이 사이의 이음매 k - 1곳 if (last == x && inFirst == y) total += 1; // 묶음 앞 구슬과 묶음의 첫 구슬 사이 count += total; if (first == 0) first = inFirst; last = inLast; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; for (int i = 0; i < t; i++) { std::string pair, design; std::cin >> pair >> design; std::cout << countPairs(pair[0], pair[1], design) << "\n"; } return 0;}
Cmain.c · 59 줄
#include <stdio.h>#include <ctype.h>#define MAX_LEN 100000#define MAX_DEPTH 3000/* 바깥 묶음 하나. 구슬이 아직 없으면 first와 last는 0 */typedef struct { long long count; char first, last; long long times;} Frame;static char design[MAX_LEN + 2];static Frame stack[MAX_DEPTH];/* 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수 */static long long count_pairs(char x, char y, const char *s) { int top = 0; long long count = 0, times = 0; char first = 0, last = 0; for (int i = 0; s[i] != '\0'; i++) { char ch = s[i]; if (isdigit((unsigned char)ch)) { times = times * 10 + (ch - '0'); } else if (ch == '(') { stack[top++] = (Frame){count, first, last, times}; count = 0; first = 0; last = 0; times = 0; } else if (ch == ')') { long long in_count = count; char in_first = first, in_last = last; Frame outer = stack[--top]; count = outer.count; first = outer.first; last = outer.last; long long k = outer.times; long long total = in_count * k; /* int로는 넘친다 */ if (in_last == x && in_first == y) total += k - 1; /* 되풀이 사이의 이음매 k - 1곳 */ if (last == x && in_first == y) total += 1; /* 묶음 앞 구슬과 묶음의 첫 구슬 사이 */ count += total; if (first == 0) first = in_first; last = in_last; } else { if (last == x && ch == y) count += 1; if (first == 0) first = ch; last = ch; } } return count;}int main(void) { int t; char pair[4]; if (scanf("%d", &t) != 1) return 1; for (int i = 0; i < t; i++) { if (scanf("%3s %100000s", pair, design) != 2) return 1; printf("%lld\n", count_pairs(pair[0], pair[1], design)); } return 0;}
Craykonmain.cray · 81 줄
// 다 꿴 줄에서 x 바로 다음에 y가 오는 자리의 수자리세기(x, y, 도안){ // 바깥 묶음들을 쌓아 두는 스택. 묶음마다 자리 수, 첫 구슬, 끝 구슬, 되풀이 횟수 쌓은수 = []; 쌓은첫 = []; 쌓은끝 = []; 쌓은횟수 = []; 수 = 0; // 지금 읽고 있는 묶음. 구슬이 아직 없으면 첫과 끝은 "" 첫 = ""; 끝 = ""; 횟수 = 0; 각각 (ch 에서 도안) { 만약 (ch >= "0" && ch <= "9") { 횟수 = 횟수 * 10 + ch.수로변환(); } 아니면 만약 (ch == "(") { 쌓은수.넣기(수); 쌓은첫.넣기(첫); 쌓은끝.넣기(끝); 쌓은횟수.넣기(횟수); 수 = 0; 첫 = ""; 끝 = ""; 횟수 = 0; } 아니면 만약 (ch == ")") { 안수 = 수; 안첫 = 첫; 안끝 = 끝; 위 = 쌓은수.개수 - 1; // 스택의 맨 위에서 바깥 묶음을 꺼낸다 수 = 쌓은수[위]; 첫 = 쌓은첫[위]; 끝 = 쌓은끝[위]; k = 쌓은횟수[위]; 쌓은수.자리빼기(위); 쌓은첫.자리빼기(위); 쌓은끝.자리빼기(위); 쌓은횟수.자리빼기(위); 모두 = 안수 * k; 만약 (안끝 == x && 안첫 == y) { 모두 += k - 1; } 만약 (끝 == x && 안첫 == y) { 모두 += 1; } 수 += 모두; 만약 (첫 == "") { 첫 = 안첫; } 끝 = 안끝; } 아니면 { 만약 (끝 == x && ch == y) { 수 += 1; } 만약 (첫 == "") { 첫 = ch; } 끝 = ch; } } 돌려주기 수;}t = 콘솔.줄읽기().수로변환();반복 (i = 0; i < t; i++){ parts = 콘솔.줄읽기().공백제거().나누기(" "); 콘솔.쓰기(자리세기(parts[0][0], parts[0][1], parts[1]));}