[백준 알고리즘] 10809번 : 알파벳 찾기

문제

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

입력

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

출력

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.

만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

예제 입력 1

baekjoon

예제 출력 1

1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

 

내가 작성한 코드(C++ 성공)

#include <iostream>
#include <string.h>

using namespace std;

int main(){
	char s[101];	
	int alpa[27]; // 알파벳 26개 
	
	cin >> s;
	
	for(int i=0; i<26; i++){
		alpa[i] = -1; // 알파벳 배열 값 -1로 초기화
	}
	
	int size = strlen(s); // char 배열의 크기
	
	for(int i=0; i<size; i++){
		if(alpa[(int)(s[i]-97)] == -1) { // 한 번도 쓰이지 않았다면
			alpa[(int)(s[i]-97)] = i;    // 배열 값 입력
		}
	}
	
	for(int i=0; i<26; i++){
		cout << alpa[i] << " "; // 알파벳 배열 출력
	}
	
	return 0;
}

 

정리

이 문제는 아스키 코드에서 'a' = 97 부터 'z' = 122 까지의 값을 가진다는 점을 이용해서 풀었다.

정말 계속해서 틀려서 어떤 부분이 틀렸는지 애먹은 문제였다.
일단 내가 잘못 작성한 코드에서 어떤 점이 잘못되었는지 적어보았다.

1. 중복된 알파벳이 있다면 가장 먼저 나온 알파벳의 위치를 입력해야 한다.
2. 알파벳은 a 부터 z 까지 26개로 되어있다. = 출력할 때 26개의 배열의 값이 출력되어야 한다.
3. 중복 알파벳 처리

자세히 정리해보자.

[1. 중복된 알파벳이 있다면 가장 먼저 나온 알파벳의 위치를 입력해야 한다.]

예제 입력을 넣었을 때 출력이 잘 나와서 작성한 코드를 제출했다.
오답 코드를 보면,

// 틀린 코드

#include <iostream>
#include <string.h>

using namespace std;

int main(){
	char s[101];	
	int alpa[27] = {0};
	
	cin >> s;
	
	for(int i=0; i<27; i++){
		alpa[i] = -1;
	}
	
	for(int i=0; i<strlen(s); i++){
		if(s[i] != s[i-1]){
			alpa[(int)(s[i]-97)] = i;
		}
	}
	
	for(int i=0; i<27; i++){
		cout << alpa[i] << " ";
	}
	
	return 0;
}

이 부분이 잘못되었다는 것을 알 수 있었다.

	for(int i=0; i<strlen(s); i++){
		if(s[i] != s[i-1]){
			alpa[(int)(s[i]-97)] = i;
		}
	}

s[i] != s[i-1] 일 경우에만 알파벳 배열에 값을 넣어주게 코드를 짰는데,
예를 들어, 'aba' 가 입력되었다면 a는 앞에 있는 b와 다르기 때문에 a의 위치가 2가 된다.
따라서, a는 0이 되어야 하기 때문에 오답이 된다.

[2. 알파벳은 a 부터 z 까지 26개로 되어있다.]

정답을 맞추기 전 코드를 보면 알 수 있다.

#include <iostream>
#include <string.h>

using namespace std;

int main(){
	char s[101];	
	int alpa[27];
    
	cin >> s;
	
	for(int i=0; i<27; i++){
		alpa[i] = -1;
	}
	
	int size = strlen(s);
	
	for(int i=0; i<size; i++){
		if(alpa[(int)(s[i]-97)] == -1) {
			alpa[(int)(s[i]-97)] = i;
		}
	}
	
	for(int i=0; i<27; i++){
		cout << alpa[i] << " ";
	}
	
	return 0;
}

코드를 잘 보면 이부분.

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

이 부분을 잘 보면 알파벳은 26개로 되어있기 때문에 26개의 값이 출력되어야 한다.
그런데 반복문을 보면 i=0 부터 i=26 까지 반복되게 있다.
따라서, 27개의 값이 출력된다는 말이다. 그래서 오답처리 되었다.
아무리 봐도 정답인거 같아 a 부터 z까지 순서대로 전부 넣어보았다.
그랬더니, 어이없는 결과가 나와버렸다.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 -1

마지막에 '-1' 의 숫자가 떡하니 나와있는.... 정말 어이없는 경우였다.
그래서 이 부분을 수정해주어 성공할 수 있었다.

[3. 중복 알파벳 처리]

1번과 같은 맥락일 수도 있다.
1번에서는 조건을 잘못 정해주어서 생긴 문제였다면 이번에는 코드상의 문제였다.
만약 알파벳이 중복되어 나온다면 어떻게 처리해주어야 할까? 고민을 많이 했다.
그래서 생각한 부분이 이중 반복문을 통해 비교해서 처리해주자 라고 생각해서
중복되는 숫자가 없다면 해당 숫자의 위치를 알파벳 배열에 바로 넣어주고
만약 중복되는 숫자가 있다면 index가 작은 값에 넣어주자 등등등 여러 시도를 해보았지만
잘못된 생각이었다.

핵심은 현재 위치에 있는 알파벳이 이전에 나왔던 알파벳이라면 건너뛴다는 것이다.

그래서 수정해서 성공한 코드가 이거였다.

	for(int i=0; i<size; i++){
		if(alpa[(int)(s[i]-97)] == -1) { // 한 번도 쓰이지 않았다면
			alpa[(int)(s[i]-97)] = i;    // 배열 값 입력
		}
	}

정말 간단하게 알파벳 배열을 초기에 '-1' 로 초기화 해주었기 때문에
만약 입력한 값 중에 알파벳이 중복되었다면 '-1' 이 아닌 다른 값이 들어가 있다는 것이다.

마지막으로 문자열을 다루는 문제였는데 생각보다 고전한 문제였다.
다들 잘하시는 분들이라 엄청 간단한 코드로 작성되어있어 덤빌 생각도 못하고 천천히 하나씩 다시 생각했던 것 같다.
문자와 문자열에 관련된 함수와 입출력에 대해서 공부할 필요성을 느꼈다.