[백준]_1316번 : 그룹 단어 체커(파이썬 and C언어)

 

1316번: 그룹 단어 체커

전략

조금 까다로워 보이는 문제이다. 어느 알파벳이 연속으로 배치되어 있는지 알아내야 하고 또한 한 번만 쓰인 알파벳이면 연속이라고 가정해야 한다. 파이썬은 다행히도 문자열을 원하는 인덱스 범위 안에서 자를 수 있다. 따라서 인덱스 i와 i+1의 요소가 같다면 i를 1 증가시키고 만약 같지 않다면 문자를 [i+2:]로 묶는다. 예를 들어 apple을 [2:]로 묶으면 ple가 된다.

---

   

시도 1(Python)

import sys
input=sys.stdin.readline
bug, cnt=0, 0
for _ in range(int(input())):
    cnt+=1
    el=str(input().strip())
    for i in range(len(el)-1):
        if el[i]!=el[i+1]:
            new=el[i+1:]
            if new.count(el[i])>0:
                bug+=1
                break
print(cnt-bug)

<평가> 전체 입력된 문자열 개수에서 생긴 bug수를 빼주었다. bug는 el [i+1:]에 el [i]가 존재하면 증가하고 탈출한다. 하지만 우리가 짜고 있는 언어는 파이썬 아닌가? 조금 더 간결하게 다음과 같이 줄일 수 있을 것 같다.

---

수정

import sys

input = sys.stdin.readline
cnt = 0
for _ in range(int(input())):
    cnt += 1
    el = input().strip()
    for i in range(len(el) - 1):
        if el[i] == el[i + 1]:
            pass
        elif el[i] in el[i + 1:]:
            cnt -= 1
            break
print(cnt)

변수 개수도 확연하게 줄었고 이중 조건문을 사용할 필요도 없어졌다.

---

시도 2(C)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int is_group_word(char *word) {
    int visited[26] = {0};

    for (int i = 0; i < strlen(word); i++) {
        int current_char = word[i] - 'a';

        if (visited[current_char] && word[i] != word[i - 1]) {
            return 0;
        }
        
        visited[current_char] = 1;
    }

    return 1;
}

int main() {
    int N;
    scanf("%d", &N);
    char **arr = (char **)malloc(N * sizeof(char *));

    int bug = 0;
    for (int i = 0; i < N; i++) {
        arr[i] = (char *)malloc(101 * sizeof(char));

        scanf("%s", arr[i]);
        bug += (is_group_word(arr[i]) ? 0 : 1);
        free(arr[i]);
    }

    printf("%d", N - bug);
    free(arr);
    return 0;
}

<해석>

 

먼저 main 함수를 살펴보자. 사용자로부터 N을 받고 동적할당을 통해 행이 N개인 2차원 배열을 만들어준다. 그다음에 i=0번째 행부터 i=N-1번째 행까지 차례대로 크기 101짜리 배열을 선언해 준다. 이 배열에는 우리가 입력할 문자열이 들어갈 자리이다. 문제에서 문자열의 길이가 최대 100이라고 하였기 때문에 넉넉히 101까지 공간을 만들어 주었다.

 

이제 받은 배열이 그룹단어인지 확인 시켜주는 is_group_word 함수를 살펴보자. 갑자기 왜 새로운 배열 visited [26]와 변수 current_char이 튀어 나왔는지 각각의 역할은 아래와 같다.

 

int current_char = word[i]-'a';

정수형으로 선언된 current_char은 문자를 아스키코드 값으로 저장하기 때문에 word[i]가 만약 'b'라면

'b' - 'a' -> 98 - 97 -> 1 으로 해석되기 때문에 current_char에는 1이 저장된다. 이 값은 결국 알파벳 배열인 visited에 해당 알파벳(b)의 위치(인덱스)가 된다.  

 

 

int visited[26]={ 0 };

숫자 26을 보고 눈치 챘을 수도 있지만 visited는 알파벳 a ~ z까지 word에서 방문된 횟수를 기록하는 배열이다. 예를 들어 word에 { 'a', 'b', 'c' }가 저장되어 있다면 반복문에 의해 반복될 때마다 visited 배열은 아래와 같이 변한다.

1. { 1, 0, 0, 0 ...}
2. { 1, 1, 0, 0 ...}
3. { 1, 1, 1, 0 ...}

마지막으로 조건문을 보자. visited[current_char]이 0이 아니고(현재의 위치보다 문자열의 앞에 해당 알파벳이 최소 1개 존재한다) 현재의 알파벳과 이전의 알파벳이 같지 않으면(만약에 같다면 연속된 알파벳이기 때문에 검사할 필요가 없다) 그룹 단어가 아니므로 0을 반환하고 탈출한다. 반대로 for문을 끝까지 돌고 return 0;에 한 번도 걸리지 않았다면 1을 반환한다.

 

삼항연산자((is_group_word(arr[i]) ? 0 : 1);)를 통해 해당 단어가 그룹 단어가 아니면 bug에 1을 추가,  아니면 bug에 0을 더한다. 이렇게 한 번 사용된 배열의 메모리를 풀어준다.

 

이 과정을 N번 반복 했을 때 N - bug를 출력해 준다.