[0818] 반복되지 않는 문자

문제

다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.

"abadabac"

코드 1

def find_not_repeating_character(string):
    fail = []
    result = []

    for i in range(len(string)):
        err = 0
        for j in range(i + 1, len(string)):
            if string[i] == string[j]:
                err += 1
                fail.append(string[i])
        if err == 0 and string[i] not in fail:
            result.append(string[i])

    if result:
      return result[0]
    else:
      return "_"

시간 복잡도 1

• 코드 1에 대한 시간 복잡도는 이중 for문이므로 𝑶(𝑵²)이 된다.
• 시간 복잡도가 𝑶(𝑵²)이므로 효율적인 코드가 되지 못한다고 생각해 다른 방식으로 코드를 작성해보았다.

코드 2

def find_not_repeating_character(string):
  alphabet_index = [0] * 26
  result = []

  for s in string:
    if not s.isalpha():
      continue
    index = ord(s) - ord("a")
    alphabet_index[index] += 1

  for i in range(len(alphabet_index)):
    occurence = alphabet_index[i]

    if occurence == 1:
      result.append(chr(i + ord("a")))

  for t in string:
    if t in result:
      return t
      
  return "_"

시간 복잡도 2

• 코드 2의 시간 복잡도는 for 문이 중첩되지 않고 따로 3번 돌아갔으므로 3𝑵이다. 따라서 𝑶(𝑵)이 되게 된다.

비교

• 코드 1과 코드 2의 시간 복잡도를 비교해보면, 코드 2가 𝑶(𝑵)로 훨씬 효율적인 코드인 것을 볼 수 있다.
• 코드 1은 내가 문제를 보고 혼자 짠 코드이고, 코드 2는 답안지의 코드이다. 코드 1의 내용이 문제를 보자마자 떠오른 방법이었는데, 확실히 머릿속이 비효율로 가득찬거 같다.