C언어 백준 1316번 그룹 단어 체커 해설

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

1316번: 그룹 단어 체커

 

문제

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

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

 

 

풀이

 

출제 포인트

1)ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어

-> 문자가 중복되는 것과 중복되지 않는 것의 공통점이 무엇인지 파악하고 해결하라.

 

2)ccazzzzbb는 그룹단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

 -> 이둘의 차이는 무엇인가? 그리고 둘의 구분을 무슨 기준으로 어떻게 할 지에 대한 문제를 해결하라

 

idea

 

1) aabbcc 와 abc는 같다.

 

2)abc와 aabbcca는 다르다. 하지만, aabbcca 는 abca 와 같다.

 ->  1),2)를 종합해볼 때 문자열이 연이어 중복되는지는 고려하지 않아도 된다. 따라서 문자열이 바뀔 때를

    기준으로 case를 나누면 된다.

 

3)덧셈이 아닌 뺄셈 방식으로 그룹 단어가 아닌 것을 빼준다.

 

4)알파벳 배열을 활용하여 중복을 체크한다.

▼

5)ASCII코드를 활용한다.

 

 

정답코드

#include <stdio.h>
#include <string.h>

int main()
{
	
	char input_words[101]; //문자열 배열
	int N ; //input 값 N
	scanf("%d", &N);
	
	
	int count = N; 
	
	for (int i = 0; i < N; i++)
	{
		char first = '0';
		int Alphabet[26] = {0, };
		scanf("%s", input_words);
		for (int j = 0; input_words[j] != '\0'; j++)
		{
			
			if (first != input_words[j]) 
			{
				first = input_words[j];
				Alphabet[input_words[j]-'a'] += 1;
			}

			if (Alphabet[input_words[j] - 'a'] == 2)
			{
				count -= 1;
				break;
			}
		}
	}

	

	printf("%d", count);
	return 0;
}

코드분석

 

(1)

if (first != input_words[j]) 
			{
				first = input_words[j];
				Alphabet[input_words[j]-'a'] += 1;
            }

입력된 문자열을 첫번째부터 체크하면서 문자열이 다른 경우에만 조건 이하의 절을 실행하는 코드이다.

앞서 말했듯, 문자열의 연이은 중복은 고려하지 않아도 되기 때문(aabb = ab).

따라서 바뀌는 시점만을 if문의 조건으로 하였다.

 

문자열이 다를 경우, 먼저 선언했던 Alphabet 배열의 인덱스를 추적하여 1을 넣어주는 코드를 작성하였다.

예를 들어 happy에서 h 다음 a를 판단할 때, h != a 이므로, 

first = a 가 된다. 그리고 새로운 문자가 들어온 것이므로

input_word[j] -'a' = 'h' -'a' 를 해주면 (104-97 =7) 즉 Alphabet[7] = 1 이 된다.(Alphabet[7]은 h의 index임)

 

(2)

if (Alphabet[input_words[j] - 'a'] == 2)
			{
				count -= 1;
				break;
			}

 

왜 2를 기준으로 했을까? 아까 말했던 happy 의 경우를 생각해보자. 알파벳 배열에 2라는 숫자가 들어올 수 있을까?

들어올 수 없다.  하지만 aaba의 경우는 어떨까?

j =0 일때 first 와 input_words[j]는 다르므로, if문으로 들어와 first = 'a' 로 바뀐다.

j =1 일때 first와 input_words[j] 가 같으므로, if문을 들어오지 않아 first는 그대로 'a'이다.

j =2 일때 first 와 input_words[j]는 다르므로, if문으로 들어와 first 는 'b'로 바뀐다.

j = 3 일때 first와 input_words[j]는 다르므로, if문으로 들어와 first는 'a'로 바뀐다.

이 때, Alphabet[input_words[j]-'a'] += 1; 를 주목해보면 alphabet[0] = 2 가 됨을 알 수 있다.

따라서 그룹 단어의 기준을 충족하지 못하게 되고 밑의 if 코드 조건에 맞게 되어

count -= 1; 이 되는 것이다.

 

 

 

기억해야할 점

1) 문제 분석을 잘해야한다.

처음에 중복되는 경우의 case도 분류하려고 했는데, 문제를 분석해보니, 중복되는 case를 분류하지 않아도 된다는 사실을 깨닫게 되었음.

 

2) 조건에 맞는 것을 더해도 되지만, 조건에 맞지 않는 것을 빼주는 알고리즘도 고려할 것