[Algorithm] 백준 1316

ZEDY·2024년 3월 11일

[코딩테스트] 알고리즘 문제풀이

목록 보기

7/46

문제

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

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

풀이

내가 푼 알고리즘

입력으로 주어진 문자열이 그룹 단어인지를 판별하는 함수 group_word(string)를 정의합니다. 이 함수는 주어진 문자열이 그룹 단어인지를 판별하여 True 또는 False를 반환합니다.
문자열의 첫 번째 문자를 기준으로 현재 문자를 설정하고, 이를 현재 문자셋인 string_set에 추가합니다.
문자열을 순회하면서 현재 문자와 이전 문자가 다르면, 현재 문자를 갱신합니다. 그리고 현재 문자가 이미 string_set에 존재한다면, 이는 그룹 단어가 아닌 것으로 판별하고 False를 반환합니다.
입력으로 주어진 개수(num)만큼 문자열을 입력받고, 각 문자열이 그룹 단어인지를 확인하여 그룹 단어가 아닌 경우 카운트(cnt)를 증가시킵니다.
전체 그룹 단어의 개수는 입력으로 주어진 개수(num)에서 그룹 단어가 아닌 문자열의 개수(cnt)를 뺀 값으로 출력됩니다.

이 알고리즘은 입력으로 주어진 문자열이 그룹 단어인지 아닌지를 판별하여 카운트하는 것으로, 각 문자열의 길이에 비례하는 시간 복잡도를 가집니다.

코드

num = int(input())
cnt = 0

def group_word(string):
    current = string[0]
    string_set = set()
    string_set.add(current)
    for i in range(1, len(string)):
        if current != string[i]:
            current = string[i]
            if current not in string_set:
                string_set.add(current)
            else:
                return False




for _ in range(num):
    string = input()
    if group_word(string) is False:
        cnt += 1
print(num - cnt)

개선

주어진 코드에서 개선할 수 있는 몇 가지 점이 있습니다:

변수명 수정: current라는 변수명은 현재 문자를 나타내는데 어느 정도 의미가 있지만, 보다 명확한 변수명을 사용하면 코드를 이해하기 쉬워집니다. 예를 들어, current 대신 previous_char 또는 prev_char와 같이 이전 문자를 나타내는 이름을 사용하는 것이 좋습니다.
함수명 변경: group_word 함수는 실제로 그룹 단어를 체크하는 것이 아니라, 그룹 단어가 아닌 경우를 체크하고 있습니다. 함수명을 is_group_word와 같이 명시적으로 변경하면 더 이해하기 쉽습니다.
현재 문자 체크 수정: 현재 문자가 이미 string_set에 존재하는지 확인하는 코드에서 if current not in string_set를 사용하고 있습니다. 이 조건은 이미 string_set에 존재하지 않을 때 True를 반환합니다. 그러나 이 경우에는 그룹 단어인지를 판별하는 것이므로, 이 조건을 if current in string_set로 수정하는 것이 더 명확합니다.
중복 코드 제거: 함수 내에서 문자열을 입력받고 그룹 단어 여부를 확인하는 부분이 중복되어 있습니다. 이를 함수 내부에서 한 번만 입력받고 그룹 단어 여부를 판별한 후 결과를 출력하도록 수정할 수 있습니다.
메인 루프 변수명 변경: 메인 루프에서 사용하는 _는 일반적으로 반복 변수를 사용하지 않을 때 사용되는 관습적인 변수명입니다. 그러나 이 경우에는 반복 변수를 사용하므로 _ 대신 다른 의미있는 변수명을 선택하는 것이 좋습니다.

아래는 위의 개선 사항을 적용한 코드 예시입니다:

num = int(input())

def is_group_word(s):
    prev_char = s[0]
    char_set = set()
    char_set.add(prev_char)
    
    for i in range(1, len(s)):
        if prev_char != s[i]:
            prev_char = s[i]
            if prev_char in char_set:
                return False
            char_set.add(prev_char)
    
    return True

cnt_non_group_word = 0

for _ in range(num):
    input_string = input()
    if not is_group_word(input_string):
        cnt_non_group_word += 1

print(num - cnt_non_group_word)