[백준] 1316번: 그룹 단어 체커

Chaejung·2022년 4월 25일

python 알고리즘

알고리즘_Python

목록 보기

5/22

1316번

문제 분석

처음에는 알고리즘 분류를 신경쓰지 않고 냅다 문제 풀이부터 하려고 했는데 이제는 알고리즘 분류를 꼭 확인한다. 그래야지 문제 접근 시간이 줄어든다.

<알고리즘 분류>: 구현, 문자열

경험 상 문자열 문제의 키워드는 정렬, 갯수, 분류, 회문 등이 있는데,

문제에 정렬이란 단어가 없지만 정렬을 쓴다면 쉽게 풀 수 있었다.

처음 이 문제를 봤을 때는 단순히 다른 글자가 등장하면 끊어서 따로 저장해야하나라는 생각을 했고 그렇게 접근했더니 손도 못 댔었다.

정렬이 익숙해진 후 몇 일 뒤에 이 문제도 정렬을 써보면 어떨까하는 쪽으로 접근했더니 풀 수 있었다.

코드 설명

isGroup()은 그룹 단어가 맞는지 boolean으로 반환하는 함수.

howManyGroup()은 해당 단어를 같은 문자끼리 쪼갰을 때 그룹의 갯수를 반환하는 함수.

그리고 isGroup()에서 입력받은 단어 그대로 그룹의 갯수를 구해보고,
입력받은 그룹을 정렬해서 같은 문자열끼리 모인 다음, 새로운 단어의 그룹의 갯수를 구한다.

만약 입력받은 단어가 그룹 단어라면 정렬 전 후 그룹의 갯수가 동일할 것이고,
아니라면 달라질 것이다.

ex)
hello // 정렬 전 h, e, ll, o 4개
ehllo // 정렬 후 e, h, ll, o 4개
pandas // 정렬 전 p, a, n, d, a, s 6개
aadnps // 정렬 후 aa, d, n, p, s 5개

🎆코드


# 해당 단어를 같은 문자끼리 쪼갰을 때 그룹의 갯수를 반환
def howManyGroup(str):
    count = 0
    for i in range(len(str)-1):
    	# 단어의 처음부터 돌면서 다음 문자열과 동일한지 구별, 다르면 그룹 추가
        if str[i] != str[i+1]:
            count += 1
    return count + 1

# 그룹 단어가 맞는지 boolean으로 반환
def isGroup(str):
    beforeSorted = howManyGroup(str)
    afterSorted = howManyGroup(sorted(str))
    if beforeSorted == afterSorted: return True
    else: return False

howManyGroupStr = 0
# 입력 갯수를 입력받고, 그 횟수만큼 단어를 입력 받아 총 그룹 단어의 갯수 증가시키기
for i in range(int(input())):
    if isGroup(input()):
        howManyGroupStr+=1

print(howManyGroupStr)

우수 코드와 비교하기

result = 0
for i in range(int(input())):
    word = input()
    if list(word) == sorted(word, key=word.find):
        result += 1
print(result)

정렬을 쓴 건 유사하지만, word.find가 꽤 생소했다.

<find()>

str.find(찾을 문자, 시작점, 종료점)

찾을 문자가 처음 위치한 자리의 값을 반환하고, 없으면 -1을 반환한다.

str 중 's'가 처음 위치한 자리
thisispython.find('s')
>>> 3

str 중 4~7번째 사이에 's'가 위치한 자리
thisispython.find('s', 4, 7)
>>> 5

str 중 'f'가 처음 위치한 자리
thisispython.find('f')
>>> -1

문법은 이해가 됐지만 코드 상에서 어떻게 활용됐는지 이해하기 어려워서 print로 찍어보았다.