해결 과정
소요 시간 1시간 이상
은근 까다로웠던 문제..? 다시 살펴보기 & 다른 풀이 살펴보기
+ 22.02.21
까다로운 문제가 아님.
체육복 개수 넣는 배열 만들자 & 앞에서 부터 풀면 Greedy 하다.
이 두 개만 명확했으면 까다롭지 않음.
Greedy의 대표적인 문제. 이 문제를 보고 왼쪽에서 오른쪽으로(혹은 그 반대로) 순차 대로 탐색해도 된다는 것을 인지했어야 Greedy로 풀 수 있는 문제였음.
나의 풀이
def solution(n, lost, reserve):
final_reserve = sorted(reserve)
final_lost = sorted(lost)
# lost와 reserve에 중복된 것 있으면 lost, reserve에서 제외시키기
duplication = set(final_reserve) & set(final_lost)
if len(duplication) > 0:
final_reserve = list(set(final_reserve) - duplication)
final_lost = list(set(final_lost) - duplication)
answer = n - len(final_lost)
# lost 와 reserve 사이 처리한 값 answer에 더하기
who_can_borrow = []
for i in final_lost:
if i == 1:
who_can_borrow.append([2])
elif i == n:
who_can_borrow.append([n-1])
else:
who_can_borrow.append([i-1, i+1])
for i in who_can_borrow:
for j in final_reserve:
if j in i:
answer += 1
final_reserve.remove(j)
break
return answer
다른 풀이
다른 풀이 v1
체육복의 개수를 배열에 저장하고 푼 풀이
시간 복잡도 O(n)
IDEA) arr = [1] * (n+2) 처럼 코드의 간결화를 위해 사용하는 코드
def solution(n, lost, reserve):
answer = 0
arr = [1] * (n+2)
for i in lost:
arr[i] -= 1
for i in reserve:
arr[i] += 1
for i in range(1, n+1):
if arr[i] == 0:
if arr[i-1] > 1:
arr[i] = 1
arr[i-1] -= 1
elif arr[i+1] > 1:
arr[i] = 1
arr[i+1] -= 1
answer = len([k for k in arr if k > 0])
return answer
다른 풀이 v2
처음 풀이와 비슷한 형식인데, 뒷 부분에서 처리하는 방식이 달랐음.
Set의 Intersection연산 시간 복잡도: O(len(s)+len(t))
이 풀이는 sorted()로 인해 최종 시간 복잡도는 O(nlogn).
reserve를 기준으로 lost에서 제외하고, 전체 n에서 남은 lost의 개수를 리턴하는 방식.
def solution(n, lost, reserve):
s = set(lost) & set(reserve)
l = set(lost) - s
r = set(reserve) - s
for x in sorted(r):
if x-1 in l:
l.remove(x-1)
elif x+1 in l:
l.remove(x+1)
return n - len(l)
IDEA
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 거리두기 확인하기 (0) | 2022.02.24 |
---|---|
[문제 풀이] 큰 수 만들기 (0) | 2022.02.17 |
[문제 풀이] 순위 검색 (0) | 2022.02.09 |
[문제 풀이] 뉴스 클러스터링 (0) | 2022.02.08 |
[문제 풀이] 메뉴 리뉴얼 (0) | 2022.02.07 |