1. 내 코드
for 문에서 리스트를 직접 수정할 경우 수정 직후 반복문이 끝나게 된다.
그래서 lost=[3,4] reserve=[4,3] 케이스에서 3만 없어지고 4는 남게 됨.
이럴 경우, [:] 를 써서 리스트 카피본으로 반복문을 돌리면 반복문이 끝까지 다 돌 수 있다.
내 코드의 복잡도는 이중 반복문 (X) 과 sort (log) 로,
L (lost size), R (reserve size) 라고 할 때,
O(L x R + LlogL) 이다.
def solution(n, lost, reserve):
answer = 0
# 여벌 체육복 중 하나만 도난당했을 경우
for l in lost[:]:
if l in reserve:
lost.remove(l)
reserve.remove(l)
if len(lost) > 1: lost.sort()
# 체육복 나누기
for num in lost:
# 여벌 학생이 없으면 반복문 탈출
if not reserve:
break
# 앞 뒤로 도난 학생 여부 파악 -> 나눠주고 여벌 학생 리스트 제거
if (num - 1) in reserve:
reserve.remove(num - 1)
elif (num + 1) in reserve:
reserve.remove(num + 1)
else:
continue
answer += 1
answer += n - len(lost)
return answer
2. GPT 코드
set 을 써서 중복을 제거하면 복잡도를 x -> + 로 낮출 수 있다.
list 자료형을 set(집합)으로 변환한 뒤
& 연산자를 통해 교집합을 추출하여 중복을 제거한다.
이렇게 하면 복잡도는 O(LlogL + R) 이 되어 이중반복문을 돌릴 때보다 낮은 복잡도를 갖게 된다.
def solution(n, lost, reserve):
# Convert lists to sets for efficient operations
lost_set = set(lost)
reserve_set = set(reserve)
# Remove students who have both lost and reserved a uniform
overlap = lost_set & reserve_set
lost_set -= overlap
reserve_set -= overlap
answer = n - len(lost_set) # Start with the number of students who already have uniforms
# Distribute uniforms
for student in sorted(lost_set):
if student - 1 in reserve_set:
reserve_set.remove(student - 1)
answer += 1
elif student + 1 in reserve_set:
reserve_set.remove(student + 1)
answer += 1
return answer
[Python 입문 강좌 - 12] 파이썬 집합(Set) 정리 및 사용법
더보기 ##파이썬 입문 목차 1. 파이썬 이란? 2-1. 파이썬 윈도우 설치 2-2. 파이썬 맥북 설치 2-3. 윈도우 파이썬 IDE 파이참 설치하기 2-4. 맥북 파이썬 IDE 파이참 설치하기 3. 파이썬 변수(Variable)의 정
ctkim.tistory.com
