Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 n행 지그재그 문자열 연결 출력하기

문제 개요

이 문제에서는 문자 시퀀스로 이루어진 하나의 문자열과 지그재그 패턴의 행 수(n)가 주어집니다. 우리가 해야 할 일은 주어진 문자열을 n개의 행으로 이루어진 지그재그 형태로 배치한 뒤, 각 행을 위에서부터 순서대로 이어 붙인 최종 문자열을 출력하는 것입니다.

개념을 더 잘 이해하기 위해 몇 가지 예시를 살펴보겠습니다.

예시 1

입력 : string = 'STUVWXYZ', n = 2
출력 : SUWYTVXZ

설명 − 2행 지그재그 패턴은 다음과 같습니다.

S     U     W     Y
   T     V     X     Z

이 지그재그 패턴을 행 단위로 이어 붙이면 SUWYTVXZ가 됩니다.

예시 2

입력 : string = 'ABCDEFGH', n = 3
출력 : AEBDFHCG

설명 − 3행 지그재그 패턴은 다음과 같습니다.

A       E
  B   D   F   H
    C   G

이 지그재그 패턴을 이어 붙이면 AEBDFHCG가 됩니다.

접근 방법

문제를 파악했으니 이제 해결 방법을 설계해 보겠습니다. 핵심 아이디어는 문자열을 처음부터 끝까지 순회하면서, 현재 행이 맨 아래 행(n-1)에 도달하면 진행 방향을 위쪽으로 바꾸고, 다시 맨 위 행(0)에 도달하면 방향을 아래쪽으로 되돌리는 것입니다. 각 문자를 자신이 속한 행의 문자열에 추가한 뒤, 마지막에 0번 행부터 n-1번 행까지 차례대로 출력하면 원하는 결과를 얻을 수 있습니다.

이 개념을 바탕으로 문제를 해결하는 알고리즘을 도출해 보겠습니다.

알고리즘

1단계 : 크기가 n인 문자열 배열 arr[n], 현재 행 번호를 나타내는 row,
        그리고 방향을 나타내는 direction(1은 아래쪽 이동을 의미)을 초기화합니다.
2단계 : 문자열의 모든 문자에 대해 3~7단계를 반복 수행합니다.
3단계 : row 값을 기준으로 현재 문자를 배열의 해당 문자열에 추가합니다.
4단계 : row == n-1이면 direction = -1로 설정합니다.
5단계 : row == 0이면 direction = 1로 설정합니다.
6단계 : direction == 1이면 row++ 합니다.
7단계 : 그렇지 않으면 row-- 합니다.
8단계 : 배열의 0번부터 n-1번까지의 문자열을 순서대로 출력합니다.

구현 예제

위 알고리즘을 바탕으로 솔루션을 구현한 C++ 프로그램입니다 −

#include<bits/stdc++.h>
using namespace std;
void ZigZagConcatenationString(string str, int n){
    if (n == 1){
        cout << str;
        return;
    }
    int len = str.length();
    string arr[n];
    int row = 0;
    int direction = 1;
    for (int i = 0; i < len; ++i){
        arr[row].push_back(str[i]);
        if (row == n-1)
            direction = -1;
        else if (row == 0)
            direction = 1;
        (direction == 1)? (row++): (row--);
    }
    for (int i = 0; i < n; ++i)
        cout << arr[i];
}
int main(){
    string str = "ABCDEFGH";
    int n = 3;
    ZigZagConcatenationString(str, n);
    return 0;
}

출력

AEBDFHCG

복잡도 분석

이 알고리즘은 문자열을 정확히 한 번만 순회하므로 시간 복잡도는 O(L)입니다(여기서 L은 문자열의 길이). 공간 복잡도 역시 각 행의 문자를 저장하기 위해 추가 배열을 사용하므로 O(L)입니다. 또한 n이 1인 경우에는 지그재그 배치 없이 원본 문자열 그대로가 결과가 되므로, 코드에서 이 경우를 별도로 처리하여 불필요한 연산을 줄였습니다.