자료구조 : 문자열

 

1. 문자열의 정의

스트링(string)이라고도 한다.

이러한 기호는 미리 정의된 집합이나 음소 문자에서 선택한다.

프로그래밍에서 문자열은 일반적으로, 요소가 문자 인코딩과 관련된 문자를 대표하는 일련의 자료값을 저장하고 있는 자료형으로 이해할 수 있다. 여기서 문자 인코딩의 경우 더 일반적인 배열 자료형과 차이가 있다. 이러한 환경에서 'binary string'과 'byte string'이라는 용어는 저장된 자료가 반드시 텍스트를 표시하지 않아도 되는 문자열을 표시하는 데 사용된다.

문자열 자료형으로 선언된 변수의 경우, 미리 정의된 어느 정도의 기호를 소유할 수 있는 메모리에 기억 자료를 할당하는 것이 보통이다. 문자열이 소스 코드에 보이면 그 문자열을 string literal이라고 일컫는다.

 

대표적인것이 아스키 코드이다.

0은 아스키코드로 NULL을 나타낸다.

숫자로 저장되어있지만 출력은 문자로 한다.

 

printf("%c", 65);     //A

printf("%c", 48);     //0

 

C++ string을 문자로 바꾸려면 stoi, stol, stoll등의 함수를 사용하면 된다.    //string to int, string to long

문자열로 바꾸고 싶으면 to_string 함수를 사용하면 된다.

여러 자료형에 대해서 오버라이딩이 되어있다.

 

for(int i=0; i<strlen(str); ++i)   

//컴파일러에 따라 strlen의 시간복잡도는 O(N)이기 때문에 총 O(N^2)의 시간이 걸릴수도 있다.

// visual studio또는 c++ 표준 등은  O(1)의 시간복잡도로 구현되어 있어 안심하고 사용해도 된다.

 

int len = strlen(str);

for(int i=0; i<len; ++i)           

//와 같은 방법으로 하는게 좋다.

 

for(int i=0; s[i]; ++i)

//strlen이나 string의 length이나 size를 사용할 수 없는 경우에는 문자열의 끝이 0(NULL)인 특징을 활용한다.

 

가끔 itoa를 사용할때 저지사이트에서 컴파일에러가 뜬다.

itoa 는 C 표준 함수가 아니며, 일부 C 구현체에만 지원한다.

sprintf(ch, "%d", result) 또는 to_string를 사용하자.

 

2. 문자열 관련 문제 풀이

백준 10808번 알파벳 개수 : https://www.acmicpc.net/problem/10808

알파벳의 개수를 배열에 저장하여 출력한다.

 

백준 10820번 문자열 분석 : https://www.acmicpc.net/problem/10809

알파벳이 문자열에서 처음나온 위치를 출력한다.

memset(arr, -1, sizeof(arr));

을 이용하여 -1로 초기화한후 배열이 -1이 아니면 문자열의 해당 위치를 저장한다.

 

백준 2743번 단어 길이 재기 : https://www.acmicpc.net/problem/2743

문자열의 길이를 출력한다.

 

백준 11655번 ROT13 : https://www.acmicpc.net/problem/11655

한 라인을 입력받아 그중 A~Z, a~z 문자를 알파벳내에서 13만큼 움직인 문자열을 출력한다.

주의할 점으로는 소문자 알파벳중 13을 더하면 아스키 코드의 마지막인 127(DEL)을 넘어가서 문제가 생길수도 있다는 것이다. 또한 fgets는 '\n'까지 입력에 포함시키기 때문에 100길이를 입력해도 102만큼의 입력 공간이 필요하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

int main(void) {
	char str[102];
	fgets(str, 102, stdin);

	int len = strlen(str);
	for (int i = 0; i < len - 1; ++i) {
		if ('A' <= str[i] && str[i] <= 'Z') {
			str[i] += 13;
			if (str[i] > 'Z') str[i] -= 'Z' - 'A' + 1;
		}
		if ('a' <= str[i] && str[i] <= 'z') {
			if (str[i] + 13 > 'z') str[i] -= 'z' - 'a' + 1;
			str[i] += 13;
		}
	}
	puts(str);
	//system("pause");
}

 

백준 10824번 네수 : https://www.acmicpc.net/problem/10824

주의할점은 stoi를 사용해서 문자열을 int로 바꿀경우 13자리를 초과해서 런타임 에러가 나올수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int main(void) {
	string A, B, C, D;
	cin >> A >> B >> C >> D;

	A += B;
	C += D;
	cout << stol(A) + stol(C);
	//system("pause");
}

 

백준 11656번 접미사 배열: https://www.acmicpc.net/problem/11656

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

char arr[1002][1002];

int main(void) {
	string s;
	cin >> s;
	int ssize = s.size();
	for (int i = 0, j; i < ssize; ++i) {
		for (j = 0; j < ssize - i; ++j) arr[i][j] = s[i + j];
		arr[i][j] = '\n';

	}

	for (int i = 0; i < ssize; ++i) for (int j = 0; j < ssize; ++j)
		if (strcmp(arr[i], arr[j]) <= 0) {
			char temp[1002];
			strcpy(temp, arr[i]);
			strcpy(arr[i], arr[j]);
			strcpy(arr[j], temp);
		}


	for (int i = 0; i < ssize; ++i) cout << arr[i];
	//system("pause");
}