[Python 파이썬] 백준 1316번 - 그룹 단체 체커

2023년 4월 30일

문제 링크 : 백준 1316 - 그룹 단체 체커

문제

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

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

입력

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

출력

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

알고리즘 분류

• 구현
• 문자열

 

---

문제 접근

문자열 내에서, 특정 문자가 한번이라도 등장했다면 특정 문자가 연속으로 재등장하는게 아닌 다른 문자 이후에 앞에서 등장했던 문자가 재등장하면, 그룹문자가 아닌 것이다.

그 어느 문자라도 ‘불연속적인 재등장’ 사례가 존재하면 그룹문자가 아닌것. 그 외엔 그룹문자이다.

예)

aabbbb : a 문자가 첫 등장 이후 연속적으로 1번 더 등장함. 그 다음 b 문자가 등장하고, 연속적으로 3번 더 등장함 ⇒ 그룹문자 성립

aabbba : a 문자가 첫 등장 이후 연속적으로 1번 더 등장함. 그 다음 b 문자가 등장하고, 연속적으로 2번 더 등장함. 이후 ‘앞에서 등장했던 a가 불연속적으로 재등장함 ⇒ 그룹문자 아님

abc : a문자 첫 등장 이후 b 문자 등장, 후에 c 문자 등장 : 문자의 불연속적인 재등장이 없기에 그룹문자 성립

그룹문자인지 아닌지 판별은 어떻게 할 수 있을까.

나는 다음과 같이 접근해보기로 했다.

1. 입력받은 문자열을 앞에서부터 탐색해, 불연속적인 문자가 등장하면 임시 배열에 담아둔다. → a가 등장하다 b가 첫 등장하면 불연속적인 문자가 등장했으니, b를 배열에 담아두는 방식
2. 해당 과정을 끝까지 마친 후, 만약 입력받은 문자열이 ‘그룹문자’라면 임시 배열에 대해 중복 요소를 제거시켰을 때 배열의 크기 차이가 없을 것이라고 판단. 임시 배열의 크기와 중복 요소 제거한 임시 배열의 크기가 다르다면, 해당 문자열은 ‘그룹문자가 아닐 것'이다.

---

순서도

1. 단어의 개수 N을 입력받음

2. N만큼 반복. 각 반복마다 단어를 입력받음.

3. 입력받은 단어는 리스트 형태로 arr에 삽입. arr 배열 내에서 '불연속적인 문자가 나올 때'마다 담아둘 _arr 리스트 선언

4. arr을 처음부터 탐색.
    4-1. 0번째 인덱스를 탐색할 땐, 비교대상이 없으니 _arr에 대입
    4-2. 현재 탐색중인 i번째 인덱스 문자와 i-1번째 인덱스 문자가 다르다면 _arr에 해당 문자 대입(불연속적인 문자 등장)

5. 최종 _arr 리스트의 길이와 '중복을 제거한 _arr문자 (set(_arr)) 의 길이가 같다'면, 해당 문자는 그룹단어. 다르다면 그룹문자 아님.

6. 2~5 과정을 N번 반복하여 최종 그룹단어 개수를 출력.

---

입력 예제

4
aba
abab
abcabc
a

aba 문자열을 예로 들어보자.

문자열 맨 앞에서부터 탐색을 진행할 것이다. a 문자는 첫 등장했으니 _arr 리스트에 담아둔다. 후에 등장한 문자는 b로 이전 문자와 다른, 불연속적인 문자이기에 _arr 리스트에 담아둔다. 이후 등장한 a 또한 이전 문자 b와 다른 문자이기에 불연속적인 문자 등장에 의거, _arr 리스트에 담아둔다.

과정을 끝마치면 _arr = [’a’,’b’,’a’] 일 것이고, 길이는 3이다. _arr 리스트에서 중복요소를 제거하면? set(_arr) = [’a’,’b’]로 길이가 2이다. 이 둘의 길이가 다르다는 것은, 앞에서 말한 대로 앞에서 등장했던 문자가 불연속적으로 재등장했었음을 보여준다.

abab, abcabc도 위와 같은 이유로 그룹문자가 아니다.

a는 문자 a의 등장 이후 불연속적인 재등장이 없으니 그룹문자 조건에 충족한다.

출력 예제

1

 

 

---

주의할 점

1. 문자열의 0번째 인덱스 요소는 먼저 _arr 리스트에 삽입하고 로직을 수행해야 한다. 까먹고 했다간 arr[-1]이 arr[0]과 같은지 검사하는 어이없는 로직으로 수행되기에 조심할 필요가 있다.

---

전체 코드

# 1316

'''
예상 풀이
1. 단어의 개수 N을 입력받음
2. N만큼 반복. 각 반복마다 단어를 입력받음.
3. 입력받은 단어는 리스트 형태로 arr에 삽입. arr 배열 내에서 '불연속적인 문자가 나올 때마다 담아둘 _arr 리스트 선언
4. arr을 처음부터 탐색.
4-1. 0번째 인덱스를 탐색할 땐, 비교대상이 없으니 _arr에 대입
4-2. 현재 탐색중인 i번째 인덱스 문자와 i-1번째 인덱스 문자가 다르다면 _arr에 해당 문자 대입(불연속적인 문자 등장)
5. 최종 _arr 리스트의 길이와 '중복을 제거한 _arr문자 (set(_arr)) 의 길이가 같다면, 해당 문자는 그룹단어. 다르다면 그룹문자 아님.
6. 2~5 과정을 N번 반복하여 최종 그룹단어 개수를 출력.
'''
# 1. 단어의 개수 N을 입력받음
N = int(input())

result = 0 # 그룹 단어의 개수를 입력받을 result 변수

#2. N만큼 반복. 각 반복마다 단어를 입력받음.
for _ in range(N):
    # 3. 입력받은 단어는 리스트 형태로 arr에 삽입.
    arr = list(input())
    # arr 배열 내에서 '불연속적인 문자가 나올 때마다 담아둘 _arr 리스트 선언
    _arr = []

    # 4. arr을 처음부터 탐색.
    for i in range(len(arr)):
        # 4-1. 0번째 인덱스를 탐색할 땐, 비교대상이 없으니 _arr에 대입
        if i == 0:
            _arr.append(arr[i])
        # 4-2. 4-2. 현재 탐색중인 i번째 인덱스 문자와 i-1번째 인덱스 문자가 다르다면 _arr에 해당 문자 대입(불연속적인 문자 등장)
        else:
            if arr[i] != arr[i-1]:
                _arr.append(arr[i])
    
    # 5. 최종 _arr 리스트의 길이와 '중복을 제거한 _arr문자 (set(_arr)) 의 길이가 같다면, 해당 문자는 그룹단어. 다르다면 그룹문자 아님.
    if len(_arr) == len(set(_arr)):
        result += 1

# 6. 2~5 과정을 N번 반복하여 최종 그룹단어 개수를 출력.
print(result)

---

풀이 후기

확실한건 효율적인 코드는 아닐 것이다. 창의적인 방법으로 푼 다른 분들의 코드도 한 번 봐야겠다.