지그재그 변환

난이도 중급
자주 묻는 질문 페이팔
끈조회수 34
링크드 인버퍼레딧텀블러

지그재그 변환 문제에서 우리는 현 길이 n의 s와 행 수를 나타내는 정수 r. r 행의 지그재그 패턴으로 주어진 문자열을 변환하고 문자를 행 방향으로 연결합니다. 새로 연결된 문자열을 인쇄합니다.

지그재그 변환핀

예

입력 : 

s =“TutorialCup”

R = 3

출력 : TrCuoilutap

입력 : 

s = "프로그래밍"

R = 4

출력 : 프람모리그

지그재그 변환에 대한 설명

문자열 s = "TutorialCup"및 행 수 즉, r = 3

지그재그 패턴을 형성하기 위해 r 크기의 문자열 배열 a []를 초기화합니다. 또한 정수 변수 행을 초기화하여 현재 행을 0으로 추적하고 부울 변수를 아래로 추적합니다.

문자열 탐색을 시작하고 다음과 같이 문자열 배열을 업데이트합니다. 아래는 위의 예에 대한 단계입니다.

  • 1 : 행 = 0, 아래 = 참, a [] = T
  • 2 : 행 = 1, 아래 = 참, a [] = T, u
  • 3 : 행 = 2, 아래 = 거짓, a [] = T, u, t
  • 4 : 행 = 1, 아래 = 참, a [] = T, uo, t
  • 5 : 행 = 0, 아래 = 참, a [] = Tr, uo, t
  • 6 : 행 = 1, 아래 = 참, a [] = Tr, uoi, t
  • 7 : 행 = 2, 아래 = 거짓, a [] = Tr, uoi, ta
  • 8 : 행 = 1, 아래 = 참, a [] = Tr, uoil, ta
  • 9 : 행 = 0, 아래 = 참, a [] = TrC, uoil, ta
  • 10 : 행 = 1, 아래 = 참, a [] = TrC, uoilu, ta
  • 11 : 행 = 2, 아래 = 거짓, a [] = TrC, uoilu, 탭

따라서 결과 문자열은 TrCuoilutap입니다.

지그재그 변환을위한 알고리즘

  1. 길이가 n 인 문자열 s와 행 수를 나타내는 정수 r을 초기화합니다.
  2. 주어진 행 수 (r)가 1이면 문자열을 반환합니다.
  3. 문자열 유형의 r 크기 배열을 만듭니다.
  4. 행을 0으로 초기화하고 부울 유형의 아래로.
  5. 0에서 n-1까지 순회하고 인덱스 행의 string 형 배열에 문자열의 문자를 저장합니다.
  6. 행이 r-1과 같은지 확인하십시오.
  7. 그렇지 않으면 행이 0이면 true로 업데이트됩니다.
  8. down이 true이면 행이 증가하고 그렇지 않으면 행이 감소합니다.
  9. 업데이트 된 문자열 배열을 인쇄합니다.

지그재그 변환을위한 C ++ 프로그램

#include<bits/stdc++.h> 
using namespace std; 
  
void ZigZag(string s, int r){ 
    
    if(r == 1){ 
        cout<<s;       
        return; 
    }    
  
    int n = s.length(); 
  
    string a[r]; 
  
    int row = 0; 
    bool down; 
    
    for(int i=0; i<n; ++i){ 
        
        a[row].push_back(s[i]); 
  
        if(row == r-1) 
          down = false; 
  
        else if (row == 0) 
          down = true; 
  
        (down)? (row++): (row--); 
    } 
  
    for(int i=0; i<r; ++i) 
        cout<<a[i]; 
} 

int main(){ 
    string s = "TutorialCup"; 
    int r = 3; 
    ZigZag(s, r); 
    return 0; 
}
TrCuoilutap

지그재그 변환을위한 Java 프로그램

import java.util.Arrays; 
  
class Concatenate{ 
  
    static void ZigZag(String s, int r){ 
  
        if(r == 1){ 
            System.out.print(s); 
            return; 
        } 
        
        char[] str = s.toCharArray(); 
  
        int n = s.length(); 
  
        String[] a = new String[r]; 
        Arrays.fill(a, ""); 
  
        int row = 0; 
        boolean down = true;
        
        for(int i=0; i<n; ++i){ 
            
            a[row] += (str[i]); 
  
            if(row == r-1){ 
                down = false; 
            }  
              
            else if(row == 0){ 
                down = true; 
            } 
  
            if(down){ 
                row++; 
            }  
            else{ 
                row--; 
            } 
        } 
  
        for(int i=0; i<r; ++i){ 
            System.out.print(a[i]); 
        } 
    } 
  
    public static void main(String[] args){
        
        String s = "TutorialCup"; 
        int r = 3; 
        ZigZag(s, r);
        
    } 
}
TrCuoilutap

지그재그 변환을위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 입력 문자열의 크기입니다.

보조 공간 : O (n)은 답을 계산하는 동안 배열 (문자열 유형)에 답을 저장하기 때문입니다.

참조

링크드 인버퍼레딧텀블러
Translate »