문자열에서 패턴 찾기 (백준 2607, 비슷한단어)

                                    첫번째 문자에 대한 dictionary를 만든다.
{key: 0~}

이후 문자들의 각 문자에 대해 dictioanry에 key로 들어가있는지 확인한다.
if s in dic and dic[s] != 0: dic[s] -= 1 // 0이 되면 miss로 체크 ✒️

문자열이 들어가 있지 않다면 miss를 체크한다.

정답 케이스를 나눈다.
1. 모든 dictioanry의 value가 제거되며 miss가 1이하인 경우
  -- 같은 구성
  -- 하나만 제거하면 되는 경우

2. dictionary에 1의 value가 남아 있으며 miss가 1이하인 경우
  -- 하나만 추가하면 되는 경우 miss = 0
  -- 하나만 변경하면 되는 경우 miss = 1

이렇게 총 4개의 케이스로 나뉘는데, 조건을 하나로 합칠 수 있다.

dictionary의 총 value의 합을 remain이라 한다면,
if remain <= 1 and miss <= 1:
    비슷한 단어 !

                                    사용한 테스트 케이스

7
abc
ab
abd
abcc
abc
abbbb
abcccc

정답: 4

                                    import sys
import copy

M = int(sys.stdin.readline().rstrip())
target_dict = {}
target_size = 0
result = 0

for m in range(M):
    word = sys.stdin.readline().rstrip()
    missed_math = 0
    total_match = 0

    # make dictioanry
    if m == 0:
        target_size += len(word)
        for w in word:
            if w not in target_dict:
                target_dict[w] = 1
            else:
                target_dict[w] += 1
    else: #test
        test_dict = copy.copy(target_dict)
        for w in word:
            if w in test_dict and test_dict[w] > 0:
                total_match += 1
                test_dict[w] -= 1
            else:
                missed_math += 1
    if missed_math > 1:
        continue
    if total_match == target_size or total_match == target_size - 1 or missed_math == 1:
#        print("added word, tm, mm, test_dict", word, total_match, missed_math, test_dict)
        result += 1

print(result)

# 7
# abc
# ab
# abd
# abcc
# abc
# abbbb
# abcccc

                                    ✏️ 이건 글 작성하기 전에 같은 논리의 흐름으로 작성한 코드이다.

내가 생각한 논리를 제대로 반영하지 못하여 틀렸다.

1. 불필요한 변수 관리
2. 제대로 정리되지 않은 논리들 (논리 케이스 정리)

이런 경우에 예측할 수 없는 결과가 나온다.

                                    import sys
import copy

M = int(sys.stdin.readline().rstrip())
target_dict = {}
result = 0

for m in range(M):
    word = sys.stdin.readline().rstrip()

    # make dictioanry
    if m == 0:
        for w in word:
            if w not in target_dict:
                target_dict[w] = 1
            else:
                target_dict[w] += 1
    else: #test
        missed_math = 0
        test_dict = copy.copy(target_dict)
        for w in word:
            if w in test_dict and test_dict[w] > 0:
                test_dict[w] -= 1
            else:
                missed_math += 1

        remain_value = 0
        for v in test_dict.values():
            remain_value += v

        if remain_value <= 1 and missed_math <= 1:
            result += 1

print(result)

                                    ✏️ 느낀점

1. 논리의 흐름을 명확하게 정리하자.
2. 테스트 케이스를 여러가지로 나열하고, 최대한 묶어서 표현하자.
 -- 이렇게 해야 덜 혼란스럽다.
3. 모든 문제에 대한 테스트 케이스는 최소 4개는 찾아보자.

                                    🤔 나의 생각
시간 복잡도: 각 스트링의 단어를 하나씩 모두 탐색하므로 O(n)이 된다.

공간 복잡도: 메모리를 사용하는 부분은 크게  dict를 정의하고, copy하는 곳이다.
dict의 크기는 첫번째 word를 따르므로 공간 복잡도는 O(firstWord * 2)가 될 것 같다.
이는 상수로 O(1)이라 할 수 있다.

                                    💡 feedback o1
시간 복잡도는 O(NM)
1. 첫 번째 및 각 단어에 대한 처리
   -- 최대 N개의 문자 순회
2. copy.copy
   -- 최대 서로 다른 N개의 문자를 포함한다면 최악의 경우 O(N) // 근데 알파벳이므로 O(1) 아님? 맞다
3. M-1개의 단어에 대해 연산을 수행 = O(N) X M-1 = O(MN)

공간 복잡도는 O(1) 맞음

                                    💡 remove() 메서드를 사용해보자.