[Python/파이썬] 백준 # 26069

문제 링크: https://www.acmicpc.net/problem/26069

 

문제

 

---

코드

from collections import deque

n = int(input())
li = deque()

for _ in range(n):
    a, b = input().split()
    if a == "ChongChong":
        li.append(b)
    elif b == "ChongChong":
        li.append(a)

    if a in li:
        li.append(b)
    elif b in li:
        li.append(a)

print(len(set(li)))

 

처음 작성한 코드는 한 줄에 입력되는 두 이름들을 띄어쓰기를 기준으로 나누어서 a, b 변수에 입력받고,

a나 b에 "ChongChong" 이라는 이름이 들어오면 그 짝을 li라는 큐에 저장한다.

그리고나서 다음 줄에서 a나 b에 들어온 이름이 ChongChong과 함께 입력된적 있는 이름이라면

또한 li 큐에 저장한다.

마지막으로 set()으로 중복을 제거한 후 그 개수를 출력했다.

---

문제점

처음 작성한 코드로도 제출 했을 때 정답처리 되었지만 더 생각해보니 몇가지 문제점들이 있었다.

• 불완전한 중복 처리 방식
  li(큐)에 중복된 이름이 여러번 들어갈 수 있음.
  마지막에 set(li)를 사용해서 중복을 제거한다고 해도, 처음부터 중복된 데이터가 들어가는 걸 방지하는 것이 더 효율적.
• 시간 복잡도 문제
  li에 사람이 들어있는지 (a in li or b in li)를 체크하는데,
  이 방식은 li를 리스트로 관리하면서 검색하는 것이기 때문에 O(n), 최악의 경우 O(n$^2$)의 시간이 걸려 비효율적.

---

성능개선

from collections import deque

n = int(input())

dance_people = {"ChongChong"}
queue = deque(["ChongChong"])

for _ in range(n):
    a, b = input().split()

    if a in dance_people or b in dance_people:
        if a not in dance_people:
            dance_people.add(a)
            queue.append(a)
        if b not in dance_people:
            dance_people.add(b)
            queue.append(b)

print(len(dance_people))

• set을 사용하여 탐색 속도 개선 (O(1))
  dance_people을 set으로 만들어서, a in dance_people 탐색을 O(1) 속도로 빠르게 수행.
• 중복된 데이터가 처음부터 queue에 들어가지 않음
• 시간 복잡도 개선 (O(n))
  리스트를 매번 검색하는 O(n$^2$) 방식 대신, set을 사용하여 O(n)만에 탐색 가능.