프로그래머스 Lv1. 체육복 [Python]

---

뭐지.. 왜 문제 복사가 안되는거지!!!??

 

암튼.. 이제부터 블로그 제대로 작성할려고 노력..!

---

문제 정리

 

일단 이 문제는 제한사항을 봐야한다. (코딩테스트의 핵심은 제한사항을 잘 봐야한다!)

 

1. 중복이 없다. 
   - 이말은 lost와 reverse 내의 원소 값이 유일해야한다는 점!
   => lost = [1,1,2,3] reserve = [2,2,3,4] 가 될 수 없다.
   
   
2. 여벌의 체육복이 있는 학생(reserve) 도 도난 당했을 수 있다.
   - lost 값에 reserve 값이 공통적으로 존재할 수 있다는 의미!
   => lost = [1,2,3] reserve = [3,4,5] 처럼..
   그래서 문제를 보면 여벌의 체육복은 1벌 밖에 없으니 3번 학생은 체육복을 빌려줄수가 없다

>> 즉, lost와 reserve에 같은 값이 있다면 그 값은 reserve에서 제외시켜줘야한다.

 

 

step1. reserve의 요소들 중 lost에 동일하게 존재하는 값들은 모두 제거해줘야 한다. 

reserve_set = set(reserve) - set(lost)
lost_set = set(lost) - set(reserve)

//set 차집합 계산법
a = [1,3,5,6]
b = [2,4,6,8]
c = set(a) - set(b) //6이 공통

print(c) 
[1,3,5]

그걸 set 자료형으로 구현했다. set은 집합 자료형이므로객체끼리 집합 연산이 가능하다. 그래서 - 연산자를 사용하여 각 집합별로 차집합을 수행할 수 있다. 

 

step2. 예시를 보자

n	lost	reserve	return
5	[2,4]	[3,5]	5

 

 

학생 1	학생 2	학생 3	학생 4	학생 5
	x	o	x	o

 

3, 5 번 학생은 여벌의 체육복을 갖고 있다. 4번 학생은 3번, 5번 학생으로부터 체육복을 받을 수 있다.

 

           - 4번 학생이 3번 학생의 체육복을 받았다고 가정. => 체육 시간 참가 가능

           - 2번 학생은 3번 학생의 체육복을 받을 수 있음에도 3번이 4번한테 줬기에 못 받음. => 체육 시간 참가 불가능

           - 4번 학생은 굳이 3번 학생이 빌려주지 않아도 5번 학생의 체육복을 받을 수 있음.

 

결론 : 체육복은 양 옆 학생에게 빌려줄 수 있으므로 왼쪽 요소부터 탐색 해야 함.

 

step3. 문제 풀이

def solution(n, lost, reserve):
    reserve_set = set(reserve) - set(lost)
    lost_set = set(lost) - set(reserve)
    
    for student in reserve_set:
        if student - 1 in lost_set:
            lost_set.remove(student - 1)
        elif student + 1 in lost_set:
            lost_set.remove(student + 1)
            
    answer = n - len(lost_set)
    return answer

reserve의 student -1 요소는 reserve 학생의 왼쪽 학생부터 빌려주고

만약에 없다면 오른쪽 학생을 주는 식으로 작성하면 끝