Reverse Words in a String

Q: 문자열에서 단어를 뒤집는 알고리즘의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 길이가 n 인 문자열에 대해 O(n) 시간이 걸립니다. 각 문자를 상수 횟수만큼 읽고 쓰기 때문입니다. 분할 방식은 단어 목록을 저장하기 위해 O(n) 의 추가 공간을 사용합니다. 전체 문자열을 뒤집은 다음 각 단어를 뒤집는 방식은 수정 가능한 문자 배열에서 O(1) 의 추가 공간만 필요합니다.

보통배열과 문자열 투 포인터

+10

단어와 공백으로 이루어진 문자열 s가 주어집니다. 단어는 내부에 공백이 없는 문자와 숫자의 연속입니다. 단어 사이에는 여러 개의 공백이 있을 수 있으며, s는 공백으로 시작하거나 끝날 수 있습니다.

단어의 순서를 뒤집고 정확히 하나의 공백으로 이어 붙인 결과를 반환하세요. 앞이나 끝에는 공백이 없어야 합니다. 각 단어의 철자는 그대로 유지하고, 단어의 순서만 바뀝니다.

함수

reverseWords(s: string) → string

sstring: 최소한 하나의 단어를 포함하는 문자, 숫자 및 공백
반환값string: s의 단어들을 역순으로, 공백 하나로 구분하여

제약 조건

1 ≤ s.length ≤ 10⁴
s에는 영문자, 숫자 및 공백만 포함됩니다.
s에는 적어도 한 단어가 들어 있습니다.

예제

입력: s = "Coddy runs in 15 languages"
출력: "languages 15 in runs Coddy"
설명: 단어는 Coddy, runs, in, 15, languages입니다. 마지막부터 거꾸로 읽으면 languages 15 in runs Coddy가 됩니다. 단어에는 숫자가 들어갈 수 있으므로 15도 단어로 간주됩니다.

입력: s = " practice makes progress "
출력: "progress makes practice"
설명: 양쪽 끝의 공백은 제거되고, 단어 사이에 두 개와 세 개씩 연속된 공백은 하나로 줄어듭니다. 세 단어는 마지막부터 처음 순서로 나옵니다: progress makes practice.

입력: s = " single "
출력: "single"
설명: 한 단어로 된 목록은 거꾸로 읽어도 똑같습니다. 단어 주변의 공백만 사라지므로 답은 single입니다.

후속 질문

단어를 거꾸로 배열하되 s의 공백은 유지할 수 있나요? 공백 묶음의 길이와 순서도 똑같이요?

풀이

단어 순서를 뒤집는 것은 한 번의 역순 처리입니다. 풀이가 틀어지는 부분은 공백입니다. 양 끝의 공백과 단어 사이에 반복되는 공백은 모두 사라져야 하며, 답에서는 단어 사이에 공백이 정확히 하나만 있어야 합니다. 단어들을 목록으로 분리하거나, 문자열 전체를 뒤집은 다음 하나의 배열 안에서 각 단어를 뒤집을 수 있습니다.

단어로 나눈 다음 역순으로 합치기

핵심 아이디어

s를 단어들로 나눈 다음, 목록을 뒤집고 단어 사이를 공백 하나로 연결하세요. 나눌 때 주의해야 합니다. " practice makes progress "를 공백 하나하나를 기준으로 나누면 세 단어 주변에 빈 조각이 여섯 개 생깁니다. 빈 조각을 제거하면 목록은 practice, makes, progress가 됩니다.

분할 과정에서는 각 문자를 한 번씩 읽고, 결합 과정에서는 남겨 둔 각 문자를 한 번씩 쓰므로 길이가 n인 문자열의 시간 복잡도는 O(n)입니다. 단어 목록과 결과를 저장하는 데는 O(n)의 추가 공간이 필요합니다.

알고리즘

s를 공백을 기준으로 분리합니다.
빈 조각을 제거합니다.
단어 목록을 뒤집습니다.
단어 사이에 공백을 하나씩 넣어 결합하고 결과를 반환합니다.

def reverseWords(s):
    # split() with no argument treats any run of spaces as one separator
    # and ignores spaces at both ends.
    words = s.split()
    words.reverse()
    return " ".join(words)

문자열 전체를 뒤집은 다음, 각 단어를 뒤집으세요

핵심 아이디어

문자열 전체를 뒤집으면 단어 순서는 올바르게 되지만 각 단어의 철자는 거꾸로 됩니다. Coddy runs in 15 languages는 segaugnal 51 ni snur yddoC가 됩니다. 그런 다음 각 단어를 개별적으로 뒤집으면 languages 15 in runs Coddy가 됩니다.

공백도 같은 과정에서 처리합니다. read 인덱스는 뒤집힌 배열을 순회하며 공백을 건너뛰고, write 인덱스는 다음에 유지할 문자가 들어갈 위치를 표시합니다. write는 read를 앞지르지 않으므로 복사 과정에서 아직 필요한 문자를 덮어쓰지 않습니다. 단어 앞에 기록되는 공백 하나가 read가 건너뛴 공백 하나 이상을 대신하기 때문입니다.

각 문자는 최대 한 번 복사되고 최대 두 번 교환되므로, 수정 가능한 문자 버퍼에서는 시간 복잡도가 O(n)이고 추가 공간 복잡도는 O(1)입니다. 여기서 문자열은 값으로 전달되므로 각 해법은 s의 작업용 복사본을 하나 만듭니다. 따라서 전체 메모리 복잡도는 O(n)입니다.

알고리즘

s를 문자 배열에 복사한 다음 배열 전체를 뒤집습니다.
읽기 인덱스로 배열을 순회하면서 공백을 건너뜁니다.
각 단어에서 첫 번째 단어가 아니라면 먼저 공백 하나를 쓰고, 그런 다음 단어의 문자를 쓰기 인덱스에 복사합니다.
복사한 부분을 뒤집어 단어가 앞에서부터 읽히도록 합니다.
처음 write개의 문자를 반환합니다.

def reverseWords(s):
    chars = list(s)

    def reverse(lo, hi):
        while lo < hi:
            chars[lo], chars[hi] = chars[hi], chars[lo]
            lo += 1
            hi -= 1

    n = len(chars)
    reverse(0, n - 1)  # words in the right order, each spelled backwards
    write = 0
    read = 0
    while read < n:
        if chars[read] == " ":
            read += 1
            continue
        if write > 0:
            chars[write] = " "  # one space before every word but the first
            write += 1
        start = write
        while read < n and chars[read] != " ":
            chars[write] = chars[read]
            write += 1
            read += 1
        reverse(start, write - 1)  # spell the word forwards again
    return "".join(chars[:write])

함정과 경계 사례

공백 하나를 기준으로 분리하고 모든 조각을 유지하기. "a b"는 a, 빈 조각, b로 분리되며, 다시 합치면 공백 두 개가 복원됩니다: "b a".
분리할 때 양 끝의 빈 조각이 제거된다고 믿기. Java의 split(" ")은 끝의 빈 조각은 제거하지만 앞의 빈 조각은 유지하므로, " a b"에는 여전히 빈 조각 하나가 남습니다.
마지막 단어를 포함해 모든 단어 뒤에 공백을 추가해서 답이 공백으로 끝나게 하기. 첫 번째 단어를 제외한 모든 단어 앞에 공백을 넣으세요.
제자리 버전에서 한 번만 뒤집기. 단어만 뒤집으면 yddoC snur ni 51 segaugnal이 됩니다.
PHP와 R에서는 2026과 같이 숫자로만 된 입력이 숫자로 전달될 수 있습니다. 분리하기 전에 문자열로 바꾸세요.

자주 묻는 질문3

문자열에서 단어를 뒤집는 알고리즘의 시간 복잡도는 얼마인가요?

두 접근 방식 모두 길이가 n인 문자열에 대해 O(n) 시간이 걸립니다. 각 문자를 상수 횟수만큼 읽고 쓰기 때문입니다. 분할 방식은 단어 목록을 저장하기 위해 O(n)의 추가 공간을 사용합니다. 전체 문자열을 뒤집은 다음 각 단어를 뒤집는 방식은 수정 가능한 문자 배열에서 O(1)의 추가 공간만 필요합니다.

단어 사이에 여러 개의 공백이 있을 때 어떻게 처리하나요?

단어를 공백이 아닌 문자들의 연속으로 간주하고 입력의 공백은 절대 복사하지 마세요. Python과 Ruby에서 구분자 없이 분할하는 방법과 Go의 strings.Fields, Rust의 split_whitespace는 이미 연속된 공백과 양쪽 끝의 공백을 모두 건너뜁니다. 다른 곳에서는 빈 조각을 제거하세요. 그런 다음 단어 사이에 공백 하나를 넣으세요.

split 함수 없이 단어를 뒤집을 수 있나요?

네. 오른쪽 끝에서부터 훑으세요. 공백은 건너뛰고, 단어가 끝나는 위치를 표시한 다음 왼쪽으로 이동해 단어의 시작 위치를 찾으세요. 그리고 첫 번째 단어가 아니라면 앞에 공백을 붙여 단어를 추가하세요. 각 문자를 한 번씩만 방문하므로 시간 복잡도는 O(n)으로 유지되고, 단어를 뒤집기 위한 목록 없이도 단어가 역순으로 나옵니다.

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

테스트 #1

테스트 #2

테스트 #3

인자

s = "Coddy runs in 15 languages"

예상 출력

"languages 15 in runs Coddy"