이번 문제는 그룹 단어를 찾는 문제였습니다. 그룹 단어에 대한 설명은 스크린샷으로 대체하도록 하고 문제를 이해하셨다는 기준하에 설명해 보도록 하겠습니다.
먼저 이 문제도 저번 문제처럼 좀 많이 걸렸습니다. 결론부터 말하자면 이번에 배운건 좀 머리를 써야할 문제 같으면 제 머리를 믿지 말고 종이로 한 번 써보자는 것이었습니다! 종이에 견적표 짜듯이 한 번 쭉 짜고 나서 종이를 보고 프로그래밍 하니 2일 걸려도 못 했던게 10분만에 풀렸습니다. 또한 도저히 for문 만으로는 제 사고 방식으로 오류가 자꾸 나와서 다른 분들이 어떤 방식으로 풀었나 구글링 해본 결과 배열을 사용한다는 것을 알고 배열이라는 힌트를 들고 제가 풀어봤습니다.
Step0. 나의 코드
import java.util.Scanner;
public class Group_Word_Check {
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
// TODO Auto-generated method stub
int count = 0; // 그룹 단어 개수
int cicle = sc.nextInt(); // 인풋 될 문자열 개수
for (int i = 0; i < cicle; i++) {
if (check() == true) {
count++;
}
}
System.out.println(count);
}
public static boolean check() {
String word = sc.next();
int num_word; // 단어의 위치를 숫자로 저장
boolean[] check_word = new boolean[26]; //알파벳 개수만큼 배열 생성. 알파벳의 순서대로 기본값 false가 들어있고 쓰인적이 있는 단어라면 true를 선언하므로써 중복된 단어를 찾는대 사용
for (int i = 0; i < word.length(); i++) { // 단어의 수 만큼 반복
num_word = word.charAt(i) - 97; // 현재 알파벳의 인덱스 위치 저장
// check_word[num_word] = true; //첫 단어는 무조건 쓰였으므로 true 저장.
if (check_word[num_word] == false) { // 현재 문자가 쓰인적이 없으면
check_word[num_word] = true; // 현재 문자를 쓰인 문자로 바꿔주고(true) 다음 문자 확인.
continue; // 처음 쓰였던 문자기에 아무 이상 없으므로 다음 문자 확인.
} else { // 현재 문자가 쓰인적이 있으면
if (word.charAt(i) == word.charAt(i - 1)) { // 현재 문자와 바로 전 문자가 같은 모양이면..즉 연속된 문자이면
continue; // 연속된 문자. 즉 안전한 문자이므로 continue
} else { // 현재 문자와 바로 전 문자가 다른 모양이면? 현재 문자는 이미 쓰였던건데 중복으로 쓰였다는 소리니깐 이 문자는 그룹 문자가 아니다! 바로
// 메소드 종료.
return false;
}
}
} return true; //모든 조건을 만족하고 false에 걸리지 않았으므로.
}
}제가 코딩을 하면서 주석으로 어떤 내용의 for문과 if문인지를 대충 써놨습니다.
ch()메서드의 경우 return true가 없으면 오류가 납니다. 이유는 return false만 있을 경우는 어떠한 조건이 맞았을 때만 false가 나오고 맞지 않아서 false를 리턴하지 못한 경우는 return할 값이 없기 때문입니다. 그렇기에 for문이 끝난 후 return문은 필수입니다. 이러한 점도 공부 할 때는 알았지만 정작 코딩에서는 제대로 생각나지 않았던 부분 같았습니다.
Step1. 문제 접근
- 첫 접근 방법(실패) : 잘못됐다기 보다는 약간 미련한 접근 방법이었습니다. 처음에 저는 문제를 보고 charAt메서드를 사용하여서 for문과 if문을 여러번 돌려서(4~5번) 풀어보고자 하였습니다. 물론 안될건 없지만 문제를 풀면서 느낀건 중간 중간 너무 많은 변수가 생긴다는 점입니다. 코드도 길어지고 중간에 문자열의 형태를 바꾸면 배열의 길이도 바뀌어서 오류도 자꾸 나오고 했습니다. 결국 하루 하고도 반나절을 씨름을 하다가 안되겠다 하고 구글링을 통해 힌트 (배열을 사용하는 방법)를 갖고 다른 방식으로 문제에 접근하였습니다.
--- 제가 했던 방법중 하나는 우선 문자열을 처음부터 차례로 charAt을 사용해서 확인하였습니다. 그 후 기준 문자열(현재 문자열)의 다음 문자열이 기준 문자열과 같으면 연속으로 나온 문자이므로 다음 문자를 확인하고 다음 문자가 같으면 반복을, 다르면 방금까지 중복되던 문자가 앞으로 다시 나오나 안 나오나를 확인하여(해당 문자 위치 이후로 같은 문자가 다시 나오면 그룹 단어에서 탈락) 그룹 단어를 확인했습니다. 이론상으로는 맞으나 코딩 과정에서 과다한 for문 if문의 남용으로 인하여 너무 꼬여버려서 다른 방법을 찾았습니다. ----
- 두 번째 접근 방법(성공) : 이번에는 구글링을 통해 다른 분들이 푼 방법을 참고하였습니다. 제가 참고한 부분은 거의 대부분의 분들이 쓰신 배열이었습니다. 그래서 저도 비슷하게 배열을 사용하였습니다. 방법을 설명드리자면 우선 알파벳 숫자만큼의 배열을 생성합니다. 이 배열은 boolean 타입이며 초기값으로는 false를 갖습니다. 그 후 문자열을 입력받고 문자열을 charAt을 사용해 1개씩 확인하여 해당 문자가 쓰일 경우 false의 값을 true로 선언하여 향후 중복 사용 확인에 사용했습니다. 여기서 또 중요한게 단순히 머리로만 생각하는게 아니라 노트라던지 메모장에 써서 정리하는게 중요하다는걸 알았습니다. 그동안 아무리 생각해도 뒤죽박죽이던 생각들이 a4용지에 잘 정리하니 10분만에 정리가 끝나고 이 용지를 토대로 10분도 안걸려서 코딩이 끝났습니다.
Step2. 풀이 방식
풀이 순서를 순서대로 적어보겠습니다.
전제조건) 알파벳 배열엔 기본 값 false가 들어있다.
전제조건) 한 번도 쓰이지 않은 문자는 false를 저장하고 있다.
전제조건) 쓰인 적이 있는 문자는 true를 저장하고 있다.
전제조건) boolean 배열은 27칸이며 0~26에는 알파벳의 자리가 존재한다고 생각한다. ex ) 배열[0] = 알파벳 a의 자리 배열[1] = > 알파벳 b의 자리 ...
전제조건) 관리하기 편하게 하기 위해 메서드를 사용하였으며 Scanner 클래스는 main과 check에서 쓰이므로 static으로 관리한다.
-
문자열의 첫 문자를 charAt을 통해 가져왔습니다.
-
현재 문자를 확인 후 현재 문자가 처음 쓰인 것인지 아닌지를 확인했습니다. 만약 처음 쓰였다면 false로 저장되어 있기 때문에 false값을 true로(이제 쓰인적이 있다) 바꾸어 주었습니다.또한 처음 쓰였다는 소리는 중복이 없다는 소리이므로 다음 문자 확인을 위해 continue를 해주었습니다.
num_word = word.charAt(i) - 97;
// check_word[num_word] = true;
if (check_word[num_word] == false) {
check_word[num_word] = true;
continue;
}num_word 변수에는 문자 알파벳의 자리를 구해주기 위해 -97을 해주었습니다.
- 현재 문자가 쓰인적이 있는 문자라면 이제 두 가지 경우를 생각해주어야 합니다. 하나는 현재 문자가 바로 전의 문자와 중복적으로 사용되고 있는 문자인가?(aaa이런 식으로), 나머지 경우는 현재 문자가 바로 전의 문자와 다른 모양인데 이미 쓰인적이 있는 문자인가?(aba 이런 식) 입니다.
3-1. 연속적으로 사용된 경우
else { // 현재 문자가 쓰인적이 있으면
if (word.charAt(i) == word.charAt(i - 1)) { // 현재 문자와 바로 전 문자가 같은 모양이면..즉 연속된 문자이면
continue; // 연속된 문자. 즉 안전한 문자이므로 continue
} 이미 위에서 현재 문자는 true라는 사실이 조건으로 딸려온 상태입니다. 이 상태로 만약 현재 문자와 현재 문자의 바로 전 문자가 같으면 중복된 문자, 즉 그룹 단어의 조건에 만족하므로 다음 문자를 확인합니다. 여기서 첫 문자의 경우는 바로 전이 없는데 오류가 뜨는거 아니냐 할 수 있지만 첫 문자이면 첫 if문에서 무조건 false이므로 여기까지 올 수가 없습니다.
3-2. 중복으로는 쓰였지만 연속적으로는 쓰이지 않은 경우
else { // 현재 문자와 바로 전 문자가 다른 모양이면? 현재 문자는 이미 쓰였던건데 중복으로 쓰였다는 소리니깐 이 문자는 그룹 문자가 아니다! 바로
// 메소드 종료.
return false;
}바로 전 if문이 연속적으로 쓰였냐를 묻는 if문이었고 여기서의 else문은 중복으로 쓰인적은 있지만 바로 전 문자와는 모양이 틀린 경우를 말합니다.(예를 들어 abca) 그렇기에 그룹 단어의 조건에 만족하지 않으므로 false를 리턴해주면서 메서드를 종료시켰습니다.
- 모든 문자가 조건에 맞아서 반복문을 나가게 되면 true를 리턴해주어 해당 문자가 그룹 단어라는 사실을 알려줍니다.
return true; //모든 조건을 만족하고 false에 걸리지 않았으므로.느낀 점
물론 제가 생각한 방법대로도 풀 수는 있지만 효율성과 가독성등의 면에서 너무 효율이 떨어지는거 같은걸 알 수 있었습니다. 더욱이 애초에 저는 처음 방법대로 풀지도 못 했는데, 이처럼 코드가 난잡해져 쉬운 문제도 어렵게 풀 수 있다는 걸 알 수 있었습니다. 이럴때 사용할 수 있는 여러 다른 관점에서의 접근 방식 (boolean, 배열)을 알 수 있었고 제 생각을 종이로 쓰는 것의 중요함도 알 수 있었고 여러 문법의 흐름등도 배울 수 있었던 매우 유익한 문제였습니다.
출처 : 백준 1316번 https://www.acmicpc.net/problem/1316
