[자바] 백준 1316 - 그룹 단어 체커 (java)

 문제 : boj1316

---

 

필요 알고리즘 개념

• 구현, 문자열
  
  • 문자열의 각 character를 어느정도 다룰 줄 알아야 하는 구현문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  간단히 생각해보려면 연속된 동일한 문자를 전부 하나로 줄인다고 생각해보자. 예를들어서

 

aaabbbbbbcccccddddaaaaaaa

의 경우 연속된 동일한 문자는 하나로 치면, abcda 라고 간단하게 생각해볼 수 있다.

 

  위와 같이 볼 수만 있다면, 이 문제는 이전에 나왔던 문자가 다시한번 나오는지 묻는 문제로 바꿔 생각할 수 있다. 영어 소문자는 총 26글자이다('z'-'a'+1). 따라서 26칸짜리 배열을 만든 후, 문자를 숫자로 변경하는 함수를 하나 만든다(코드의 atoi()). 그리고 'a'부터 'z'를 순서대로 0부터 26으로 변환하자.

 

  그리고 연속된 동일한 문자가 나온 횟수를 기록해준다. 예를들어 abcda인 경우 아래와 같다. 

2

1

1

1

...

이런식으로 카운팅 해줬을 때, 2이상인 값이 하나라도 나오면 그룹단어가 아니다.

 

  그럼 이제 연속된 문자를 어떻게 하나로 생각할지만 알면 된다. char bf; 를 하나 두고 이전에 나온 문자를 bf에 넣는다고 생각해보자. 그렇다면 현재 문자가 bf와 동일하다면 그냥 무시해주면 된다.

private boolean isGroupWord(String s) {
    int[] cnt = new int[LENGTH_OF_A_TO_Z];
    char bf = '\0';	// bf의 초기값은 영어 소문자에 포함안되는 어떠한 문자라도 상관없다.
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (bf==c) continue;	// 현재 문자가 bf와 동일하다면 무시
        bf = c;
        if (++cnt[atoi(c)]==2) return false;	// cnt[atoi(c)]를 1 증가시킨게 2가 되는 순간 그룹단어가 아님을 알 수 있다.
    }
    return true;
}

 

 

---

 

코드 : github

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

public class Main {
    private static final int LENGTH_OF_A_TO_Z = 'z'-'a'+1;
    private int atoi(char c) {return c-'a';}
    private boolean isGroupWord(String s) {
        int[] cnt = new int[LENGTH_OF_A_TO_Z];
        char bf = '\0';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (bf==c) continue;
            bf = c;
            if (++cnt[atoi(c)]==2) return false;
        }
        return true;
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int answer = 0;
        while (n-->0)
            if (isGroupWord(br.readLine())) answer++;
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}