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]));}