[BOJ] 백준 1316 그룹 단어 체커

출처: https://www.acmicpc.net/problem/1316

Approach

# 완전탐색

단어 속에 특정문자가 연속되지 않게 재등장하는지 확인해야 한다.

① 주어지는 단어에서 문자 하나하나 확인해도 된다.

② 시작되는 문자를 기준(pivot)으로 잡는다.

③ pivot을 기준으로 남은 문자를 탐색하면 같은 문자가 있는지 확인한다.

④ 같은 문자인데, pivot과 거리가 있는 경우에는

   직전에 위치한 문자와 비교해서 연속 여부를 판별한다.

 

ex) "aaaya" 라는 단어가 있다고 가정해보자.

    word[0] "a"를 기준으로 남은 문자열 "aaya"를 탐색한다.

    word[1] "a"가 word[0]이지만 거리가 1 이므로 연속된다.

    word[2] "a"도 word[0]와 같은데, 연속여부를 판단하기 위해서 직전 문자와 비교한다.

    word[3] "a"도 word[0]와 같은데, 연속여부를 판단하기 위해서

                   직전 문자 "y"와 비교되는데 다르므로 연속되지 않는다.

현재 까지 word[0] = "a" 기준으로 탐색했는데,

이러한 일련의 과정을 남은 문자에서도 동일하게 수행하면 된다.

 

단어의 길이가 최대 100 이며 각 단어마다 비교탐색해도 100 * 100 으로 TLE 발생하지 않는다.

▶ [알고리즘] 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? 

알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? (빅-오)

---

#include <iostream>
#include <string>
using namespace std;

int N, ans;
string word;

void check()
{
    int i, j;
    int key = 0;
    for (i = 0; i < word.length(); i++)
    {
        char pivot = word[i];
        for (j = i + 1; j < word.length(); j++)
        {
            // 같은 문자이면서  처음 나타난 문자와 거리가 있을 때,
            if (pivot == word[j] && j - i > 1)
            {
                // 이전 문자와 다른 경우, 연속된 같은 문자가 아니다.
                if(word[j - 1] != word[j])
                    return;
            }
        }
    }            
    ans++;
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        cin >> word;
        check();
    }

    printf("%d\n", ans);
}

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 입력받은 문자열의 개수
		int n = Integer.parseInt(sc.nextLine());
		// 그룹단어 개수를 저장할 변수 
		int count = 0;
		
		// 문자열을 입력 받는다!
		// 입력 받을때마다 바로 해당 문자열이 '그룹 단어인지 확인'
		for(int i=0; i<n; i++){
			String str = sc.nextLine();
			// 함수를 이용해 문자열만 전달한다.
			// true / false를 통해 개수를 확인
			if(checker(str)){
				count++;
			}
		}

		
		// 개수 출력
		System.out.println(count);
		
	}

	private static boolean checker(String str) {
		// 문자열은 문제 특성상 소문자로만 구성되어 있다.
		// 알파벳은 총 26개로 구성되어 있다.
		int[] alphabet = new int[26];
//		System.out.println(Arrays.toString(alphabet));
		char curCri = str.charAt(0);
		alphabet[curCri - 97]++;
		for(int i=1; i< str.length(); i++){
			curCri = str.charAt(i);
			char preCri = str.charAt(i-1);
			if(preCri != curCri && alphabet[curCri - 97] != 0){
				return false;
			}
			alphabet[curCri - 97]++;
		}
		return true;
	}
}