백준 알고리즘 No.1316 그룹 단어 체커
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.
출력
첫째 줄에 그룹 단어의 개수를 출력한다.
체감 난이도: ★★★
알고리즘을 풀어본 적도 없는데다 기억도 가물가물한 파이썬으로 풀려니 더 감이 안잡혔다. 체감상 이번 스터디 문제 중 가장 어려웠음..
Code
n = int(input())
checker_list = []
count = 0
# n개의 단어를 입력받아 리스트에 저장
for i in range(n):
input_word = input()
checker_list.append(input_word)
# Group 단어인지 판별하는 함수
def group_checker(word):
already_group = set()
for j in range(len(word)):
if word[j] != word[j-1] and word[j] in already_group:
return False
already_group.add(word[j])
return True
# Group 단어의 개수 체크
for k in range(n):
if group_checker(checker_list[k]) == True:
count += 1
print(count)
Solution
aaabbaa처럼 이미 그룹이 끝난 문자열 이후에 중복된 문자가 나올 것을 효과적으로 판별하기 위해 중복된 원소를 허용하지 않는 set()을 활용했다.
✔ set()이란?
- 파이썬에서 제공하는 내장 자료형
- 중복된 원소를 허용하지 않는다.
- 원소들 간에 순서가 없이 저장되어 있다.
- 변경 가능한 자료형이다. (새로운 원소를 추가, 삭제 가능)
group_checker(word) 함수를 통해 각 문자가 앞의 문자와 같은지 체크하고 다르면 False, 같다면 해당 문자를 already_group에 추가하도록 하였다. 또한, 이미 있는 문자가 재등장한 경우를 체크하기 위해 word[j] in already_group 식을 통해 False 처리를 하였다.
혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃
