백준 10809

백준 10809 문제

 

문제 풀이

 

1. 알파벳 26자를 저장할 배열ch를 먼저 만든다.

int ch[26];

 

이 배열에는 단어의 포함 여부와 위치를 저장할 것이다.

(단어가 포함되어 있지 않다면 해당 배열의 원소는 -1이고 포함되어 있다면 -1이 아닌 위치가 저장되어 있을 것이다.)

 

2. 문자열을 입력받고, ch[26]을 -1로 초기화한다.

 

* c언어에서 문자열을 한번에 입력받고 싶다면 char 타입의 배열을 만든 후, scanf에서 %c 대신 %s로 배열을 통째 입력받으면 된다.

 

즉,

 

1) char word[100];  //char 타입의 길이가100인 word 배열을 생성하고

 

2) scanf("%s", word); //%s로 문자열(string)을 입력받아 word 배열에 그대로 넣는다.

단, 이 경우 배열에 저장하는 것이므로 &를 쓰면 안된다. (&를 생략한 배열 word는 word[0]와 동일) 

 

 string.h를 포함하여 strlen으로 word배열에 포함된 문자열의 길이를 얻는다.

 

3. ch[26]을 채워넣는다.

 

word에는 baekjoon이 저장되어있다.

ch에는 -1 -1 -1 -1 .............이 저장되어 있는데 이 숫자들은 순서대로 a, b, c, d, e.....에 해당된다. 

 

word[0] = b

word[1] = a

word[2] = e

word[3] = k 

...

이때 

ch[0]= 1

ch[1]= 0 

ch[2] = -1

...

이 저장되어야 한다. 

 

ch[0]은 알파벳 a이고

ch[index]의 해당 index는 word[i]- 'a' 로 구할 수 있다. 

 

(index가 0이면 알파벳 a인데, 이는 word[i]의 영어소문자가 a와 얼마나 떨어져있는지로 구할 수 있다.

즉, word[i]가 b이면 word[i]-'a' == 1 이다. 이때 ch[1]은 b다.)

 

이를 활용하여 ch[index]==-1이면 알파벳이 포함이 안되어 있는 것이므로, 포함된 알파벳의 처음 위치인 i를 ch[index]에 담으면 된다.

-> 처음 위치를 담은 후엔 ch[index] != -1이므로 중복된 알파벳의 다음 위치가 담길 수 없다. 

 

전체 코드는 아래와 같다.