Reverse a String

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

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

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

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

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

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

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

+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가 서로 자리를 바꿉니다.

후속 질문

문장에 있는 단어의 순서를 어떻게 뒤집어 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]를 실행한 뒤에는 기존 왼쪽 문자가 사라집니다. 단, 사용하는 언어가 두 값을 한 번에 교환하는 경우는 예외입니다.

자주 묻는 질문3

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

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

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

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

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

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

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

테스트 #1

테스트 #2

테스트 #3

인자

s = "Coddy2026"

예상 출력

"6202yddoC"