2/18기록 - 백준 1316

오늘은 어제 공부한 알고리즘이 좀 어려웠기 때문에 기분 좋게 백준 실버 5문제를 풀어 보았다.

백준 1316번 그룹 단어 체커 문제이다.

 

 

문제를 이해하기는 쉽다. 문자열에서 이전 문자와 같은 문자가 이어서 나오면 그룹을 형성할 수 있고, 다른 문자가 나왔을 때 이전에 해당 문자가 나오지 않았다면 문자 하나라도 그룹으로 체크할 수 있다. 이렇게 문자열 하나를 모두 조사해서 그룹으로만 형성 되었다면 해당 단어를 그룹 단어로 판단 가능하다. 그런 문자가 몇 개 인지를 파악하는 문제이다.

 

알고리즘 생각

사실상 문제를 설명 하면서 거의 문제의 핵심을 말했다고 해도 과언이 아니다.

1. 단어를 체크할 boolean 함수를 하나 만들고, 해당 함수가 true이면 count++ 시켜준다.

2. 함수 안에서 문자열을 입력 받는다.

3. 알파벳을 담을 boolean 배열을 크기 26으로 만든다.

4. 문자열의 길이 만큼 반복하는 반복문 안에서 알고리즘을 구현한다.

- 이전 문자 변수 선언, 체크할 현재 문자를 charAt()으로 뽑아냄

- 이전 문자와 현재 문자가 다르면 체크, 같으면 그룹이므로 지나감

- 배열의 인덱스로 체크를 하는데, 'a'의 아스키 코드가 97이므로 배열[현재 알파벳 - 97]이 false라면 이전에 나온적 없는 문자이므로 문자를 그룹으로 판단하고 true를 반환해줌 그리고 현재 체크한 문자를 이전문자로 만들어줌

- 배열[현재 알파벳 - 97]이 true라면 이전에 나온적 있는 문자이므로 그룹 X -> false를 반환해줌

- 그룹 문자면 true가 반환되므로 최종적으로 함수의 return값을 true로 지정해줌.

 

 

※ 경우의 수를 살펴보면

 

이전 문자와 같은 문자가 나오는 경우(그룹) -> 그냥 true반환

 

이전 문자와 다른 문자가 나오는 경우 ->  1. 앞에 해당 문자가 없을 때(false가 나오는 상태) - 그룹 => true 입력

                                                      2. 앞에 해당 문자가 있을 때(true가 나오는 상태) - 그룹 X => false 반환 시킴

 

 

이렇게 해결 할 수 있었다. 문제의 특징을 두 가지 정도 살펴 보자면, BufferedReader를 static변수로 선언해서 함수에까지 영향을 주게 만드는 점과 이전문자와 현재문자를 int 변수로 만들어서 배열의 인덱스로 해결할 수 있게 하는 점이다. 해당 포인트를 놓치면 문제를 다 구상해 놓고 어렵게 풀 수 있다.

 

2/18 기록 끝!!!!!!!!