Reverse a String

Q: 문자열을 뒤집는 시간 복잡도는 얼마인가요?

뒤집기에는 O(n) 시간이 걸립니다. 모든 문자를 새 위치로 옮겨야 하고 각 문자를 한 번씩 처리하기 때문입니다. 새 문자열을 만들면 O(n) 의 추가 공간이 필요합니다. 문자가 이미 변경 가능한 배열에 있다면 두 포인터를 사용해 교환할 때는 O(1) 의 추가 공간만 필요합니다.

Q: 내장된 reverse 함수 없이 문자열을 어떻게 뒤집나요?

문자들을 배열에 복사하고, 양쪽 끝에 포인터를 하나씩 놓은 다음, 두 문자를 서로 바꾸고 포인터가 만날 때까지 서로를 향해 이동합니다. 또는 마지막 인덱스부터 첫 번째 인덱스까지 반복하며 각 문자를 빌더에 추가합니다. 두 방법 모두 한 번의 순회로 문자열을 뒤집습니다.

Q: 문자열을 제자리에서 뒤집을 수 있나요?

문자가 C, Java 또는 C#의 char 배열, Python의 리스트 또는 C++의 std::string 과 같은 변경 가능한 버퍼에 있을 때만 가능합니다. Java, Python, JavaScript 및 기타 여러 언어의 문자열은 변경할 수 없으므로, 문자열을 배열에 복사한 다음 배열 안에서 문자를 서로 바꾸고 새 문자열을 만듭니다. 어느 경우든 문자 교환 단계 자체는 제자리에서 수행됩니다.

Q: 두 포인터 루프는 왜 중간에서 멈추나요?

각 교환은 두 문자를 최종 위치에 놓으므로, n / 2 번 교환한 후에는 모든 문자가 제자리에 있게 됩니다. 중간을 지나 계속하면 같은 문자 쌍을 다시 교환하여 작업을 되돌리게 됩니다. 길이가 홀수일 때는 가운데 문자가 이미 자신의 대칭 인덱스에 있으므로 교환할 필요가 없습니다.

입문배열과 문자열 투 포인터

+10

영문자와 숫자로 이루어진 문자열 s가 주어집니다. 문자의 순서를 거꾸로 바꾼 새 문자열을 반환하세요. 즉, 마지막 문자가 맨 앞에 오고 첫 번째 문자가 맨 뒤에 오도록 하세요. 대소문자를 포함해 모든 문자를 있는 그대로 유지하세요.

함수

reverseString(s: string) → string

sstring: 뒤집을 문자열
반환값string: s의 문자를 역순으로

제약 조건

1 ≤ s.length ≤ 10⁴
s에는 영문자(a부터 z까지, A부터 Z까지)와 숫자(0부터 9까지)만 포함됩니다.

예제

입력: s = "Coddy2026"
출력: "6202yddoC"
설명: Coddy2026을 마지막 문자부터 첫 번째 문자까지 읽어 보세요: 6, 2, 0, 2, 그다음 y, d, d, o, 그리고 마지막으로 대문자 C.

입력: s = "noon"
출력: "noon"
설명: noon은 회문이므로, 뒤집어도 같은 단어입니다. 바깥쪽 n들이 서로 자리를 바꾸고, 그다음 두 o가 서로 자리를 바꿉니다.

제출 시 숨은 테스트 +14개

후속 질문

문장에 있는 단어의 순서를 어떻게 뒤집어 hello big world를 world big hello로 바꾸면서 각 단어의 글자 순서는 그대로 유지할 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

모든 문자는 고정된 목적지가 있습니다. 인덱스 i에 있는 문자는 인덱스 n-1-i에 있어야 합니다. 문자를 그 순서대로 새 문자열에 쓸 수도 있고, 양쪽 끝에서부터 쌍을 이루어 서로 바꿀 수도 있습니다. 면접관이 묻는 방식은 서로 바꾸는 방법입니다. 같은 두 포인터 이동 방식으로 배열을 제자리에서 뒤집고 회문인지 확인할 수 있기 때문입니다.

뒤에서 문자를 복사하세요

핵심 아이디어

s의 역순은 s의 마지막 문자로 시작해 끝에서 두 번째 문자로 이어지고 첫 번째 문자로 끝납니다. 따라서 인덱스를 n-1에서 0까지 거꾸로 이동하면서 각 문자를 만날 때마다 답에 추가하세요. Coddy2026의 경우 6, 2, 0, 2, y 등을 추가하면 6202yddoC이 됩니다.

각 문자는 한 번 읽고 한 번 쓰므로 작업량은 O(n)입니다. 답은 n개의 문자로 이루어진 두 번째 문자열이므로 추가 공간은 O(n)입니다.

문자를 추가하는 방법이 중요합니다. 불변 문자열에 +를 사용해 문자 하나를 추가하면 매번 전체 문자열이 복사됩니다. 따라서 n = 10^4일 때 약 5 × 10^7개의 문자가 복사됩니다. 문자를 리스트나 문자열 빌더에 모은 다음 마지막에 한 번만 결합하세요.

알고리즘

답을 위한 빈 리스트 또는 문자열 빌더를 만듭니다.
i를 n-1부터 0까지 거꾸로 반복합니다.
답에 s[i]를 추가합니다.
답을 문자열로 결합하여 반환합니다.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

양쪽 끝에서 두 개의 포인터로 교환하기

핵심 아이디어

뒤집기는 바깥쪽에서 안쪽으로 문자를 짝지어 진행합니다. 첫 번째 문자와 마지막 문자의 위치를 바꾸고, 그다음 두 번째 문자와 끝에서 두 번째 문자의 위치를 바꾸는 식으로 가운데를 향해 나아갑니다. 인덱스 0에 포인터 left를 놓고 인덱스 n-1에 포인터 right를 놓은 뒤, 두 문자의 위치를 바꾸고 두 포인터를 안쪽으로 한 칸씩 이동합니다.

포인터가 만나거나 서로 교차하면 멈춥니다. noon에서는 포인터가 0과 3에서 시작해 1과 2로 이동한 다음, 두 번 위치를 바꾸고 나면 서로 교차합니다. xYz처럼 길이가 홀수인 경우 포인터는 가운데 문자에서 만나는데, 이 문자는 이미 최종 위치에 있으므로 건드리지 않습니다. 위치를 바꿀 때마다 두 문자가 최종 위치에 놓이므로 n / 2번 위치를 바꾸면 작업이 끝납니다.

위치를 바꾸는 데는 임시 변수 하나만 필요하므로 추가 공간은 O(1)입니다. 대부분의 언어에서는 문자열을 제자리에서 변경할 수 없으므로 먼저 문자열을 문자 배열로 복사해야 하며, 이때 O(n)의 비용이 듭니다. 입력이 이미 문자 배열인 면접 상황에서는 이 방법으로 추가 메모리를 전혀 사용하지 않고 배열을 뒤집을 수 있습니다.

알고리즘

s를 문자 배열로 복사합니다.
left = 0과 right = n-1을 설정합니다.
left < right인 동안 left와 right 위치의 문자를 서로 바꾼 다음, left에 1을 더하고 right에서 1을 뺍니다.
배열을 다시 문자열로 변환하여 반환합니다.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

함정과 경계 사례

뒤집기는 한 줄로 끝나는 것처럼 보이지만, 버그는 반복문의 경계 조건과 결과를 만드는 방식에 숨어 있습니다.

left를 n-1까지 반복합니다. 중간 지점을 지나면 각 쌍이 두 번째로 교환되어 문자열이 원래대로 돌아옵니다. left < right에서 멈추세요.
역방향 반복문을 n-1 대신 n에서 시작하면 끝을 넘어선 위치를 읽게 됩니다. 대신 Lua와 R에서는 인덱스가 1부터 n까지입니다.
변경할 수 없는 문자열에서 result = result + ch로 결과를 만듭니다. 매 단계마다 지금까지의 내용을 모두 복사하므로, 긴 입력에서는 선형 작업이 이차 작업으로 바뀝니다.
C에서 종료 문자 '\0'를 빠뜨립니다. n바이트 버퍼는 한 바이트 부족하므로 n + 1을 할당하세요.
임시 변수 없이 교환합니다. chars[left] = chars[right]를 실행한 뒤에는 기존 왼쪽 문자가 사라집니다. 단, 사용하는 언어가 두 값을 한 번에 교환하는 경우는 예외입니다.

자주 묻는 질문4

문자열을 뒤집는 시간 복잡도는 얼마인가요?

뒤집기에는 O(n) 시간이 걸립니다. 모든 문자를 새 위치로 옮겨야 하고 각 문자를 한 번씩 처리하기 때문입니다. 새 문자열을 만들면 O(n)의 추가 공간이 필요합니다. 문자가 이미 변경 가능한 배열에 있다면 두 포인터를 사용해 교환할 때는 O(1)의 추가 공간만 필요합니다.

내장된 reverse 함수 없이 문자열을 어떻게 뒤집나요?

문자들을 배열에 복사하고, 양쪽 끝에 포인터를 하나씩 놓은 다음, 두 문자를 서로 바꾸고 포인터가 만날 때까지 서로를 향해 이동합니다. 또는 마지막 인덱스부터 첫 번째 인덱스까지 반복하며 각 문자를 빌더에 추가합니다. 두 방법 모두 한 번의 순회로 문자열을 뒤집습니다.

문자열을 제자리에서 뒤집을 수 있나요?

문자가 C, Java 또는 C#의 char 배열, Python의 리스트 또는 C++의 std::string과 같은 변경 가능한 버퍼에 있을 때만 가능합니다. Java, Python, JavaScript 및 기타 여러 언어의 문자열은 변경할 수 없으므로, 문자열을 배열에 복사한 다음 배열 안에서 문자를 서로 바꾸고 새 문자열을 만듭니다. 어느 경우든 문자 교환 단계 자체는 제자리에서 수행됩니다.

두 포인터 루프는 왜 중간에서 멈추나요?

각 교환은 두 문자를 최종 위치에 놓으므로, n / 2번 교환한 후에는 모든 문자가 제자리에 있게 됩니다. 중간을 지나 계속하면 같은 문자 쌍을 다시 교환하여 작업을 되돌리게 됩니다. 길이가 홀수일 때는 가운데 문자가 이미 자신의 대칭 인덱스에 있으므로 교환할 필요가 없습니다.

Python

def reverseString(s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "Coddy2026"

기대값

"6202yddoC"