첫 줄에 정수 n과 w, 둘째 줄에 질문 수 q, 셋째 줄에 조각 번호 q개가 주어진다.
1부터 n까지의 수를 차례로 빈칸 없이 이어 붙여 긴 숫자 띠를 만든다(n = 12이면 "123456789101112").
이 띠를 앞에서부터 w글자씩 잘라 조각을 만들고, 앞에서부터 1번, 2번, … 조각이라 부른다.
마지막 조각은 w글자보다 짧을 수 있다.
질문한 번호의 조각을 질문 순서대로 한 줄에 하나씩 출력하라.
12 5 3 3 1 2
01112 12345 67891
10 4 1 3
910
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
n이 100만이면 띠는 약 590만 글자라서, 이어 붙이는 방법에 따라 빠르기가 크게 달라요.
Java String·C# string은 바꿀 수 없는 값이라 s += x를 할 때마다 지금까지의 글자를 모두 복사한 새 문자열을 만들어요.
반복문 안에서 쓰면 O(n²)이라 시간 초과가 나요.
그래서 StringBuilder의 append/Append로 모아요.
Python 문자열도 바꿀 수 없는 값이에요.
CPython에는 +=를 빠르게 해 주는 최적화가 있지만 언어가 약속하는 동작은 아니어서, 조각을 모아 "".join(...)으로 잇는 것이 정석이에요.
JS·TS 엔진(V8)은 +=를 내부에서 조각을 이어 두는 방식으로 처리해서 빨라요.
배열에 모아 join("")해도 돼요.
C++ std::string의 +=는 뒤에 덧붙이기라 빠르지만, s = s + x는 매번 복사본을 만들어요.
C에는 문자열 타입이 없어요.strcat은 붙일 때마다 문자열 끝을 처음부터 찾아서 이것도 O(n²)이에요.sprintf가 돌려주는 글자 수로 끝 자리를 기억해 두고 거기에 바로 써요.
조각 번호는 1부터 세니 k번 조각은 (k - 1) * w번 글자(0부터)에서 시작해요.
크레이콘은 ribbon += i로 수를 문자열 뒤에 붙이고(JS 위에서 돌아서 빨라요), ribbon.부분문자열(시작, 개수)로 조각을 잘라요.
n, w = map(int, input().split())q = int(input())ks = list(map(int, input().split()))# 조각을 목록에 모았다가 join 한 번으로 잇는다ribbon = "".join(str(i) for i in range(1, n + 1))for k in ks: start = (k - 1) * w print(ribbon[start:start + w])const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, w] = lines[0].trim().split(/\s+/).map(Number);const ks = lines[2].trim().split(/\s+/).map(Number);const parts = [];for (let i = 1; i <= n; i++) parts.push(i);const ribbon = parts.join("");console.log(ks.map((k) => ribbon.slice((k - 1) * w, k * w)).join("\n"));import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, w]: number[] = lines[0].trim().split(/\s+/).map(Number);const ks: number[] = lines[2].trim().split(/\s+/).map(Number);const parts: number[] = [];for (let i = 1; i <= n; i++) parts.push(i);const ribbon: string = parts.join("");console.log(ks.map((k) => ribbon.slice((k - 1) * w, k * w)).join("\n"));import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int w = sc.nextInt(); int q = sc.nextInt(); // String += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다 StringBuilder ribbon = new StringBuilder(); for (int i = 1; i <= n; i++) ribbon.append(i); StringBuilder out = new StringBuilder(); for (int j = 0; j < q; j++) { int start = (sc.nextInt() - 1) * w; out.append(ribbon, start, Math.min(start + w, ribbon.length())).append('\n'); } System.out.print(out); }}using System;using System.Text; class Program{ static void Main() { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), w = int.Parse(t[1]); Console.ReadLine(); // string += 는 매번 새 문자열을 만든다 — StringBuilder 하나에 이어 붙인다 var ribbon = new StringBuilder(); for (int i = 1; i <= n; i++) ribbon.Append(i); string s = ribbon.ToString(); foreach (string k in Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)) { int start = (int.Parse(k) - 1) * w; Console.WriteLine(s.Substring(start, Math.Min(w, s.Length - start))); } }}#include <iostream>#include <string> int main() { int n, w, q, k; std::cin >> n >> w >> q; // std::string의 += 는 뒤에 덧붙인다(용량을 넉넉히 늘려 가서 빠르다) std::string ribbon; for (int i = 1; i <= n; i++) ribbon += std::to_string(i); for (int j = 0; j < q; j++) { std::cin >> k; std::cout << ribbon.substr(static_cast<std::size_t>(k - 1) * w, w) << '\n'; }}#include <stdio.h> static char ribbon[6000000]; int main(void) { int n, w, q, k; scanf("%d %d %d", &n, &w, &q); // 끝 자리(len)를 기억하며 그 뒤에 바로 쓴다 — strcat은 매번 처음부터 끝을 찾는다 int len = 0; for (int i = 1; i <= n; i++) len += sprintf(ribbon + len, "%d", i); for (int j = 0; j < q; j++) { scanf("%d", &k); int start = (k - 1) * w; int count = len - start < w ? len - start : w; printf("%.*s\n", count, ribbon + start); } return 0;}t = 콘솔.수들읽기();n = t[0];w = t[1];q = 콘솔.줄읽기().수로변환();ks = 콘솔.수들읽기();ribbon = "";반복 (i = 1; i <= n; i++){ ribbon += i;}각각 (k 에서 ks){ start = (k - 1) * w; 콘솔.쓰기(ribbon.부분문자열(start, 수학.작은수(w, ribbon.길이 - start)));}