문자열
알고 있어야 할 내용
- 추가 공간을 이용하면 무식하지만 간단한 방법으로 해결할 수 있다.
- 가변 문자열을 앞에서부터 갱신해나가면 느리므로 뒤에서 부터 값을 붙여 나가야 한다.
문자열 라이브러리 함수들
- == 는 포인터 동등성이 아닌 논리적 동등성을 검사한다.
- insert의 경우 iter를 쓰고 싶다면 뒤 인자는 char 혹은 initialize_list
를 넣어주어야 한다.. - string을 넣고 싶다면 size_t를 첫 인자로 쓰고 뒤 인자로 string을 하자
- int isalnum(int a)
- true / false 반환
- Checks whether c is either a decimal digit or an uppercase or lowercase letter.
- int tolower(int a)
- Converts c to its lowercase equivalent if c is an uppercase letter and has a lowercase equivalent. If no such conversion is possible, the value returned is c unchanged.
int main()
{
string a = "0123";
a.append("45");
cout << "string a : " << a << endl;
a.push_back('6');
cout << "string a : " << a << endl;
a.pop_back();
cout << "string a : " << a << endl;
a.insert(a.begin()+6, {"67"});
cout << "string a : " << a << endl;
string b = a.substr(1, 5); // pos, len
cout << "string b : " << b << endl;
cout << "b.compare(a) : " << b.compare(a) << endl;
cout << "a.compare(b) : " << a.compare(b) << endl;
cout << "a.compare(a) : " << a.compare(a) << endl;
cout << "a==a : " << (a==a) << endl;
return 0;
}
/* print
string a : 012345
string a : 0123456
string a : 012345
string a : 0123465
string b : 12346
b.compare(a) : 1
a.compare(b) : -1
a.compare(a) : 0
a==a : 1
*/
다른 라이브러리 함수들
- reverse
- 뒤집을 때 좋다.
- size
- string 의 경우 c의 문자열과 달리 length와 결과값이 같다.
- ‘\0’ 이 끝에 없기 때문
- string 의 경우 c의 문자열과 달리 length와 결과값이 같다.
palindrom
회문(palindromic)은 거꾸로 읽어도 같은 문자열을 뜻한다. 문자열을 뒤집어 추가 공간을 사용하기 보단, 입력 문자열을 앞뒤로 동시에 읽어 공간을 절약한다. 길이가 짝수든 홀수든 동일하게 처리할 수 있다.
bool IsPalindromic(const string& s) {
for (int i = 0; j = size(s) -1; i < j; ++i, --j) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
n이 문자열의 길이라고 했을 때, 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)이다
문제 6.1 문자열과 정수 상호 전환하기
정수형 숫자(음의 정수를 포함) 값이 문자열로 주어 졌을 때, 이를 정수형 숫자로 바꾸는 프로그램을 작성하라. 단, C++에서 제공하는 stoi 같은 라이브러리 함수를 사용하면 안 된다.
정수를 문자열로 변환하는 함수와 문자열을 정수로 변환하는 함수를 작성하라.
힌트: 숫자를 하나씩 차례대로 만들어 보자
근사한 방법으로 가장 왼쪽의 숫자부터 계산을 시작하는 방법이 있다. 즉, 중간 결괏값에 10을 곱한 뒤 각 자리수를 더해 나가면 된다. 문자열 “314” 를 정수로 바꾼다고 해보자. 중간값 r=0으로 초기화 해두고 첫 번째 반복에서 r=3이 된다. 두 번째에서는 r=310 + 1 이 된다. 마지막으로 r=3110 +4 가 된다.
음수의 경우에는, 부호를 기억한 뒤 마지막 결과를 음수로 바꿔 주면 된다.
string IntToString(int x) {
bool is_negative = false;
if (x<0) {
is_negative = true;
}
string s;
do {
s += '0' + abs(x % 10);
x /= 10;
} while (x);
s += is_negative ? "-" : ""; //is_negative면 음수 부호를 뒤에 붙여준다
return {rbegin(s), rend(s)};
// 뒤집는듯
}
int StringToTint(const string& s) {
return (s[0] == '-' ? -1 : 1) *
accumulate(begin(s) + (s[0] == '-' || s[0] == '+'), end(s), 0,
[](int running_sum, char c) {
return running_sum * 10 + c - '0';
});
}
문제 6.2 밑수 바꾸기
문자열 하나와 두 개의 정수 b1, b2가 주어졌을 때, 정수의 밑수를 바꾸는 프로그램을 작성하라. 밑수가 b1인 입력 문자열을 밑수가 b2인 문자열로 바꾸면 된다. 2≤b1, b2≤16이고, “A”는 10, “B”는 11, … “F”는 15를 나타낸다. 예를 들어 문자열이 “615”이고, b1은 7, b2는 13일 때, 결과는 “1A7”이 된다. 왜냐하면 6 * 7^2 + 1 * 7 + 5 = 1 * 13^2 + 10 * 13 + 7 이기 때문이다.
힌트: 우리가 주로 사용하는 밑수는 무엇인가?
string ConvertBase(const string& num_as_string, int b1, int b2) {
bool is_negative = num_as_string.front() == '-';
int num_as_int =
accumulate(begin(num_as_string) + is_negative, end(num_as_string), 0,
[b1](int x, char c) {
return x * b1 + (isdigit(c) ? c - '0' : c - 'A' + 10);
});
return (is_negative ? "-", "") +
(num_as_int == 0 ? "0" : ConstructFromBase(num_as_int, b2));
}
string ConstructFromBase(int num_as_int, int base) {
return num_as_int == 0 ? ""
: ConstructFromBase(num_as_int / base, base) +
static_cast<char>(num_as_int % base >= 10
? 'A' + num_as_int % base - 10
: '0' + num_as_int % base);
}
s의 길이를 n이라고 했을 때 시간 복잡도는 O(n(1+$log_{b2}{b1}$))이 된다. 먼저 s에서 x를 얻기 위해 n개의 곱셈과 덧셈을 수행한다. 그 뒤 $log_{b2}x$만큼의 곱셈과 덧셈을 수행한다. x의 상한은 b1^n이고 따라서..
문제 6.3 스프레드시트 열 인코딩 계산하기
스프레드시트는 열을 표현할 때 알파벳을 사용한다. 열 값이 문자열로 주어졌을 때 이를 정수값으로 변환하는 함수를 작성하라. 단 “A”는 1을 나타낸다. 즉, “D”는 4, “AA”는 27, “ZZ”는 702 등으로 표현된다.
풀이 방법
- [”A”, “Z”]에는 26개의 문자가 존재하고, 각 문자는 어떤 숫자로 대응한다
- 26진수 숫자를 정수값으로 바꾸는 문제와 거의 같다. “A”가 0이 아닌 1과 대응된다는 점이 다르다.
문제6.4 문자열 바꾸고 삭제하기
문자 배열이 주어졌을 때 ‘b’는 삭제하고 ‘a’는 ‘d’ 두 개로 대체하는 프로그램을 작성하라.
풀이 방법
두 가지 방법을 합쳐 하나의 완성된 알고리즘을 얻을 수 있다. 먼저 배열을 차례로 읽으면서 ‘b’를 지우고 최종 문자의 개수를 구한다. 그다음에 뒤에서부터 거꾸로 배열을 읽으면서 ‘a’를 두 개의 ‘d’로 바꾼다. ‘b’가 ‘a’보다 많다면 유효한 최종 문자의 개수는 줄어들 것이다. 반대는 늘어날 것이다.
배열을 앞으로 한 번 뒤로 한 번 총 두 번 읽으므로 전체 시간 복잡도는 O(n)이다. 추가 공간은 필요하지 않다.
문제 6.5 회문 확인하기
여기서의 회문(palindrom)이란 알파벳이 아닌 문자들을 모두 제거했을 때 앞뒤로 읽은 결과가 같은 경우를 말한다. 대소문자는 구별하지 않는다. 문자열 s가 주어졌을 때 이 문자열이 회문인지 확인하는 함수를 작성하라.
힌트: 인덱스 변수 두 개를 사용하여 풀어 보자.
변수 두 개를 이용하여 하나는 뒤에서 앞으로, 다른 하나는 앞에서 뒤로 읽으며 알파벳을 비교한다. 서로 교차하면 s는 회문이다
bool IsPalindrome(const string& s) {
// i는 앞으로 읽고, j는 뒤로 읽는다.
int i = 0; j = size(s) - 1;
while (i < j) {
// i와 j는 영문자나 숫자가 아니면 건너뛴다.
while (!isalnum(s[i]) && i < j) {
++i;
}
while (!isalnum(s[j]) && i < j) {
++j;
}
if (tolower(s[i++] != tolower(s[j--]))) {
return false;
}
}
return true;
}
s의 길이를 n이라고 했을 때 전체 시간 복잡도는 O(n)이다.
문장의 모든 단어 뒤집기
빈칸으로 구분되는 단어 집합이 있을 때 이 단어의 순서를 역순으로 배열해 보자 예를 들어 “Alice likes Bob”은 “Bob likes Alice”가 된다. 입력 문자열의 원본은 유지하지 않아도 된다.
문자열 s의 단어를 모두 뒤집는 함수를 작성하라.
풀이 방법
- 문자열을 한 번만 읽어서 풀기는 쉽지 않다.
- 단일 패스를 통해 각 문자의 최종 위치를 알아내기는 어렵다. 모든 단어가 단일 문자로 구성되어 있다면 단순히 s를 뒤집기만 하면 될 것이다. 일반적으로 s를 뒤집으면 단어는 상대적으로 올바른 위치에 놓인다. 단어의 길이가 1이상일 때는 문자가 역순으로 표현되어 버린다. 각 단어를 다시 뒤집어 주면 해결할 수 있겠죠.
개미수열 문제
개미수열(look-and-see)은 1부터 시작한다. 그 다음 수열은 이전 수열을 설명하는 방식으로 진행되는데, 이전 수열에서 나타난 숫자와 해당 숫자가 연속으로 쓰인 개수를 함께 쓰는 방식으로 진행된다. 1로 시작하는 개미수열의 첫 여덟 개 숫자는 <1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211> 이다.
정수 n이 주어졌을 때 n번째 개미수열을 문자열로 출력하는 프로그램을 작성하라
풀이 방법
- 정수가 아닌 문자열로 출력하면 된다.
- 문자열을 사용하면 쉽게 연속된 숫자의 개수를 셀 수 있다.
로마 숫자를 10진수로 바꾸기
로마 숫자는 문자 집합 I, V, X, L, C, D, M 을 이용해서 자연수를 표현하는데, I는 1, V는 5, X는 10, L은 50, C는 100, D는 500, M은 1000을 나타낸다. 다음은 예외 사항이다.
- I는 V혹은 X바로 전에 올 수 있다
- X는 L혹은 C바로 전에 올 수 있다
- C는 D혹은 M바로 전에 올 수 있다
로마 숫자는 각 문자에 대응하는 숫자를 더하면 되는데, 위의 예외 상황에서는 큰 수에서 작은 수를 뺀 결과를 더해 주면 된다.
유효한 로마숫자가 문자열로 주어졌을 때 이에 상응하는 정수를 반환하는 프로그램을 작성하라
풀이 방법
- 위의 예외 상황을 제외하고 생각해 보자
- 무식한 방법은 문자열 s를 왼쪽에서 읽어나가면서 일반적인 경우에는 해당 문자에 대응하는 숫자를 더해 주고, 예외 상황에서는 높은 숫자에서 낮은 숫자를 뺀 결과를 더해 주는 것이다.
- 좀 더 간단히 하기 위해 문자열을 거꾸로 읽어 보자. 문자열을 오른쪽에서 왼쪽으로 읽으면서 전보다 숫자가 작은 경우에는 전체 결과에서 빼주고, 아닌 경우에는 더해 준다.
Leave a comment