문제

---

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

코드

---

import java.io.*;
import java.util.*;


class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String[] input = new String[N];
		for (int i = 0; i < N; i++) {
			input[i] = br.readLine();
		}

		System.out.println(solve(N, input));
	}

	static int solve(int N, String[] input) {
		boolean[] check = new boolean[26];

		int count = 0;
		for (int i = 0; i < N; i++) {
			char[] arr = input[i].toCharArray();
			int prev = 0;
			boolean isGroup = true;
			for (int j = 0; j < arr.length; j++) {
				int idx = arr[j] - 'a';
				if (j > 0) {
					prev = arr[j - 1] - 'a';
					if (prev != idx && check[idx]) {
						isGroup = false;
						break;
					}
				}
				check[idx] = true;
			}
			if (isGroup) {
				count++;
			}

			Arrays.fill(check, false);
		}

		return count;
	}
}

문제 이해

---

• 입력으로 주어진 단어에서 "그룹 단어"의 개수를 판별해서 그 개수를 출력하는 문제이다.
• 그룹단어란 한 단어에서 1) 알파벳이 하나씩만 존재하거나, 2) 연속으로 존재하는 단어를 의미한다.
• 예를 들어 happy, hap, h는 위 조건을 만족함으로 그룹단어가 된다.
• 반대로 hapa의 경우는 a가 두번 등장함에도 불구하고 연속적으로 붙어있지 않기 때문에 그룹단어가 될 수 없다.

풀이 방법

---

• 문제 정의대로 그대로 구현하면 된다.
• 우리가 확인해야 될 것은 1) 알파벳이 이전에 나온적이 있는지 , 2) 만약 나온적이 있다면 그 알파벳이 연속적으로 존재하는지 두 개의 조건이다.
• 핵심은 26의 크기를 갖는 check배열을 사용하는 것이다. 알파벳이 등장했을 떄 이 check배열을 true로 갱신함으로써 추후 해당 알파벳이 나왔는지 판별할 수 있다.
• 위 check배열이 true인지 확인함으로써 1번 조건을 구현할 수 있다.
• 알파벳이 연속적으로 존재하는지 확인하기 위해서는 이전 알파벳 인덱스를 저장하는 prev 변수를 사용한다.
• j>0이상, 즉 prev를 초기화할 수 있는 시점부터 이전 알파벳과 현재 알파벳의 일치 여부를 확인할 수 있다.
• 위에서 언급한 check배열과 prev의 값을 각 입력의 알파벳마다 비교함으로써 그룹단어 여부를 확인할 수 있다.

핵심 포인트

---

• 위에 언급한 두가지 조건, 1) 알파벳이 이전에 나왔으며 2) 이전 알파벳과 현재 알파벳이 일치하는지만 구현하면 해결할 수 있는 문제이다.
• 문제 조건대로 그대로 구현하면 되는 문제이기에 구현에 어려운 점은 없으나, check배열과 isGroup의 초기화 시점에 유의해야 한다.

보완할 점 / 느낀 점

---

• 이전에 풀었던 문제였고, 반복문과 조건문만 잘 활용하면 되기에 크게 어려운 문제는 아니었다.
• 이전에 풀었을 때의 코드와 비교해서 메모리와 수행시간은 같았으나, 코드가 다소 난잡하게 나온 것 같다.
• 문제를 푸는 것에 더 익숙해질 필요가 있다.

참고자료

---

좀 더 간결한 버전

• 이 코드에선 prev대신 next를 사용하여 문제를 해결하였다.
• 같은 로직을 구현하긴 하나, 좀 더 간결한 느낌이다.

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int count = N;
		for (int i = 0; i < N; i++) {
			char[] str = br.readLine().toCharArray();
			count += solve(str);
		}
		System.out.println(count);

	}

	public static int solve(char[] str) {
		boolean[] appearArr = new boolean[26];

		for (int i = 0; i < str.length - 1; i++) {
			int idx = str[i] - 'a';
			
			if (!appearArr[idx]) {
				appearArr[idx] = true;
			} 
			
			int nextIdx = str[i + 1] - 'a';
			if (appearArr[nextIdx] && nextIdx != idx) {
				return -1;
			}

		}

		return 0;
	}
}