[백준BOJ10809 C++] 알파벳 찾기

문제

https://www.acmicpc.net/problem/10809

---

풀이

단어 S의 조건을 잘 이해해야 한다.

1. 단어의 길이는 100을 넘기지 않는다.
   C++을 기준으로 char 문자열은 마지막에 null 문자(\0)로 끝나야 한다. 따라서 100글자의 문자를 저장한 후에 null 문자(\0) 포함 총 101 크기를 담을 수 있어야 한다.
2. 알파벳 소문자로 이뤄져 있다.
   해당 문제에서 아스키 코드를 이용할 경우, S[i] - ‘a’ 같은 형태로 알파벳 위치를 추적할 수 있다. (S[0]이 ‘b’일 경우 ‘b’-‘a’=1 이 된다) 해당 코드는 숫자의 합에서도 사용해서 풀 수 있다.

2번의 내용을 간단하게 설명했는데 구체적으로 아스키 코드를 이용하는 이유는 출력 조건 때문이다. 알파벳이 문자에서 처음 등장하는 위치를 나타내는 것이 조건이다.

baekjoon

b:0, a:1, e:2, k:3, j:4, o:5 n:7

순서는 a b c … x y z 로 나타나기 때문에 1 0 -1 … -1 -1 -1 등으로 나타난다.

여기서 처음 등장하는 위치를 말하는 것이기 때문에 o의 경우는 6을 출력해서는 안된다. (제어문 등으로 통해 이 부분을 막도록 한다)

이렇게 된다면 a b c … x y z 를 의미하는 출력조건을 만족시키기 위해서는 알파벳 위치를 나타내는 배열을 생성해야 한다. 참고로 알파벳 갯수는 26개이며, fill_n 함수 등으로 통해 -1로 채운다. 이후 아스키 코드로 통해 알파벳 위치를 추적하여 배열에 처음 나타난 위치(i) 를 삽입한다.

  char S[101];
	int a[27];
	fill_n(a, 27, -1);

	cin >> S;
	int l = strlen(S);

	for (int i = 0; i < l; i++) {
		if (a[S[i] - 'a'] == -1) a[S[i] - 'a'] = i;
} //if는 o의 경우 6이 나오지 않기 위해 초기값인 -1일 때만 위치를 나타내도록 했다.

---

제출

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	char S[101];
	int a[27];
	fill_n(a, 27, -1);

	cin >> S;
	int l = strlen(S);

	for (int i = 0; i < l; i++) {
		if (a[S[i] - 'a'] == -1) a[S[i] - 'a'] = i;
	}

	for (int i = 0; i < 26; i++) {
		cout << a[i] << " ";
	}

	return 0;
}

제출했던 오답 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	char S[100];
	int a[27];
	fill_n(a, 27, -1);

	cin >> S;
	for (int i = 0; i < strlen(S); i++) {
		if (a[S[i] - 'a'] == -1) a[S[i] - 'a'] = i;
	}

	for (int i = 0; i < 26; i++) {
		cout << a[i] << " ";
	}

	return 0;
}

---

메모

• fill_n(arr, 배열크기, 배열에 채울 값)
• char 문자열의 끝은 null문자(\0)을 포함한다.
• strlen 함수의 시간 복잡도
  해당 함수를 for문에 그대로 사용하면 각 호출에서 매번 호출된다. 문자열의 크기를 나타내는 함수이며, 문자열의 끝을 찾기 위해 처음부터 끝까지 반복한다. 문자열의 길이에 비례하는 시간으로 작업하기 때문에 등차수열의 합 형태로 O(n^2)의 시간복잡도가 나타난다. 따라서 strlen 함수의 반환값을 저장해두고 사용해야 한다. O(n^2) 시간복잡도에 대한 글은 버블정렬에서도 작성했었다.

질문게시판에 작성한 글 에서 댓글로 통해 오답 코드에 대한 문제점을 지적해주신 changwook987님께 다시 한번 감사하다는 말씀을 드립니다.