문제 URL : https://leetcode.com/problems/zigzag-conversion/
ZigZag Conversion - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제접근법 :
시뮬레이션으로 접근하면되는데 지그재그 방향으로 동작하듯 그대로 구현합니다.
처음 아래로 numRows-1칸 만큼 움직이고 대각선으로 numRows-1칸만큼 움직이면서 2차원배열에 채워줍니다.
아래 그림과같이
그다음 이중for문으로 순서대로 채워진 문자만 string에 집어넣으면 끝인 문제입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
int dy[2] = { 1,-1 };
int dx[2] = { 0,1 };
class Solution {
public:
string convert(string s, int numRows) {
vector<vector<char>>board(numRows, vector<char>(s.size()));
if (numRows == 1)
return s;
int idx = 1;
string res;
int dir = 0;
int y = 0;
int x = 0;
int cnt = 0;
for (int i = 0; i < s.size(); i++) {
board[y][x] = s[i];
y += dy[dir];
x += dx[dir];
cnt++;
if (cnt == numRows - 1) {
dir = (dir + 1) % 2;
cnt = 0;
}
}
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < s.size(); j++) {
if (board[i][j]) {
res += board[i][j];
}
}
}
return res;
}
};
|
cs |
사실 이 코드는 시간복잡도와 공간복자도가 좋지 않은코드입니다. 둘다 O(n^2)에 해당하니까요
O(n)에 풀수있는코드는 해당사이트에 답지에 나와있으니 참고하시길 바랍니다.
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.
'LeetCode' 카테고리의 다른 글
| LeetCode 459 Repeated Substring Pattern (0) | 2021.07.31 |
|---|---|
| LeetCode 38 Count and Say (0) | 2021.07.15 |
| LeetCode 28 Implement strStr() (0) | 2021.07.06 |
| LeetCode 59 Spiral Matrix II (0) | 2021.02.10 |
| LeetCode #100 Same Tree (0) | 2021.01.06 |
