문제 76

문자열 회전시키기

태그 보기

구현

알파벳 소문자로 이루어진 문자열 $S$가 주어진다.

문자열의 맨 앞 문자를 맨 뒤로 옮기는 것을 문자열을 왼쪽으로 한 칸 회전한다고 하자.

문자열 $S$를 왼쪽으로 $0$칸, $1$칸, $\cdots$, $\lvert S \rvert-1$칸 회전한 문자열을 차례대로 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에 문자열 $S$가 주어진다. $(1 \le \lvert S \rvert \le 100)$

첫 번째 줄부터 $\lvert S \rvert$개의 줄에 걸쳐 문자열 $S$를 왼쪽으로 각각 $0, 1, \cdots, \lvert S \rvert-1$칸 회전한 문자열을 출력한다.

abcde

abcde
bcdea
cdeab
deabc
eabcd

문자열을 실제로 옮길 필요 없이 출력할 문자의 인덱스만 바꾸면 된다. 문자열 길이를 $L$이라 하자.

왼쪽으로 $k$칸 회전한 문자열의 $0$부터 센 $j$번째 문자는
\[ S_{(k+j)\bmod L} \]
이다. $S_k$부터 끝까지 읽은 다음 처음으로 돌아와 $S_{k-1}$까지 읽는 순서이기 때문이다.

$k=0,1,\cdots,L-1$에 대해 위 순서로 $L$글자를 한 줄씩 출력한다. 주기 때문에 같은 문자열이 다시 나오더라도 회전 횟수마다 출력한다.

출력량이 $L^2$글자이므로 시간복잡도는 $O(L^2)$, 입력 문자열을 저장하는 공간복잡도는 $O(L)$이다.

string에 입력을 저장하고 두 반복문으로 $k,j$를 순회하며 S[(k + j) % L]을 출력한다. 회전마다 문자열을 복사하거나 실제로 앞 문자를 지우지 않아도 된다.

시작점 k마다 S[(k+j)%L]을 j=0부터 L-1까지 출력한다. 회전 결과를 전부 저장할 필요는 없다. 같은 문자열이 생겨도 문제에서 요구한 L개 회전을 모두 출력한다.

k=0부터 len(S)-1까지 S[k:]+S[:k]를 출력한다. 한 번의 문자열 슬라이스 비용은 출력 길이와 같아 전체 $O(L^2)$에 맞는다. set으로 중복 회전을 제거하지 않는다.

각 k에서 charAt((k+j)%L)을 한 행의 StringBuilder에 넣어 출력한다. 회전 순서를 유지하고 동일한 문자열도 생략하지 않는다. 전체 회전을 담는 별도 배열은 필요 없다.

ASCII 문자열의 바이트 슬라이스 두 개를 BufWriter에 순서대로 쓴다. &s[k..] 다음 &s[..k]를 출력하면 문자 복사 없이 한 회전을 만든다. 모든 k를 순서대로 출력한다.

소문자 ASCII이므로 s.length는 글자 수와 같다. 회전량 $i$를 $0$부터 길이보다 작은 값까지 늘리며 s.slice(i) + s.slice(0, i)를 출력한다. 끝 인덱스가 제외되는 slice 규칙 덕분에 원래 순서와 길이를 보존한다.

const out = [];
for (let i = 0; i < s.length; i++)
    out.push(s.slice(i) + s.slice(0, i));
console.log(out.join('\n'));

문자열 길이가 $100$ 이하라 모든 출력 줄을 모아도 작다. 원형 큐나 별도 회전 클래스를 만들 필요는 없다. 출력량 자체가 $O(|S|^2)$이므로 복잡도도 이에 맞는다.

언어