문제
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);
풀이
$jmp=2\times \text{numRows}-2$의 주기로 반복되는 규칙이 생긴다는 것을 캐치하자.
그러면 줄별로 주기가 $jmp$가 되고, 규칙에 맞게 순서대로 출력을 하면 끝난다.
첫줄과 마지막 줄은 $jmp$마다 1개씩, 나머지 줄은 2개씩 포함된다는 것을 캐치한다면 나머지는 구현.
Time Complexity : $O(n)$
코드
class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1) return s;
string ret;
int l=s.size(), jmp = 2*numRows-2;
for(int i=0;i<numRows;i++)
{
for(int j=0;j+i<l; j+=jmp)
{
ret += s[j+i];
if(i!=0 && i!= numRows-1 && j+jmp-i<l) ret+=s[j+jmp-i];
}
}
return ret;
}
};
'PS > leetcode' 카테고리의 다른 글
[leetcode] 8. String to Integer (atoi) (0) | 2019.04.28 |
---|---|
[leetcode] 7. Reverse Integer (0) | 2019.04.28 |
[leetcode] 5. Longest Palindromic Substring (0) | 2019.04.28 |
[leetcode] 4. Median of Two Sorted Arrays (0) | 2019.04.28 |
[leetcode] 3. Longest Substring Without Repeating Characters (0) | 2019.04.28 |