1316번(그룹 단어 체커) 파이썬(Python) 풀이 공유

들어가며

문제를 이해하자마자 문자열을 구성하는 모든 문자의 인덱스를 알아내면 문제를 풀 수 있을 것 같았다. 하지만, 3차원 리스트, 여러 반복문 사용으로 구현하기에는 꽤나 복잡할 것으로 예상되는 문제였는데, 생각보다 쉽게 통과하였다.

---

1. 문제

• 1316번 그룹 단어 체커

시간 제한	메모리 제한
2초	128 MB

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

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

1.1. 입력

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

1.2. 출력

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

1.3. 예제

입력	출력
3 happy new year	3
4 aba abab abcabc a	1

---

2. 풀이

문제를 이해하는 과정에서 문득 1부터 숫자 N 사이에 존재하는 연속적인 모든 숫자를 구하는 가우스 공식이 생각났다.(문과 출신임에도 불구하고 이럴때마다 가슴이 웅장해진다.) 이를 문자열 S에 적용시켜보면, 문자열의 길이를 L, 문자열 S에서 특정 문자의 시작과 끝 인덱스를 각각 i, j로 하고, 특정 문자의 수량을 n으로 할 때 아래 공식이 성립해야 한다.

L = n = j - i + 1

달리 말하자면, 위의 공식이 성립하면 i부터 j까지의 범위 안에 존재하는 숫자는 연속적인 상태라는 의미가 된다. 그렇다면 이 문제에서도 문자열을 구성하는 모든 문자의 인덱스가 연속적인 상태인지 확인하는 방식으로 문제에 접근하였다. 이를 위해 문자의 수량, 시작과 끝 인덱스만 알아내면 문제를 해결할 수 있다.

첫 번째 예제 중 happy에서 p의 수량(=길이)는 2, p의 시작과 끝 인덱스는 아래 그림과 같이 2와 3이다. 그리고 공식을 적용시켜보면 2 = 3 - 2 + 1로 공식이 성립하므로, 연속적인 상태인 것을 알 수 있다.

또, 두 번째 예제 중 abcabc에서 a의 수량(=길이)은 2, a의 시작과 끝 인덱스는 아래 그림과 같이 0과 3이다. 그리고 공식을 적용시켜본 결과 2 = 3 - 0 + 1로 공식이 성립하지 않으므로, 불연속적인 상태라는 것을 알 수 있다.

위 내용을 토대로 코드를 작성하면 아래와 같다.

count = int(input())
words = [list(input()) for _ in range(count)]

index_listes = [[[i for i, _ in enumerate(word) if word[i] == alphabet] 
                 for alphabet in set(word)] for word in words]

for index_list in index_listes:
    index_list = list(filter(lambda lst: len(lst) > 1, index_list))
    for lst in index_list:
        length = len(lst)
        if lst[-1] - lst[0] + 1 != length:
            count -= 1
            break

print(count)

• Line 1 : 입력받은 모든 단어를 그룹 단어로 가정하여 총 수량을 변수 count에 초기화한다. 이는 반복문을 수행하면서 공식이 성립하지 않은 경우 수량을 차감하는 방식으로 사용하였다.
• Line 2 : 총 수량 만큼 입력 받은 단어를 리스트 변수 words에 저장한다.
• Line 4 - 5 : 각 단어를 구성하는 알파벳의 인덱스를 알아내는 과정에서 반복을 최소화하기 위해 집합 구조로 중복을 제거한 후 2차원 리스트에 저장하고, 2차원 리스트의 요소를 통해 알파벳에 해당하는 인덱스를 3차원 리스트에 저장한다.
• Line 7 - 10 : for 문으로 필터링된 리스트가 담긴 2차원 리스트를 반복하면서 리스트의 수량(알파벳의 수량)을 산출한다.
• Line 11 - 13 : if 문으로 리스트의 수량과 길이가 일치하지 않은 경우 불연속적인 상태이므로 count를 차감 후 2차 반복문을 탈출하고, 나머지 1차 반복을 실행하도록 한다.
• Line 15 : 최종적으로 남은 그룹 단어의 수량을 출력한다.

---

마치며

반복문을 수행하면서 현재 알파벳과 다음 알파벳의 동일 여부를 파악하는 방식으로도 구현할 수 있을 것으로 예상된다. 알고리즘 문제를 풀면서 가끔 느끼지만, 가우스 공식과 같은 수학 공식을 다양하게 활용하여 어떠한 문제를 해결했을 때 그 쾌감이 알고리즘의 재미를 지속시켜주는 것 같다.