[C++]BOJ 10809번 : 알파벳 찾기

시간제한	메모리제한	알고리즘 분류
1 초	256 MB	구현, 문자열

 

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

출력

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.
만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

제한

• 0 ≤ S의 길이 ≤ 100

---

문제 해결 조건

알파벳 a부터 z까지가 입력받은 단어에 포함되어 있는 경우 a-z순으로 해당하는 인덱스를 출력하고, 포함되어 있지 않은 경우에 "-1"을 출력한다. 각 숫자는 공백을 구분해 출력한다.

 

1차 시도한 코드

이중 반복문 없이, 조건문을 이용하려 했음.

// 1) 알파벳 여부 확인용 배열 초기화
    int arr[26];
	for (int i = 0; i < 26; i++)
	{
		arr[i] = -1;
	}

먼저, 알파벳이 들어있는지 대조하기 위한 배열 arr를 선언해 알파벳 갯수만큼 "-1"을 초기화한다.

// 2) 단어와 알파뱃 대치 확인
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] >= 97 && s[i] <= 122)
		{
			arr[s[i] - 97] = i;
		}
	}

단어를 입력받을 스트링 s를 선언하고, 입력받는다. s[i]는, 입력받은 단어의 i번째 문자이다. if (s[i] >= 97 && s[i] <= 122) 조건을 통해 단어가 소문자인지 확인한다. s[i] - 97은, 알파벳의 정수 표현이다. 예를 들어, baekjoon을 입력했을 때, s[0] - 97 = 'b' - 97 = 'b' - 'a' = 1로, 알파벳 배열의 두번째 글자인, b를 나타내는 정수이다. 반복문에서 i를 증가시키면서 arr[s[i] - 97]에 i를 저장하면, 알파벳이 단어에서 몇 번째로 등장했는지 확인할 수 있다. 

// 3) 출력용 반복문
	for (int i = 0; i < 26; i++)
	{
		cout << arr[i] << " ";
	}

아래는 1차 시도 코드 합본.

#include <iostream>
#include <string>

using namespace std;

void solve() {
	string s;
	cin >> s;
	int arr[26];
	
	for (int i = 0; i < 26; i++)
	{
		arr[i] = -1;
	}

	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] >= 97 && s[i] <= 122)
		{
			arr[s[i] - 97] = i;
		}
	}

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

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}

1차 출력 결과 (실패)

 

 

출력 결과는 아래와 같아야하는데, '5'의 자리에 6이 온 채로 출력되었다. 따라서 전체적인 코드를 다시 살펴보고 구현에 오류가 없었는지 검증한다. 아마도 baekjoon과 같이 반복된 문자가 있는 단어를 입력한 경우 때문에 생긴 것 같다.

// 2) 단어와 알파뱃 대치 확인
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] >= 97 && s[i] <= 122)
		{
			arr[s[i] - 97] = i;
		}
	}

기존에 시도했던 위 코드는, arr[s[i]-97]에 i를 대입할 때, 중복 처리를 거치지 않았다. 만약 입력받은 단어에 같은 글자가 있을 경우, 의도했던 바와 다르게 처음 등장한 'o'가 아니라 뒤에 위치한 'o'의 i값이 출력되는 오류가 발생한다. 

// 2) 단어와 알파뱃 대치 확인 (수정)
	for (int i = 97; i <= 122; i++)
	{
		for (int j = 0; j < s.length(); j++)
		{
			if (i == s[j])
			{
				arr[s[j] - 97] = j;
				break;
			}
		}
	}

따라서 입력한 단어의 알파벳 등장 여부를 확인하는 코드를 위와 같이 수정했다. 단어의 문자를 처음부터 97, 즉 "a"와 비교하기 시작해서 "z"까지 대조할 것이다. 조건문의 조건인 i == s[j]는, 입력받은 단어 s의 j번째 글자를 a부터 z까지 대조하는 조건이며, 일치하는 알파벳이 있을 경우, 알파벳의 첫 등장 순서는 j가 된다. 그리고 break로 반복문을 종료시키고 다음 알파벳을 확인하는 과정으로 넘어가 중복을 피한다. 

 

2차 시도 완성 코드 (성공)

#include <iostream>
#include <string>

using namespace std;

void solve() {
	string s;
	cin >> s;
	int arr[26];
	
	// 1) 알파벳 여부 확인용 배열 초기화
	for (int i = 0; i < 26; i++)
	{
		arr[i] = -1;
	}

	// 2) 단어와 알파뱃 대치 확인
	for (int i = 97; i <= 122; i++)
	{
		for (int j = 0; j < s.length(); j++)
		{
			if (i == s[j])
			{
				arr[s[j] - 97] = j;
				break;
			}
		}
	}

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	solve();
}