[코테] 체육복

HOU·2022년 5월 24일

코딩테스트

목록 보기

3/24

문제

문제 간략 설명

도둑이 들어서 체육복을 훔쳐갔다. 체육복을 훔쳐갔으면 범인을 잡아야지, 수업을 할 생각을 하다니 엄청나구만! 학구열에 불타는 학교에서는 체육복을 최대한 많이 나눠가지고 수업을 진행하려고 한다. 이 문제에서는 크게 세 가지 변수가 주어지는데 학생수 N, 잃어버린 학생 목록 lost, 여벌의 옷을 가지고 있는 목록 reserve

조건

명단은 번호 순으로 되어있고, 앞뒤에 있는 사람들 -1, +1 의 사람들에게만 체육복을 빌려줄 수 있고!
중요한 조건 여벌의 옷이 있지만, 체육복을 도둑맞은 경우는 , 그냥 자신의 체육복을 입는것으로 생각하면 된다!!

풀이

하아.. 그리디 알고리즘 문제를 푸는 와중에 처음으로 그리디 알고리즘에 대해서 나왓다. 그리디 알고리즘은 매순간의 선택일 때 가장 최고의 순간을 결정하는 것이다. 추후에 블로그에 정리해야겠다. 그리디 알고리즘은 모든 것을 확인하기에 데이터 양이 너무 많을 경우 사용하는 알고리즘이란다. 추후에 정리해야지! 이 문제를 풀 때 고려 한게, 두가지였다.

고려 사항
1. 여분의 체육복이 있는데 도난 당한 사람에 대한 처리
2. +1 부터 반복문을 돌릴지, -1부터 반복문을 돌릴지에 대한 문제였다.

1번 고려사항에 대한 풀이

두 리스트를 비교해서 동일한 것은 삭제 후에 리스트를 반환해 주려고 했는데, 정말 환상적인 파이썬은 너무나 간단하게 가능했다. 가독성도 좋다.! set(집합)자료형으로 만들어 준 후 에 차집합으로 동일한 부분을 제거 하고 하나만 남게 만들었다. 초대박!!!

lostA = set(lost) - set(reserve) #동일한 것은 제거되고 lost에 남은 값들만 들어간다.
reserveA = set(reserve) - set(lost) # 동일한 것은 제거되고 reserve에 남은 값들만 들어간다.

2번 고려사항에 대한 풀이

어떤 것(lost or reserve) 을 반복문으로 돌려서 값을 확인 할 것인지에 대한 문제가 있었다.
그리고 첫 풀이 후 이건 그리디라기 보다는, 그냥 전부다 확인하는거자나! 라는 생각이 들었다.
더 잘 풀어보고 싶었는데 ..

자! 어떻게 풀었나! 일단! 여벌옷을 가진 사람들 기준으로 -1 +1 사람을 확인해봐야했다.
그래서 사용한게, in이란 함수 였다. in이란 함수는 그 배열안에 값이 있는지 없는지를 True, False로 반환해준다. -1 값 부터 확인해야, 작은 사람들을 놓치지 않고 다 찾을 수 있다... ~~이걸 몰라서 한참을 고생했다.~~

그리고 값이 있으면 remove함수를 이용해서 해당 요소를 삭제해주었다.

for r in reserveA:
	if(r-1) in lostA:
    	lostA.remove(r-1);

전체 코드

마지막으로 lostA에 남아있는 배열 수만큼 전체 학생수에 빼주면 값이 나온다.!

def solution(n, lost, reserve):
    answer = n;
    
    #동일한 요소들 제거
    lostA = set(lost) - set(reserve)
    reserveA = set(reserve) - set(lost)

    #구분을 해야 한다. /남아 있는 값을 구하는 것이자나
    for r in reserveA:
        if(r-1 in lostA):
            lostA.remove(r-1)
        elif(r+1 in lostA):
            lostA.remove(r+1)
        
    
    return answer-len(lostA);