[문제 풀이] 체육복

코딩테스트 연습 - 체육복

 

해결 과정

소요 시간 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