1316번 문제 : 그룹 단어 체커

자바

1316번: 그룹 단어 체커 (acmicpc.net)

1316번: 그룹 단어 체커

보기엔 쉬워보였는데 어떤 알고리즘을 구현해야할 지 생각이 잘 안 났다.

잘 뜯어보면

1. 한 단어에서 다음단어로 바뀔 때 ! 

2. 그 다음 단어가 나온 적 없는 단어이면 된다.

 

ex) aba일 경우 a에서 b로 바뀔 때 b가 나온 적이 없었으면 되고 또 b에서 a로 바뀔 때 a가 나온 적이 없었으면 되는데 앞에 나왔으니까 이 단어는 그룹단어가 아니다.

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	int num = Integer.parseInt(br.readLine());
    	
    	int result = 0;
    	for(int i=0;i<num;i++) {
    		String str = br.readLine();
    		String alpa= "abcdefghijklmnopqrstuvwxyz";
    		int ch = 1;
    		if(str.length() == 1) {
    			result ++;
    			continue;
    		}
    		for(int j=0;j<str.length();j++) {
    			char c = str.charAt(j); //문자열을 한글자씩 찢음

   				String smj = Character.toString(c);
   				if(alpa.contains(smj)) {
   					if(j < str.length()-1)
   					if(c != str.charAt(j+1)) {
       					alpa = alpa.replace(smj, "!");
       					//System.out.println(alpa);
   					}
   					else {
   						continue;
   					}
   				}
   				else {
   					ch=0;
   					break;
   				}	
   			}
   			if(ch==1) {
   				//System.out.println(alpa);
   				result++;
   			}
    	}
    	System.out.println(result);
	}
}

나는 요렇게 했다. a~z가 담긴 문자열 alpa를 만들어놓고 주어진 단어를 한 글자씩 찢어서 c에다 넣어놓은 다음에 문자열 alph에 그 c라는 문자열이 존재하면 (alpa.contains(smj)) c다음단어와 c가 같은지를 비교. (그 사이에 j가 문자열의 맨 끝 인덱스보다 하나 적을 때만 실행한다는 조건을 추가해줌.) 비교해서 다르면 a~z가 있는 문자열에 해당 단어를 !로 바꿔버림.

j가 str.lengt()-1보다 작지 않는다는 말은 맨 끝 단어라는 말이다. 

그럴 땐 그냥 continue해서 다음 반복 진행 이 조건에 걸렸다는 말은 a~z문자열에 아직 그 단어가 있다. == 전에 나온 적이 없다.

근데 만약 다음 알파벳이 alpa라는 문자열에 없다면 그 알파벳은 이미 이전에 나온 적이 있어서 !로 바뀌어있는 거기 때문에 ch=0으로 하고 반복을 종료. 더 볼 것도 없이 그룹단어가 아님.

반복문이 종료 되었을 때 ch=1이면 그룹단어라는 말이라 result를 ++함. 

또 생각해야할 조건 ) 단어가 한 글자로 이루어졌을 때는 그룹단어니까 반복 돌 필요없이 조건으로 잡아줌. 끗 !