[Algorithm] 백준 1316

목록

1. 첫 번째 절망
2. 두 번째 절망
3. 성공 (풀이) <- 답만 보고 싶을 때

 

이번 문제는 혼자서 풀어 보았다.

 

여러 번의 시행착오가 있었다

문제 설명

문자가 연속해서 나오는 것을 그룹 단어라고 부른다 우리는 그 그룹 단어를 분류해야 한다.

 

ex) happy, hhaah, apple, pineapple

 

여기서 그룹 문자는 무엇일까? (정답 : happy, apple)

 

그럼 hhaah, pineapple은 왜 아닐까?

문자가 연속하지 않는다

[ hhaah는 맨 뒤에 h가 또 들어간다] 

[pineapple 은 e가 연속되지 않는다]

 

#1 첫 번째 절망

나는 이번 문제를 풀면서 지금 까지 배웠던 모든 지식을 꺼내서 적용해봤다.

처음 생각했던 것은 

어? 알파벳으로 나눠 볼까?

 

//알파벳 나누기 
//알파벳 개수 26개
int[] alpha = new int[26];

//알파벳으로 나눠서 뭘할까?

일단 알파벳으로 나눈 다음에 나오는 문자들은 중복이 허용되지 않도록

나오는 문자의 index에는 +1 해주자!!

 

int[] alpha = new int[26];

//문자열을 입력하는
//문자 하나하나당 나눠줌

char[] word = br.readLine().toCharArray();

//word배열 크기만큼 반복문을 돌음
for(int j =0; j < word.length; j++){

	//만약 앞문자가 뒤문자랑 다르면 저장
    //happy로 예를 들면 word[j] = h, word[j+1] = a
	if(word[j] != word[j+1]){
    
    	//앞문자 뒷문자 모두 각자 알파벳 배열에 인덱스에 맞게 저장
    	alpha[(int)word[j] - 'a') += 1;
        alpha[(int)word[j-1] - 'a') += 1;
    }
    
    //만약 앞문자와 뒷문자가 같다면? continue 넘어가~,왜? 난 이미 앞뒤 다 저장 했거든 그리고 할거거든
    else if(word[j] == word[j+1]){
    	continue;
    }
}

1. 각 알파벳에 매치되는 배열에 +1 해줘도 연속되지 않고 뒤에 한 번 더 나오는 문자를

잡을 수 있는 방법이 없었다.

 

2. 반복문을 돌던 j가 마지막에 돌입했을 때 word [j+1]을 할 index가 없던 것이었다....

이것이 나의 첫 절망이다

 

#2 두 번째 절망

첫 번째 뭐 그래 실수할 수 있다 다시 해보자

 

나는 생각했다. 전 로직은 마지막 index가 없었으니깐 이번엔 word [j-1]을 사용해 보자 즉 빼보자는 이야기다

int[] alpha = new int[26];

char[] word = br.readLine().toCharArray();

for(int j =1; j < word.length; j++){
	//쉽게 말해 만약 나왔던 문자라면 break해라 
    if(alpha[(int)word[j] - 'a'] > 0){
    	break;
    }
	if(word[j] != word[j-1]){
    	alpha[(int)word[j] - 'a') += 1;
        alpha[(int)word[j-1] - 'a') += 1;
    }
    
    else if(word[j] == word[j+1]){
    	continue;
    }
}

 

그런데  문제가 생겼다

 

1. 첫 번째 방법과 같다 뒤에 나오는 독립된 문자를 잡기가 어려워졌다.

ex) hoollyo 여기서 o가 총 3번 나오는 데 연속된 o에서 alpha 배열에 +2가 된다 이렇게 되니 l로 넘어가기 전에 break가 되었다.

 

 

#3 성공

문제를 계속 보다가 

아니 뮈첸 왜 Boolean을 알고리즘 풀 때 한 번도 사용할 생각을 못했을까?

나는 생각했다 Boolean을 쓰자

 

import java.io.*;
import java.util.Arrays;

public class Problem_1316 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			Boolean is = true;
			Boolean[] alpha = new Boolean[26];
			Arrays.fill(alpha, false);
			char[] word = br.readLine().toCharArray();

			alpha[(int) word[0] - 'a'] = true;
			for (int j = 1; j < word.length; j++) {
				if (word[j] != word[j - 1]) {
					if (alpha[(int) word[j] - 'a'] == true) {
						is = false;
						break;
					}
					alpha[(int) word[j] - 'a'] = true;
				}
			}
			if (is == true)
				cnt++;
		}
		System.out.println(cnt);
	}
}

알파벳에 매치되는 Boolean 배열을 만들고 false로 초기화 나온 문자는 true로 변환 

이렇게 하면 되는 것을 난......