프로그래밍 면접 문제 12: Reverse Words in a String
프로그래밍 면접 문제 12: Reverse Words in a String
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 11: All Permutations of String
이 문제는 면접 질문 중 문자열에 관한 문제 중에서 가장 자주 등장하는 문제입니다. 문자열이 입력으로 주어지면, 모든 단어를 뒤집는 문제입니다. 좀 더 명확하게 예를 들어보겠습니다. 입력이 다음과 같을때: “Interviews are awesome!” 출력은 다음과 같습니다: “awesome! are Interviews”. 또한 문자열 맨 앞과 맨 뒤의 공백은 모두 제거합니다. 따라서, ” CS degree”, “CS degree”, “CS degree “, or ” CS degree ”의 결과는 모두 공백을 제거하면 degree CS”가 됩니다.
def reverseWords1(text):
print " ".join(reversed(text.split()))
def reverseWords2(text):
print " ".join(text.split()[::-1])
파이썬에는 이 문제를 해결하는 데 유용한 함수가 있기 때문에 이를 이용하면 상당히 쉽게 해결할 수 있습니다. 공백을 기준으로 문자를 나눈 다음(맨 처음 공백과 맨 마지막 공백을 포함해서 연속된 공백 문자는 제거합니다), 각 단어의 순서를 뒤집습니다. 퍼이썬 함수를 이용해서 이를 구현하는 간단한 방법은 다음과 같이 두 가지 방법이 있습니다:
def reverseWords1(text):
print " ".join(reversed(text.split()))
def reverseWords2(text):
print " ".join(text.split()[::-1])
하지만 이 방법은 파이썬이 대부분의 일을 대신 해주기 때문에 약간의 꼼수를 부린것 같은 느낌이 듭니다. 그 대신, 주어진 텍스트에 대해서 직접 루프를 실행해서 split 함수를 사용하지 않고 단어를 직접 추출해 봅시다. 추출된 단어를 스택(stack)에 저장한 뒤(push) 단어의 순서를 뒤집기 위해서 꺼냅니다(pop). 다음은 이를 구현한 코드입니다:
def reverseWords3(text):
words = []
length = len(text)
space = set(string.whitespace)
index = 0
while index < length:
if text[index] not in space:
wordStart = index
while index < length and text[index] not in space:
index += 1
words.append(text[wordStart:index])
index += 1
print " ".join(reversed(words))
이 해결 방법은 모두 추가 공간을 사용합니다(스택 또는 새로운 리스트를 생성합니다). 하지만, 추가 공간의 사용 없이 문제 해결이 가능합니다. 문자열의 모든 문자의 순서를 뒤집은 다음, 각 단어의 글자를 뒤집으면 됩니다. 이 방법은 C 또는 C++를 이용해서 구현 가능합니다. 하지만 파이썬 문자열은 변경이 불가능하게 때문에 추가 공간을 사용하지 않고는 내용 변경이 불가능 하며, 문자열의 변경이 발생하면 새로운 문자열이 반환됩니다. 아래는 같은 로직을 이용했지만 추가 공간을 사용해서 구현한 파이썬 코드 입니다:
def reverseWords4(text):
words = text[::-1].split()
print " ".join([word[::-1] for word in words])
C/C++에서는 전체 문자열을 뒤집은 다음 읽기와 쓰기 용도의 포인터 두개를 이용해서 뒤집은 문자열에 대해서 루프를 실행합니다. 문자열이 저장된 공간에서 변경한 문자를 덮어씁니다. 연속적인 공백 및 처음과 끝에 위치한 공백까지 제거하기 때문에 결과로 얻은 문자열은 원본 문자열보다 짧을 수 있습니다. 이렇게 공백을 제거하기 때문에 2개의 포인터가 필요합니다. 하지만 쓰기 용도의 포인터는 읽기 포인터를 지나칠 수 없도록 해서 충돌이 발생하지 않게 해야합니다. 다음은 C로 작성한 코드입니다:
void reverseWords(char *text)
{
int length = strlen(text);
reverseString(text, 0, length-1, 0);
int read = 0, write = 0;
while (read < length)
{
if (text[read] != ' ')
{
int wordStart=read;
for ( ; read < length && text[read] != ' '; read++);
reverseString(text, wordStart, read-1, write);
write += read - wordStart;
text[write++] = ' ';
}
read++;
}
text[write-1]='\0';
}
void reverseString(char *text, int start, int end, int destination)
{
// reverse the string and copy it to destination
int length = end - (start + 1);
int i;
memcpy(&text[destination], &text[start], length * sizeof(char));
for (i = 0; i < (length / 2); i++)
{
swap(&text[destination + i], &text[destination + (length - 1 - i)]);
}
}
이 문제는 가장 일반적인 인터뷰 질문 중 하나이기 때문에 인터뷰를 준비하는 사람은 누구나 손쉽게 해결할 수 있어야합니다.
