문제 이해하기
문자열 s와 정수 k가 주어졌을 때, 문자열의 각 문자를 대각선 방향으로 왼쪽 위에서 오른쪽 아래로 이동하며 배치하다가 k번째 줄에 도달하면 다시 오른쪽 위 방향으로 올라가는 방식으로 새로운 문자열을 만들어야 합니다. 즉, 문자를 지그재그(zigzag) 형태로 배치한 결과를 구하는 것이 목표입니다.
예를 들어 입력이 s = "ilovepythonprogramming", k = 5라면 출력은 다음과 같습니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 각 줄별로 문자를 저장할 맵(line)을 하나 생성합니다.
- 현재 줄을 나타내는 cnt를 0으로, 이동 방향을 나타내는 delta를 1로 초기화합니다.
- 문자열 s의 각 인덱스 i와 문자 c에 대해 다음을 반복합니다.
- line[cnt]의 끝에 (c, i) 쌍을 추가합니다.
- cnt를 delta만큼 증가시킵니다.
- cnt가 k와 같아지면 delta를 -1로 바꾸고 cnt를 k - 2로 설정합니다.
- cnt가 0이 되면 delta를 다시 1로 설정합니다.
- 결과를 담을 리스트 ans를 생성합니다.
- line의 각 키 i와 값 c에 대해 다음을 수행합니다.
- 문자열 길이와 같은 크기의 리스트 prefix를 만들고 공백으로 채웁니다.
- c의 각 쌍 (x, y)에 대해 prefix[y] = x로 문자를 배치합니다.
- prefix의 요소들을 하나의 문자열로 연결하여 ans에 추가합니다.
- 마지막으로 ans의 연속된 요소 사이에 개행 문자를 넣어 하나의 문자열로 합친 뒤 반환합니다.
구현 예제
아래 코드를 통해 더 자세히 이해할 수 있습니다.
from collections import defaultdict
class Solution:
def solve(self, s, k):
line = defaultdict(list)
cnt = 0
delta = 1
for i, c in enumerate(s):
line[cnt].append((c, i))
cnt += delta
if cnt == k:
delta = -1
cnt = k - 2
if cnt == 0:
delta = 1
ans = []
for i, c in line.items():
prefix = [" "] * (len(s))
for x, y in c:
prefix[y] = x
ans.append("".join(prefix))
return "\n".join(ans)
ob = Solution()
s = "ilovepythonprogramming"
k = 5
print(ob.solve(s, k))입력
"ilovepythonprogramming", 5
출력