3 분 소요

구현, 문자열

문제

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

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

입력

첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며, 길이는 최대 100이다.

출력

첫째 줄에 그룹 단어의 개수를 출력한다.

예제 입력 1 복사

3 happy new year

예제 출력 1 복사

3

예제 입력 2 복사

4 aba abab abcabc a

예제 출력 2 복사

1

예제 입력 3 복사

5 ab aa aca ba bb

예제 출력 3 복사

4

예제 입력 4 복사

2 yzyzy zyzyz

예제 출력 4 복사

0

예제 입력 5 복사

1 z

예제 출력 5 복사

1

예제 입력 6 복사

9 aaa aaazbz babb aazz azbz aabbaa abacc aba zzaz

예제 출력 6 복사

2

스스로 고민

  • 처음에 문자열을 replace 함수로 바꿔서 관리하려고 했지만 뭔가 복잡해졌다
  • 첫 번째 문자가 있을 경우 해당 문자에 카운트함수를 활용해서 몇 개가 있는지 확인 후
  • 그 숫자 만큼만 반복문을 돌면서 문자를 제거하고 해당 문자가 아닌 경우 나왔을 경우 반복문이 돌아가고 이건 아직 해당 문자열이 뒤에 남아있는 것이므로 전체 단어에서 하나를 빼는 식으로 생각을 했다.
  • 하지만 뭔가 너무 복잡해졌고 글자를 지울 때마다 문자열 자체의 길이가 달라져서 구현이 점점 복잡해졌다.
  • 해당 방법은 좋은 방법이 아니라고 판단이 들어서 좀 더 단순하게 생각을 해봤다.

    구현 코드


n = int(input())
count = n
for _ in range(n):
    word = input()
    z = len(word)
    for i in range(0, z-1):
        if word[i] == word[i+1]:
            pass
        elif word[i] in word[i+1:]:
            count -=1
            break
print(count)
  • 제한 부분에 단어의 개수가 100을 넘지 않아서 input() 을 사용했다. 시간 제한도 2초라서 반복문을 두 번 사용해서 문제를 해결했다.
  • 해당 단어의 길이를 측정한 후 전체 길이에서 1개의 길이만 뺀 후 앞에 문자와 뒤에 문자를 순차적으로 조회 -> 만약 앞에 문자와 뒤에 문자가 달라질 경우 슬라이싱을 통해 i번 뒤에 있는 문자중에 현재 문자가 있는지 확인 한 후 만약 있으면 -1 후 break 문을 빠져나오게 했다.

    시간 복잡도와 공간 복잡도

시간 복잡도:

  1. 사용자로부터 정수 n을 입력 받는 부분의 시간 복잡도는 O(1)다.
  2. for 루프는 n번 반복하며, 각 반복에서 문자열 word를 입력 받고 처리한다. 따라서 for 루프의 시간 복잡도는 O(n)다.
  3. 각 문자열 word의 길이를 계산하는 데 걸리는 시간은 O(z) 다. 여기서 z는 문자열의 길이다.
  4. 내부 for 루프도 z번 반복하며, 각 반복에서 문자열을 비교하고 조건을 체크한다.
  5. 문자열을 비교하고 조건을 체크하는 부분의 시간 복잡도는 O(z^2)다.

따라서 전체 시간 복잡도는 O(n * z^2)다.

공간 복잡도:

  1. 입력 받은 정수 n, 문자열 word, 그리고 정수 z에 필요한 메모리가 상수이므로 공간 복잡도는 O(1)다.

코드의 시간 복잡도는 n과 문자열의 길이 z에 의존하며, z가 상대적으로 큰 값이 될 경우에는 비교 연산을 수행하는 부분에서 더 많은 시간이 소요된다. 따라서 입력된 문자열의 길이와 입력된 문자열들 간의 관계에 따라 실행 시간이 크게 변할 수 있다.

회고 과정

처음에 그래프 부분부터 공부하려고 했지만 스터디에서 과제를 할 때마다 구현 부분이 너무 약해서 그냥 처음부터 단계 별로 알고리즘을 풀고 있다. 😑
확실히 쉬운 문제라서 대부분 구현 위주의 문제가 많았고 leetcode 보다 글로 설명되는 상황을 구현하는 게 더 어려운 나에게는 딱 안성맞춤이였다.

삼성문제 같은 경우 진짜 구현이 너무 복잡해서 힘들었는데 쉬운 구현 문제를 풀다 보니 어느 부분에서 내가 잘 구현을 못 하는지 알 수 있었다.
5단계 까지는 손쉽게 풀다가 지금 문제에서는 시간이 좀 오래 걸려서 나중에 다시 풀어보려고 블로그에 정리했다.

지금 코드에서 뭘 개선할 수 있지?

  • 좀 더 쉽게 하는 방법을 찾다가 해당 방법을 찾았다.
cnt = 0
for i in range(int(input())):
    word = input()
    cnt+=list(word) == sorted(word, key=word.find)
print(cnt)
  • 만약 각각 독립된 단어라면 정렬을 했을 때 서로가 같을 것이다.
  • 하지만 알파벳 순으로 정렬이 되므로 key 값을 정해두면 원래 값 그대로 정렬이 된다.
  • 예를 들면 banana 가 정렬 될 경우
    • 그냥 정렬한다면 aaabnn
    • 키를 설정한다면 baaann 와 같이 처음 나타난 문자의 순서대로 정렬된다.

댓글남기기

참고