본문 바로가기

Algorithm

[leetcode] Zigzag Conversion (swift)

문제

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. 1번째 줄, 마지막(N)번째 줄 

1번째 줄과 마지막 N번째 줄은 항상 (numRows-1) * 2 만큼의 index를 건너띕니다. numRows = 4라고 한다면 1번째 줄은 0 다음 index는 0 + 6 = 6 이 됩니다. 마지막번째 줄인 4번째 줄도 마찬가지입니다. 

2. 첫번째와 마지막번째 사이의 줄 (2 ~ N-1)

지그재그는 아래로 내려갈 때와 위로 올라갈 때 2가지 케이스가 있고 모두 고려해야 합니다. 이 때 규칙은 아래와 같습니다.

1번째 줄의 index 간격을 K라고 한다면, i번째 줄의 index는 내려갈 때, (K - 2*i)만큼의 간격이고 올라갈 때, (2*i)만큼의 간격을 가집니다. 

 

풀이 코드

Runtime 116ms | Memory 14.6 MB