[1316] 그룹 단어 체커(java)

문제

1. 무작위 String을 입력받는다(영어한정)

2. 예를들어 그 단어가 aabbcc 일경우 이는 그룹 단어 이다.

3. 하지만 aabbcca 일 경우 이는 그룹 단어가 아니다.

4. 즉 같은 알파벳이 중복해서 두번 출현하면 안된다. 여러개의 알파벳이 출연할 경우 이는 연속되어있어야한다.

5. abc, ab, aa, bb, dffg, c 는 그룹단어이며 aba, ggccg, bguub 등은 그룹단어가 아니다.

 

- 입력

1. n(회 반복)

2. 공백을 허용하지 않은 무작위 영어 String

 

-출력

1. n개의 String중 그룹 단어의 개수를 출력한다.

 

 

-해결

1. n을 입력받는다. 이후 n회 반복하는 for문을 선언한다.

cnt의 경우 n을 복사한 변수이고, 그룹 단어 체커 변수로 그룹 단어가 아닐경우 cnt를 감소시킬것이다.

int n = sc.nextInt();
int cnt = n;
for(int i=0;i<n;i++){

2. String을 선언한다.

String str = sc.next();

3. String 내 각 Character 의 출현 유무를 결정하기 위한 부울 배열을 선언한다.

boolean tf[] = new boolean[124];

4. 첫번째 char을 따서, 출현 표시를 해준다.

tf[str.charAt(0)] = true;

5. 2번째 char값 부터 다시 조사한다.

for(int j=1;j<str.length();j++){...}

6. 조사받는 char값의 아스키코드를 따고, num으로 선언해준다.

int num = (int)str.charAt(j);

 

7. 만약 조사 받는 char이 이전의 char과 같았다면, 이는 연속되었으므로 continue 한다.

if(str.charAt(j-1)==str.charAt(j)) {
    continue;
}

8. 그렇지 않을 경우 해당 번호의 부울 배열을 확인해 이전에 출현한 기록이 없다면, 이는 최초 출현이므로 true로 바꾼 후 continue 한다.

else{
    if(!tf[num]) {
        tf[num] = true;
        continue;
    }

9. 출현하였다면, 위에서 정의한 cnt 를 감소시키고 내부 반복문을 탈출한다.

else{
    cnt--;
    break;

 

10. 출력한다.

System.out.print(cnt);

- 전체 코드

import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int cnt = n;
        for(int i=0;i<n;i++){
            String str = sc.next();
            boolean tf[] = new boolean[124];
            tf[str.charAt(0)] = true;
            for(int j=1;j<str.length();j++){
                int num = (int)str.charAt(j);
                if(str.charAt(j-1)==str.charAt(j)) {
                    continue;
                }
                else{
                    if(!tf[num]) {
                        tf[num] = true;
                        continue;
                    }
                    else{
                        cnt--;
                        break;
                    }
                }
            }
        }
        System.out.print(cnt);

    }
}

 

-생각

1. 부울배열을 알파벳 개수로 고정하고 메모리 공간을 확보할 수 있었다. 하지만 이는 char값 검사시 ascii 값에 일일이 97을 빼야 한다는 단점이 있다.(대충 이런식) 결국 메모리를 확보할것인가, 연산수를 최소 할것인가의 문제였다. 나는 부울 배열의 크기가 크지 않기에 그냥 127개를 다 선언했다.

boolean tf[] = new boolean[26];
...
if(tf[num-97]){
	tf[num-97] == true;
    continue;
}

2. queue 로 입력받고, queue에서 char을 하나씩 빼서 새로운 String에 추가하는 방식, 그리고 다른 char값이 나오면 검사하는 방식도 생각해보았다. 하지만 역시 매 검사마다 String 내부 문자를 확인하기위한 for문이 필요하기에 시간이 더 오래걸릴것이라 판단했다.

 

3. 모든 검사에는 부울배열이 최우선으로 생각되어야 할것이다.