[백준알고리즘/문자열] 1316번 문제 : 그룹 단어 체커(자바/JAVA)

안녕하세요

백준 알고리즘 단계별로 풀어보기 7단계 1316번 문제 그룹 단어 체커를 풀어봤습니다

처음에 문제가 이해가 안 되어서 여러 번 읽어 본 문제입니다

몇 번 읽고 예시를 찬찬히보다보니 이해가 됐습니다

연속되지 않은 경우 같은 알파벳이 또 나오는 경우 그룹 단어가 아니게 됩니다

그렇게 그룹 단어가 아닌 것을 제외하면서 푸는 문제입니다

제가 풀은 방식들을 설명하겠습니다!

 

---

문제

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

 

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

 

 

---

 

 

문제 풀이

첫 번째 풀은 방법입니다

몇 번 제출해서 틀리다가 처음 정답을 맞췄을 때 코드입니다

알파벳 배열을 만들어서 그룹 단어인지 아닌지 체크하는 방식입니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언 및 N 변수 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		int count = N;
		
		// 그룹단어체크용 배열 선언
		boolean[] alphabet = new boolean[26];
		
		// 반복문 시작
		for(int i = 0; i < N; i++)
		{
			// 단어 입력
			String str = br.readLine();
			
			// 배열을 false로 채워넣는다
			Arrays.fill(alphabet, false);			
			alphabet[str.charAt(0) - 97] = true;
			
			// 반복문 시작
			for(int j = 1; j < str.length(); j++)
			{
				// 앞뒤가 다른 경우
				if(str.charAt(j) != str.charAt(j - 1)) {
					// 이미 true처리가 되어있으면 그룹 단어가 아니므로 count--;
					if(alphabet[str.charAt(j) - 97] == true) {
						count--;
						break;
					}
					// false로 되어있으면 true로 변경
					else {
						alphabet[str.charAt(j) - 97] = true;
					}
				}					
			}
		}
		
		// 결과 출력
		System.out.print(count);
	}
}

 

---

두 번째 풀은 방법입니다

방식 자체는 첫 번째 방법과 다르지 않지만 다른 분들이 풀은 것을 바탕으로 조금 더 다음어서 제출했습니다

그룹 단어 체크를 하는 부분을 메서드로 빼내어서 그룹 단어 갯수를 구합니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 선언 및 반복변수 N 선언
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		int N = Integer.parseInt(br.readLine());
		int count = 0;
		
		// 반복문 시작
		for(int i = 0; i < N; i++)
		{
			// 그룹단어체크 메서드 호출 -> 그룹단어의 경우 count++;
			if(isGroup(br.readLine()))
				count++;
		}
		
		// 결과 출력
		System.out.print(count);
	}
	
	// 그룹단어체크 메서드 선언
	static boolean isGroup(String str) {
		// 그룹단어체크 변수 선언
		boolean check = true;			// 기본 true
		int[] alphabet = new int[26];	// 중복체크용 배열
		int pre = -1, cur = -1;			// 이전단어, 현재단
		
		// 단어갯수만큼 반복시작
		for(int i = 0; i < str.length(); i++)
		{
			// 현재단어
			cur = str.charAt(i) - 97;
			
			// 현재단어, 이전단어가 다른 경우 -> 이전단어가 -1이 아니면 알파벳배열 -1로 변경
			if(cur != pre) {
				if(pre != -1)
					alphabet[pre] = -1;
				
				// 이전단어를 현재단어로 변경
				pre = cur;
			}
			
			// 현재단어의 알파벳배열이 -1로 나오면 이전에 한 번 변경이 됐으므로 그룹단어가 아님
			if(alphabet[cur] == -1) {
				check = false;
				break;
			}
		}
		
		return check;
	}
}

 

이제 속도 비교를 해보겠습니다!

 

---

 

속도 비교

첫 번째 제출한 정답은 많이 다듬지 않아서 시간이 많이 든 것을 볼 수 있습니다

두 번째 제출한 정답이 시간이 많이 절약됩니다

하지만 메모리차이 무엇...

첫 번째 제출한 정답이 메모리는 더 적게 드네요;;

 

두 번째 다듬은 답안이 백준알고리즘 상위권에 올랐습니다!!

처음으로 제출한 답안이 상위권에 올라서 자랑해봅니다 헿

 

이상 백준 알고리즘 1316번 그룹 단어 체커를 풀은 내용이었습니다

여기까지 문자열 단계의 모든 문제를 풀었습니다! 짝짝짝

다음 글에서는 기본 수학 1단계를 풀어보겠습니다!!

 

이전 문제 : 2021.05.18 - [알고리즘/알고리즘JAVA] - [백준알고리즘/문자열] 5622번 문제 : 다이얼(자바/JAVA)