[Algorithm#7] 백준 5597 과제 안 내신 분..? (Python)

목표

 

X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다.

교수님이 내준 특별과제를 28명이 제출했는데, 그 중에서 제출 안 한 학생 2명의 출석번호를 구하는 프로그램을 작성하시오.

 

입력

 

입력은 총 28줄로 각 제출자(학생)의 출석번호 n(1 ≤ n ≤ 30)가 한 줄에 하나씩 주어진다. 출석번호에 중복은 없다.

 

출력

 

출력은 2줄이다. 1번째 줄엔 제출하지 않은 학생의 출석번호 중 가장 작은 것을 출력하고, 2번째 줄에선 그 다음 출석번호를 출력한다.

 

풀이

1. 직관적인 완전 탐색

 

변수 설정 

• 출석번호 저장을 위한 a 리스트 

풀이 방법:

1. 리스트 선언 : a = []
2. 과제를 제출한 28명의 출석 번호 a 리스트에 저장 : a = [int(input()) for _ in range(28)]
3. 1부터 30까지 리스트 안을 확인하면서 a 안에 i 번호가 있는지 확인 : [print(i) for i in range(1,31) if i not in a]

a = []
a = [int(input()) for _ in range(28)]
[print(i) for i in range(1,31) if i not in a]

 

핵심원리

• 1부터 30까지 숫자를 하나씩 부르면서 탐색하는 가장 기초적인 방법

장단점

• 장점 : 논리가 사람의 사고방식가 유사하여 이해가 쉬움
• 단점 : 매번 리스트 처음부터 끝까지 뒤져야 하므로 시간 복잡도가 O(N^2)

---

 

2. 체크 배열과 함수형 프로그래밍

 

변수 설정 

• 출석번호 전체 저장을 위한 a 리스트 
• 제출 하지 않은 학생을 필터링 하여 저장하기 위한 f 리스트
• 출석번호 단일 저장을 위한 정수형 변수 idx

풀이 방법:

1. 리스트 선언과 0으로 초기화 : a = [0]*30
2. idx에 각 출석번호 저장 : for _ in range(28) : idx = int(input()) \n arr[idx-1] = idx
3. 리스트 내 값이 0인 인덱스 번호만 추출하여 리스트로 저장
   1. 람다 함수를 사용하여 arr 리스트 내 0인 값을 추출 : lambda x : arr[x] == 0 , range(30)
   2. 필터 함수를 통해 추출된 값들의 위치 값을 추출 : filter(lambda x : arr[x] == 0, range(30))
   3. 리스트로 변환 후 f 리스트에 저장 : list(filter(lambda x : arr[x] == 0, range(3)))
4. min과 max 함수를 활용하여 출력 : print(min(f) + 1, max(f)  + 1, sep = "\n")

import sys
input = sys.stdin.readline

arr = [0]*30
for _ in range(28):
    idx = int(input())   
    arr[idx-1] = idx
    
f = list(filter(lambda x : arr[x] == 0, range(30)))
print(min(f) + 1, max(f)+1, sep="\n")

 

핵심 원리

• 수학의 집합 개념을 사용합니다. '1부터 30까지 있는 전체 집합'에서 '입력받은 숙자들의 집합'을 통째로 빼버립니다.

장단점

• 장점 : 1번 방법의 시간 초과를 인덱스를 활용해 시간 복잡도 O(N)으로 우회
• 단점 : 단순히 누락된 값을 찾기 위해 filter, lambda, min, max가 사용되어 코드가 무겁고 장황해짐

---

3. 집합 연산과 숏코딩

 

변수 설정 

• 과제를 제출하지 않은 출석번호 리스트 a 

풀이 방법

1. 집합 연산과 언패킹 연산자를 활용하여 과제를 제출하지 않은 출석번호 추출
   1. 1번부터 30번까지 차례대로 집합을 생성 : {*range(1,31)}
   2. open 연산자를 활용하여 입력된 모든 데이터를 한번에 읽어서 집합을 생성 : {*map(int, open(0))}
   3. 1번 집합과 2번 집합을 빼버린 후(차집합) 리스트로 변환: [*{*range(1,31)} - {*map(int, open(0))}]
2. sort 함수를 통해 리스트 a를 정렬하고 차례대로 출력 : for i in sorted(ad) : print(i)

a = [*{*range(1, 31)} - {*map(int, open(0))}]
for i in sorted(a): print(i)

 

핵심 원리

• 수학의 집합 개념을 사용합니다. '1부터 30까지 있는 전체 집합'에서 '입력받은 숙자들의 집합'을 통째로 빼버립니다.

  

장단점

• 장점 : 속도가 압도적으로 빠름(O(N)) 파이썬의 집합 연산은 C언어 수준으로 최적화되어 있음
• 단점 : 숙련도가 낮은 사람이 보기에 연산자가 많고 함축적

 

---

 

비교 항목	1번 코드(직관)	2번 코드(체크)	3번 코드(집합)
핵심 기법	in 연산자를 활용한 선형 탐색	인덱스 직접 주소화	Set의 차집합 연산
시간 복잡도	O(N2)	O(N)	O(N)
공간 복잡도	O(N)	O(M) (M은 전체 번위의 크기)	O(N)
코드의 유연성	보통	매우 높음	낮음
가독성	매우 높음	보통	낮음