[백준] 1316. 그룹 단어 체커

1316번: 그룹 단어 체커

---

오늘은 너무 코앞으로 다가온 정처기 시험 준비때문에 2문제만 풀었는데, 이 문제가 시간을 많이 잡아먹었다.
먼저 풀었던 '2941.크로아티아 알파벳' 문제와 비슷한데, 미리 길이가 정해져있지 않아서 슬라이싱은 활용할 수 없었다. 그래서 연속된 숫자가 어디까지 이어지나 확인해보고자, 투 포인터 알고리즘을 이용해서 풀어보려고 했다.

# 1316 그룹 단어 체커
# 이거 dfs로도 풀 수 있을 것 같긴 한데,
# 투 포인터로 풀어보자.
# 풀고 나서 다른 사람들 풀이를 한번 봐야지.

def is_group(w):
    MAP = [0 for _ in range(26)]

    i = 0
    while i < len(w):
        # 이미 한번 숫자가 나온 경우라면
        # 그룹 단어가 될 수 없으므로 False를 반환한다.
        if MAP[ord(w[i]) - 97] > 0:
            return False

        else:
            MAP[ord(w[i]) - 97] = 1
            cnt = 0
            # 투 포인터
            for z in range(i+1, len(w), 1):
                if w[z] != w[i]:
                    break
                else:
                    cnt += 1
            MAP[ord(w[i]) - 97] += cnt
            # i가 반복문 다음 단계로 넘어가기 위해 +1 해줘야 하는데
            # 거기에 연속된 수가 있는 만큼 넘어가야 하므로 += cnt + 1
            i += cnt + 1
    return True

N = int(input())
count = 0
for i in range(N):
    if is_group(input()) == True:
        count += 1

print(count)

우선 알파벳 길이만큼의 0으로 채워진 배열을 하나 만들어두고, 연속된 알파벳이 나온 횟수만큼 배열의 해당 알파벳 인덱스('a'의 위치가 인덱스 0번이 되도록 아스키코드로 변환 후 97을 빼준 인덱스 값에 넣었다.)의 값에 더해줬다.

만약 반복문을 돌던 중, 이전에 연속된 값이 이미 1개 이상 나온 값이 다시 나오게 된다면 그룹 단어가 아니니 False를 return해주도록 했다. 그렇지 않다면 일단 1번 나온 알파벳 값만큼 MAP의 해당 위치에 더해주고, 그 후 반복문을 한번 더 돌려서 알파벳이 어디까지 연속되는지 알아본 후(투 포인터), 연속되는 수만큼 i에 더해 연속된 부분 다음부터 다시 반복문을 돌릴 수 있도록 했다.

pycharm으로 디버깅을 시도했는데 F7(step into)를 눌러도 그냥 실행이 종료되버려서, 오류를 정확히 알기 위해 pythontutor(https://pythontutor.com/)에서 돌리면서 어떤 부분이 잘못됐었는지 오류를 수정해갔다.

Python Tutor: Learn Python, JavaScript, C, C++, and Java by visualizing code

++) 다른 분께서 훨씬 깔끔하게 푸신 걸 보고 많이 배웠다.
따로 MAP 배열같은 걸 만들지 않고, 슬라이싱만 활용해서 푸셨는데 만약 i와 i+1이 다른 문자일 경우(연속되지 않을 때) word[i+1:](i+1인덱스부터 끝까지)를 새로 단어로 만들고 해당 단어 안에 i인덱스의 알파벳이 포함되어 있다면 그룹 단어가 아닌 걸로 판명하는 방식이다.(https://ooyoung.tistory.com/79)

백준 1316번 [파이썬 알고리즘] 그룹 단어 체커