문제
실버는 어려워
두 번째로 맞이하는 실버5단계 문제.. 쉽지 않다.
이번 문제는 문제를 풀면서 겪었던 삽질에 대해 좀 길게 써보려고 한다.
코테를 공부할 때는 대표적인 알고리즘 코드를 외우다싶이 반복해서 비슷한 문제에 써먹는 게 최고의 방법이라지만,
내가 다 풀 수 있을 것 같은데 자꾸만 안 되는 답답한 상황에 그만 자존심을 못 버리고 삽질을 해버렸다.
지나고 보니 정답률이 53%나 되는 생각보다 간단한 문제였지만, 이렇게 느끼는 것도 삽질이 없었다면 불가능하지 않았을까 싶고, 나중에 오래 기억에 남을 테니까 오히려 좋은 거 아닌가 하는 긍정적인 생각으로 마인드셋을 또 해본다. 하하
처음 구현한 코드
이 문제를 접하고 처음 설계한 알고리즘은 맞았는데, 구현 능력이 낮아서 실패했다.
내가 알고리즘을 설계할 때 떠올렸던 생각의 흐름을 기록하고 넘어가겠다.
먼저 단어를 N번 입력받았으므로 가장 바깥에 반복문이 N번 실행되어야 하고,
단어마다 한 문자씩 검사해야 하므로 안쪽에 단어 길이만큼의 for문이 하나 더 위치해야 한다.
이전에 나온 알파벳인지 확인해야 하므로 문자 하나를 추출할 때마다 해당 알파벳이 등장했는지 아닌지 기록한다.
- 길이 26의 int 배열 사용, 모든 요소 0으로 초기화
- 처음 등장하는 알파벳이라면 1삽입, 이미 1이라면 이전 문자와 비교 -> 같으면 통과 / 같지 않으면 그룹 단어가 아님
여기까지 설계하고 '같으면 통과 / 같지 않으면 그룹 단어가 아님'을 어떻게 구현해야 할지 전혀 감히 안 왔다.
그래서 일단 에시 문자열을 하나 정해서 내가 짠 알고리즘을 손코딩해봤다.
직접 i=0, i=1, ...인 경우 어떤 코드를 거쳐야할지 생각하며 노트에 써보았다.
예) 단어가 aabcad인 경우: arr1[] 모두 0으로 초기화, i=0일 때 arr2[0]=charAt(0), j=0일 때 if(charAt(0)=a) arr1[0]=1 ...
그렇게 완성한 알고리즘 :
- 알파벳이 처음 등장 -> 배열에서 해당 알파벳의 인덱스를 1로 만들기, 다음 문자 계속 검사
- 알파벳이 중복
- 이전 문자와 같음 -> 다음 문자 계속 검사
- 이전 문자와 다름 -> 그룹 단어가 아님
그리고 바로 코드를 짰다.
필요한 변수나 배열은 미리 생각해두었으므로 그때그때 선언해서 썼다.
//굳이 이해하지 않아도 됩니다..
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//앞서 나온 글자가 연속하지 않는 것을 발견하면 그룹 단어로 세지 않기
int count = 0; //그룹 단어 수를 저장할 변수
int[] arr1 = new int[26]; //알파벳이 등장했는지 확인하기 위한 배열
for(int i=0; i<arr1.length; i++) { //모두 0으로 초기화
arr1[i] = 0;
}
int N = Integer.parseInt(br.readLine()); //단어의 개수 입력받기
for(int k=0; k<N; k++) {
String str = br.readLine();
//한 문자열마다 arr2 새로 생성 : 이전 문자와의 비교를 위한 공간
char[] arr2 = new char[str.length()];
for(int i=0; i<str.length(); i++) { //단어마다 실행
//현재 문자 저장
arr2[i] = str.charAt(i);
//현재 알파벳 자리에 1 저장
for(int j=0; j<26; j++) { //추출한 문자가 어떤 알파벳에 해당되는지 for문으로 검사
if(str.charAt(i) == (char)(j+97)) {
if(arr1[j] == 0) { //처음 등장한 알파벳
arr1[j] = 1;
break;
}else if(arr1[j] != 0) { //이전에 등장한 적이 있는 알파벳
if(arr2[i-1] != arr2[i] && i<str.length() && i>0) { //바로 전 문자와 다르다면
//해당 문자열은 더 볼 필요 없이, 다음 문자열 검사하면 됨
//첫 번째 for문까지 한꺼번에 탈출하기
i+=(str.length()-i);
break;
}else if(arr2[i-1] == arr2[i] && i<str.length() && i>0) { //바로 전 문자와 같다면
if(arr2.length == str.length()) //arr2가 모두 채워졌다면 count++
count++;
//다음 문자 계속 검사하기
break;
}
}
}
}
}
}
bw.write(count+" ");
bw.close();
}
}IDE에서 예제를 입력해보니 실행 결과는 전혀 맞지 않고, 어떤 단어에서는 접근 불가능한 인덱스 에러가 발생하기도 했다.
그래서 정확한 원인 파악도 안된 채 조건문에 and연산자로 여러 조건을 붙여보기도 하고, 처음 등장한 알파벳이라면 for문을 두 번이나 탈출해야해서 두 번째 for문에 break문을 썼다 지웠다 반복.. 이상하게 디버깅을 했다.
- 이 코드의 문제점 + 개선 방안
- 추출한 문자가 어떤 알파벳인지 굳이 for문을 사용해서 26번 확인하고있다. 이 부분은 일일이 a~z까지 탐색할 필요 없이 추출한 문자의 유니코드로 바로 알 수 있다.
- 알파벳 체크용 배열을 int로 사용하고있다. int보다 boolean이 효율적이다. boolean을 사용하면 0으로 초기화하는 과정이 필요없어진다.
- 추출한 문자를 char타입 그대로 사용하고 있다. 추출한 문자를 가지고 어떤 작업을 하는지 생각해보면, 아스키코드(int형)로 받는 게 더 효율적일 것이다. 어차피 이전 문자와 같은지만 체크하면 되고, 배열의 인덱스로도 쓰여야한다.
- 단어가 그룹 단어인지 체크하는 코드를 별도의 함수로 만드는 게 낫다. for문이 세 번이나 중첩되어있을 정도로 복잡한데도 이미 짠 코드를 수정하면 못 알아보게될까봐 별도의 함수로 빼지 않았다. 별도의 함수로 빼서 boolean형으로 선언하면 return false를 이용해 그룹 단어가 아님을 표현할 수 있다.
정답 코드 1
위의 개선방안을 모두 수용해서 수정한 코드이다.
checker함수 설명 :
- 알파벳이 처음 등장 -> checkAlpha배열에서 해당 알파벳의 인덱스를 true로 만들기, pre를 now로 변경, 다음 문자 계속 검사
- 알파벳이 이전에 나온 적 있음
- 이전 문자와 다름 -> 그룹 단어가 아님 (return false)
- 이전 문자와 같음 -> 다음 문자 계속 검사
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int count = 0;
int N = Integer.parseInt(br.readLine());
for(int i=0; i<N; i++) {
if(checker(br.readLine())) {
count++;
}
}
bw.write(count+" ");
bw.close();
}
static boolean checker(String str) {
int pre = -1; //이전 문자를 저장할 pre변수 선언, -1로 초기화
boolean[] checkAlpha = new boolean[26]; //알파벳이 이전에 등장했는지 확인할 boolean타입의 checkAlpha배열 선언. 초기화하지 않아도 초기값 모두 false
for(int i=0; i<str.length(); i++) {
int now = str.charAt(i);
if(checkAlpha[now-97]==false) { //알파벳이 처음 등장
checkAlpha[now-97] = true; //해당 알파벳의 인덱스를 true로 만들기
pre = now;
continue;
}else { //알파벳이 이전에 나왔음
if(pre != now) { //이전 문자와 다름 -> 그룹 단어 아님
return false;
}else { //이전 문자와 같음 -> 다음 문자 계속 검사
continue;
}
}
}
return true;
}
}
정답코드 2
정답코드 1과 검사 순서가 반대지만 결론적으로 동작 방식은 같다.
checker함수 설명 :
- 이전 문자와 다름
- 알파벳이 처음 등장 -> checkAlpha배열에서 해당 알파벳의 인덱스를 true로 만들기, prev을 now로 변경, 다음 문자 계속 검사
- 알파벳이 이전에 나온 적 있음 -> 그룹 단어가 아님 (return false)
이전 문자와 같음 -> 다음 문자 계속 검사
import java.util.*;
import java.io.*;
//aabca
public class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int count = 0;
int N = Integer.parseInt(br.readLine());
for(int i=0; i<N; i++) {
if(checker(br.readLine())) {
count++;
}
}
bw.write(count+" ");
bw.close();
}
static boolean checker(String str) {
int prev = -1; //이전 문자 저장할 변수
boolean[] checkAlpha = new boolean[26]; //이전에 나온 알파벳인지 확인할 배열
for(int i=0; i<str.length(); i++) {
int now = str.charAt(i); //현재 문자 저장할 변수
if(prev != now) { //바로 전 문자와 같지 않다면 이전에 나왔던 알파벳인지 검사해야 함
if(checkAlpha[now-97] == false) { //처음 등장하는 알파벳이면
checkAlpha[now-97] = true; //true로 변경
prev = now;
}else { //이전에 등장했던 알파벳이면
return false; //그룹 단어가 아니므로 false 리턴
}
}else { //바로 전 문자와 같다면
continue; //계속 다음 문자 검색하면 됨
}
}
return true;
}
}
Note
- 아직 어떻게 하면 모든 경우의 수를 안 빼먹고 설계할 수 있는지는 모르겠다. 그래서 그냥 그 부분은 신경쓰지 않고 짜보는 걸로. 웬만한 알고리즘을 다 습득하고 나면 자연히 알게되지 않을까?
- [Cannot make a static reference to the non-static method checker(String) from the type Main] 에 : static으로 선언된 메서드에서는 static으로 선언된 메서드만 불러올 수 있다. static, non-static 메서드는 다른 메모리 영역에서 생성되어 동작하기 때문이다.
- checkAlpha 배열을 int타입으로 선언해서 모두 0으로 초기화한 후 사용한 경우 vs boolean타입으로 선언한 경우 성능 차이. (boolean이 위)
'BOJ' 카테고리의 다른 글
| [백준 2738번/JAVA] 행렬 덧셈 (0) | 2024.03.13 |
|---|---|
| [백준 25206번/JAVA] 너의 학점은 (0) | 2024.03.13 |
| [백준 2941번/JAVA] 크로아티아 알파벳 (0) | 2024.03.11 |
| [백준 1157번/JAVA] 단어 공부 (0) | 2024.03.11 |
| [백준 10988번/JAVA] 팰린드롬인지 확인하기 (0) | 2024.03.11 |