•
•
문제 설명 : 주어진 규칙에 따라 문자열을 뒤집는다.
•
풀이 방법
◦
규칙이 상당히 복잡한데, 이 부분의 이해를 하는게 제일 오래 걸렸다. 2k 마다 문자를 끊어 범위를 만든 후 조건에 맞게 뒤집는 것이다.
1.
(문자열 시작 ~ 문자열 시작 + 2k) → 문자열 내 반복되는 대상 범위라고 하자.
2.
대상 범위(문자열 시작 ~ 문자열 시작 + 2k)의 길이가 K보다 작다면 대상 범위의 모든 문자열을 뒤집는다.
3.
대상 범위(문자열 시작 ~ 문자열 시작 + 2k)의 길이가 K보다 크고 2K보다 작다면 (문자열 시작 ~ 문자열 시작 + k)의 모든 문자열을 뒤집는다.
◦
여기서 중요한 점은, (문자열 시작 ~ 문자열 시작 + 2k) 범위로 자르다보면 [문자열 시작 + 2k]가 문자열 전체 길이를 초과할때가 있다.
◦
이때 위 2, 3번 조건이 동작하는 것이다.
◦
근데 결국에 조건을 하나씩 그려보면, (문자열 시작 ~ 문자열 시작 + k) 범위를 모두 뒤집어 버리면 되는 것이다.
▪
단, 다음 범위의 시작 위치는 (문자열 시작 + 2k)여야하는 것이다.
◦
그렇다는건, 만약 범위가 6글자라면 앞 3글자는 뒤집고 뒤 3글자는 냅둔다.
▪
다음 시작 위치는 6글자를 넘어간 7번째 글자부터이다.
•
시간복잡도 :
•
성공 코드
# O(N + N + N) -> O(N)
class Solution:
def reverseStr(self, s: str, k: int) -> str:
start, end = 0, 0
# O(N)
result = list(s)
# 탐색 범위의 시작 지점이 배열 내 범위 일 때
# 해당 while문은 배열을 1번만 순회하기 때문에 O(N)이다.
while start < len(s):
# 문제에 여러 조건이 있었지만, 결국에는 (탐색 범위 시작지점 ~ 탐색 범위 시작지점 + k) 범위를 뒤집으면 되는거다.
# 즉, 탐색 시작 부분이 0이라고 하면 아래와 같다. [인덱스 번호 기준]
# 0 ~ (k - 1) -> 뒤집음
# k ~ (2k - 1) -> 안뒤집음
end = start + k - 1 if start + k - 1 < len(s) else len(s) - 1
# 뒤집어야하는 갯수가 몇개인지 확인해서, 양쪽 끝을 swap 하는 방식으로 뒤집는다.
# 만약, 길이가 5라면 아래와 같다.
# 0, 4 swap -> 1, 3 swap -> 2는 그냥 둔다.
for i in range((end - start) // 2 + 1):
if end - i >= 0 and start + i >= 0:
result[end - i], result[start + i] = result[start + i], result[end - i]
# 탐색 시작 범위는 2k씩 이동
start += 2 * k
# O(N)
return ''.join(result)
Python
복사