[백준] 1920번 수 찾기 - Python(1편)

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

 

백준 1920 문제를 간략히 설명하자면 N개의 정수로 이루어진 수열 A에서 M개의 정수가 각각 존재하는지 확인하여, 존재하면 1, 존재하지 않으면 0을 출력하는 프로그램을 작성하는 것입니다.

 

코드를 작성해서 제출했는데 시간 초과가 떴습니다. 1편에서는 왜 시간 초과가 뜨는지 한 번 알아보고, 2편에서 코드를 수정해 보겠습니다.

 

아래는 시간초과가 나온 코드입니다.

import sys
input = sys.stdin.readline

N = int(input())
treatment_group = list(map(int, input().split()))
M = int(input())
control_group = list(map(int, input().split()))

for data in control_group:
    if data in treatment_group:
        print(1)
    else:
        print(0)

 

시간 초과가 발생한 이유를 찾아보기 위해 현재 코드의 시간 복잡도를 계산해 보겠습니다.

혹시 모를 사람들을 위한 시간복잡도 설명이 있는 링크입니다.

2024.12.09 - [코딩 테스트] - 파이썬 코딩 테스트를 위한 시간 복잡도 이해하기

 

그럼 시간 복잡도 분석을 시작하겠습니다.

1. 입력 처리: O(N) + O(M)
   1. treatment_group 생성: O(N)
   2. control_group 생성: O(M)
2. 주요 연산: O(M * N)
   1. 외부 루트가 control_group의 인덱스 수인 M만큼 반복합니다.
   2. 각 반복마다 treatment_group 리스트의 in 연산이 O(N) 만큼 소요됩니다.
      1. 파이썬의 리스트에서 in 연산자는 선형 검색을 수행합니다.
      2. 최악의 경우, 리스트의 모든 요소를 검사해야 하므로 O(N)의 시간이 걸립니다.
   3. control_group의 각 요소에 대해 treatment_group 전체를 검사하므로, 총 M * N 번의 비교 연산이 발생합니다.
3. 전체 시간 복잡도
   1. O(N) + O(M) + O(M * N) = O(M * N)
   2. M * N의 항이 가장 큰 항이므로, 다른 항들은 무시합니다.

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.