python 코딩테스트 - 체육복

 

처음 든 생각

- lost, reserve에 각각의 포인터를 둔 다음

- 차이 1 나면 포함 아니면 넘어가는 걸로 해야겠다

 

나의 답안 - 오답

def solution(n, lost, reserve):
    answer = n - len(lost)
    i = 0
    j = 0
    lost.sort()
    reserve.sort()
    for m in lost:
        if m in reserve:
            lost.remove(m)
            reserve.remove(m)
            answer += 1 
                
    while i<len(lost) and j<len(reserve):
        if abs(lost[i] - reserve[j]) >1:
            continue
        elif abs(lost[i] - reserve[j])<= 1:
            answer += 1
            i +=1
        j+=1 
    return answer

각각의 리스트를 배열해준 후에 먼저 같은 값이 있는지 없는지 확인한다. 그 다음 포인터로 하나씩 이동시키면서 값을 확인하는 것이 아이디어였다. 하지만 시간 초과도 일어났고 같은 값에 대한 필터링도 잘 이루어지지 않아 처음부터 다시 풀어야겠다고 생각했다. 특히 시간 초과가 난 부분에서 리스트 자료형을 쓰는 것이 맞는지부터 의심을 했다.

---

나의 답안 - 수정

def solution(n, lost, reserve):
    lost_set = set(lost)
    reserve_set = set(reserve)
    intersect_set = lost_set & reserve_set
    
    lost_set -= intersect_set
    reserve_set -= intersect_set
    
    for i in reserve_set:
        if i-1 in lost_set:
            lost_set.remove(i-1)
        elif i+1 in lost_set:
            lost_set.remove(i+1)

    answer = n - len(lost_set)
    return answer

근본적인 자료형부터 바꿨다. 겹치는 것을 처리하기 위한 가장 좋은 자료형을 set라고 판단하였고 교집합을 매우 간단하게 찾을 수 있었다. 또한 답을 내는 방식도 처음에 빼준 뒤에 되는 친구들을 하나씩 더해주는 방식이 아니라, 안 되는 애들만 남겨서 n에서 그 애들의 수만 빼면 되겠다고 하였다. 

 

set의 교집합 연산과 차집합 연산으로 겹치는 애들을 제거한 후 반복문을 돈다. 여기서도 lost_set으로 돌아야할지 reserve_set으로 돌아야할지 고민이 됐다. 하지만 체육복을 빌려줄 수 있는지의 여부를 결정하는 것이 reserve_set 그리고 답은 산출하는 방식이 lost_set에 불가능한 아이템들을 남기는 방식이었기에 reserve_set를 기준으로 반복문을 도는 것이 타당하다. 그렇게 빌려줄 수 있는 애들을 lost_set에서 찾아내어 제외시켜주었다.

 

시간 초과가 생겼던 부분 그리고 겹치는 부분에 대해서 필터링한 부분이 훨씬 더 깔끔하고 쉽게 개선되었다.