[JAVA] LeetCode - Zigzag Conversion - 6

문제내용

https://leetcode.com/problems/zigzag-conversion/

Zigzag Conversion - LeetCode

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

 

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

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

Example 3:

Input: s = "A", numRows = 1
Output: "A"

 

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

---

문제 접근 방법

이문제를 이해못하는 사람은 없을꺼라고 생각한다.. 그냥 문자열을 차례대로 읽으면서 써내려가는 방식이 지그재그일뿐,,

 

기본적으로 나는 문제를보고 각 문자를 저장시키기 위한 2차원 배열이 필요하다 생각했는데 행은 주어지지만 열을 주어지지 않기 때문에 인접리스트를 이용해서 풀었다.

그리고 규칙을 보면 첫시작은 무조건 세로로 문자를 넣어준 후에 문제에서 주어진 'numRows - 2' 만큼 대각선으로 문자를 써야한다는걸 알수 있다. 또한 문제에서 반환값은 1행~numRows행 까지 문자를 읽어서 반환하면 되는 문제니깐 굳이 문제에서 보여준것처럼 지그재그 모양이 되도록 할필요도 없다.

 

즉, 정리해보면 아래같은 과정을 구현하면 되는 문제이다.

 

1. 인접리스트 생성
   인접리스트를 선언하고 numRows 만큼의 방을 만들어준다.
2. 문자열 읽으면서 세로로 쓰기.
   문자를 처음부터 읽기 시작하고 int row=0; 을 활용해서 list에 문자를 넣어준다. 이때 row는 list의 행 인덱스로 활용한다.
   한마디로 if(row<numRows) 일때 list.get(row).add( 문자 ); 를 해주면된다.
3. 대각선으로 문자 쓰기.
   int zig = numRows-2; 와 int zigIdx = 1; 을 이용한다. zig는 대각선으로 문자를 써야하는 횟수를 나타내고 zigIdx는 list의 어느 행에 문자를 써야할지 알려주기위한 변수이다.
   따라서 if(zig>0) 일때 list.get(row-zigIdx-1).add( 문자 ); 를 해준다.
   
   
4. 반복
   2번과정으로 세로 한줄쓰고 3번 과정으로 대각선 문자를 썼다면
   다시 2번,3번을 순서대로 반복해주면 된다. 주어진 문자열이 끝날때까지!!

코드를 보고 생각하자.

 

---

풀이

import java.util.ArrayList;
public class Solution {
    public String convert(String s, int numRows) {
        ArrayList<ArrayList<Character>> list = new ArrayList<ArrayList<Character>>();
    	
        for(int i=0; i<numRows; i++) 
        	list.add(new ArrayList<Character>());
        
        int row = 0;//행
        int zig = numRows-2;//대각선으로 써야하는 횟수
        int zigIdx = 1;//대각선 문자를 어느행에 쓸지 알려줄 인덱스
        for(int i=0; i<s.length(); i++) {
        	char temp = s.charAt(i);
        	//세로와 대각선을 한번씩 다썼으면 인덱스와 횟수 처음으로 초기화
        	if(row>=numRows && zig<=0) {
        		row = 0;
        		zig = numRows-2;
        		zigIdx = 1;
        	}
        	//세로한줄 먼저쓰기
        	if(row<numRows) {
        		list.get(row).add(temp);
        		row++;
        		continue;
        	}
        	
        	//대각선으로 쓰기
        	if(zig>0) {
	        	list.get(row-zigIdx-1).add(temp);
	        	zig--;
	        	zigIdx++;
        	}
        }
        
        StringBuilder sb = new StringBuilder();//정답
        for(int i=0; i<list.size(); i++) {
        	for(int j=0; j<list.get(i).size(); j++) {
        		sb.append(list.get(i).get(j));
        	}
        }
        
    	return sb.toString();
    }
}

---

마치며

이 코드의 시간은 8ms 가 걸렸는데 토론방 가보면 더빠른 코드도 있다.

하지만 결국 인덱스를 어떻게 관리하냐 라는게 키포인트가 된다.