[Java] LeetCode 6. Zigzag Conversion

[Java] LeetCode 6. Zigzag Conversion

 

문   제 : 

문자열 s와 행의 개수 numRows가 주어진다.

문자열 s를 지그재그로 놓았을 때, 그걸 다시 가로로 봤을 때 어떤 문자열이 나오는지 구하여라.

 

{ 1 <= s.length <= 1000 }

{ 1 <= numRows <= 1000 }

 

 

Example )

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation:
P   A   H   N
A P L S I I G
Y   I   R

//////////////////////////////////////////////////////////

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

 

---

접   근 : 

numRows만큼 문자열을 생성하고, 문자열 s를 순서대로 맞는 위치에 위치 시킨 다음

생성시킨 문자열들을 다 연결한다.

---

해   결 : 

예외처리 - 만약 주어진 행이 한 줄이라면, 지그재그가 되지 않는다.

 

numRows만큼 문자열을 생성하고, 초기화해준다. -> str[]

s에 주어진 문자열들을 한 글자씩 접근한다.

한 글자 한 글자가 str 배열중 어디에 들어갈 지 정해야한다.

 

flag를 만들어서 글자가 다음 어디 str 배열에 들어가야하는지 방향을 알려준다.

만약 flag == true 일 경우,   행 번호는 올라간다.

만약 flag == false 일 경우,  행 번호는 내려간다.

 

numRows만큼 만들어진 행 들에, 각 끝 행들에 도달하면 flag를 바꿔주면 되는 방식이다.

각 끝 행들을 구하는 점화식은 다음과 같다.

 

i 는 문자열 s에서 떼 온 글자의 번호이다.

윗 줄 끝 행 : 

i % ((numRows-1) * 2) == 0

 

아랫 줄 끝 행 :  

i % ((numRows-1) * 2) == numRows-1

 

그리고 나서 index위치에 해당 글자를 삽입해주면 된다.

 

---

 

만약 주어진 행이 한 줄이라면, 지그재그가 되지 않는다.

if(numRows == 1) return s;

 

---

 

str 배열 생성 및 초기화

 

String[] str = new String[numRows];
Arrays.fill(str, "");
// str[0] = "P A H N"
// str[1] = "APLSIIG"
// str[2] = "Y I R"

 

 

---

플래그에 따라 글자가 들어갈 행의 번호가 정해지는 부분

if(flag == true && (0 <= index-1 && index-1 < numRows)){ // up
    index--;
}
else if(flag == false && (0 <= index+1 && index+1 < numRows)){ // down
    index++;
}

---

결   과  :

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) return s;
        
        String[] str = new String[numRows];
        Arrays.fill(str, "");
        // str[0] = "P A H N"
        // str[1] = "APLSIIG"
        // str[2] = "Y I R"

        int index = -1, min=0, max=numRows;
        boolean flag = false; // false = down, true = up
        // flag = down (false) -> 행 번호 증가
        // flag = up  (true)   -> 행 번호 감소

        // i = 순서, index = 들어갈 줄 번호
        for(int i=0; i<s.length(); i++){
            String insert = s.substring(i, i+1);
            if(flag == true && (0 <= index-1 && index-1 < numRows)) // up
                index--;
            else if(flag == false && (0 <= index+1 && index+1 < numRows)) // down
                index++;
            ///// flag change
            if(i != 0 && i % ((numRows-1) * 2) == 0) // 맨 윗줄일 경우
                flag = false;
            else if(i != 0 && i % ((numRows-1) * 2) == numRows-1 ) // 맨 아래줄일 경우
                flag = true;
            // 위치 삽입
            str[index] += insert;
        }

        String res = "";
        for(int i=0; i<str.length; i++)
            res += str[i];
        return res;
    }
}