문자 배열에서 단어의 순서 효율적으로 뒤집기
문자 배열에서 단어의 순서를 뒤집는 것은 알고리즘과 문자열 조작에 대한 이해를 시험하는 고전적인 문제입니다. 면접을 준비하거나 프로그래밍 기술을 다듬고 있다면, 이 도전 과제를 마스터하는 것은 매우 보람차고도 의미 있는 일입니다. 이 포스트에서는 문제를 자세히 살펴보고 C/C++에서 효율적인 솔루션을 분해해 볼 것입니다.
문제 정의
문장으로 구성된 문자 배열이 주어졌을 때, 우리는 개별 단어의 글자를 변경하지 않고 단어의 순서를 뒤집어야 합니다. 예를 들어, 다음을 입력하면:
"this is a string"
출력은 다음과 같아야 합니다:
'string a is this'
문제에서는 이 작업을 O(N) 시간과 O(1) 공간에서 수행해야 한다고 명시합니다. 이는 split()와 같은 함수나 추가 공간을 조작하는 스택과 같은 데이터 구조를 사용할 수 없음을 의미합니다.
문제 분석
시간 복잡도
O(N) 시간 복잡도의 요구 사항은 알고리즘이 데이터에 대해 선형 패스를 수행해야 함을 의미합니다. 따라서 시간 복잡도를 증가시키는 중첩 루프는 피해야 합니다.
공간 복잡도
O(1) 공간 복잡도를 위해 우리는 저장을 위한 추가 데이터 구조를 사용할 수 없습니다. 즉, 모든 작업은 입력 배열 내에서 직접 이루어져야 합니다.
해결책
해결책을 단계별로 분해해 보겠습니다. 우리는 이 문제를 효율적으로 해결하기 위해 두 번의 패스를 사용할 것입니다.
단계 1: 전체 문자열 뒤집기
첫 번째 단계는 전체 배열을 뒤집는 것입니다. 이렇게 하면 원본 문자열이 모든 문자가 뒤집힌 문자열로 변환됩니다. 우리의 예시인 "this is a string"이 뒤집힌 후:
"gnirts a si siht"
단계 2: 각 단어 뒤집기
전체 문자열을 뒤집었으니, 이제 각 개별 단어를 다시 올바른 순서로 돌려놓기 위해 뒤집어야 합니다. 다음은 C/C++에서 이 단계를 어떻게 구현할 수 있는지입니다:
void swap(char* str, int i, int j) {
char t = str[i];
str[i] = str[j];
str[j] = t;
}
void reverse_string(char* str, int length) {
for(int i = 0; i < length / 2; i++) {
swap(str, i, length - i - 1);
}
}
void reverse_words(char* str) {
int l = strlen(str);
// 전체 문자열을 뒤집기
reverse_string(str, strlen(str));
int p = 0;
// 단어의 경계를 찾고 단어별로 뒤집기
for(int i = 0; i < l; i++) {
if(str[i] == ' ') {
reverse_string(&str[p], i - p); // 확인된 단어를 뒤집음
p = i + 1;
}
}
// 마지막 단어를 뒤집기
reverse_string(&str[p], l - p);
}
코드 설명
- 스왑 함수: 우리는 배열에서 문자를 교환하기 위해 보조 함수
swap을 사용합니다. - 문자열 뒤집기 함수: 이 함수는 스왑 함수를 사용하여 문자열의 문자를 뒤집습니다.
- 단어 뒤집기 함수: 핵심 함수는 먼저 전체 문자 배열을 뒤집고, 그 후 공백으로 구분된 개별 단어를 뒤집기 위해 배열을 반복합니다. 마지막 단어는 루프가 끝난 후 처리됩니다.
복잡도 분석
배열을 두 번 뒤집는 것은 시간 복잡도를 O(N)으로 만듭니다:
- 첫 번째 패스: 전체 문자열 뒤집기 O(N).
- 두 번째 패스: 각 단어 뒤집기 O(N).
따라서 최종 시간 복잡도는 O(N)으로 유지됩니다. 공간 복잡도는 반복을 위한 변수를 제외하고는 추가 공간이 사용되지 않으므로 O(1)입니다.
결론
효율적으로 문자 배열에서 단어의 순서를 뒤집는 것은 문자열 조작과 인덱스 접근에 대한 이해가 결합되어야 가능합니다. 여기서 제시된 알고리즘은 O(N) 시간과 O(1) 공간 요구 사항을 충족하는 명확한 접근 방식을 보여줍니다. 이 솔루션을 연습하면 프로그래밍 도구의 훌륭한 추가물이 될 것입니다!