푼 날짜 : 2020.11.25
문제
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
입출력 예 설명
예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.
예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.
출처
※ 공지 - 2019년 2월 18일 지문이 리뉴얼되었습니다.
※ 공지 - 2019년 2월 27일, 28일 테스트케이스가 추가되었습니다.
내 풀이
여벌을 챙겨온 사람이 잃어버린 경우와 여벌을 챙겨오지 않은 사람이 잃어버린 경우로 나누어서 생각했습니다.
먼저, 여벌을 챙겨온 사람이 잃어버린 경우를 보겠습니다. 잃어버린 사람이 여벌을 가져왔다면 그 사람은 잃어버린 사람도, 여벌을 가져온 사람도 아니게됩니다. 그렇기에 for,if 를 사용해서 요소가 여벌의 가져온 사람들 리스트(reserve) 의 요소가 잃어버린 사람들(lost) 에 있다면 두 리스트에서 모두 빼줍니다. 이때 reserve 를 앞에서 부터 출력하면서 제거를 하면, reserve의 인덱스에 영향을 주고 원하는 결과를 가져올 수 없습니다. 그렇기 때문에 reserve의 요소를 역순으로 출력하면서 제거해 줍니다.
다음은 여벌을 챙겨오지 않은 사람이 잃어버린 경우입니다. reserve 의 요소가 lost 의 요소 +- 1 에 존재할때, 그 요소를 제거해주면 됩니다. 이때는 제거하는 리스트가 lost 밖에 없기에 reserve 의 요소를 앞에서부터 출력해도 상관이 없습니다.
이렇게 두 경우를 나누어서 잃어버린 사람들의 리스트를 수정해주는 방식으로 답을 구했습니다.
다른 사람들 풀이
차집합으로 lost 와 reserve 를 수정한 풀이입니다. 이렇게 해주면 lostN과 reserveN에서 공통된 요소가 없습니다. 공통된 부분을 제거해주고 lostN 요소와 reserveN 요소를 비교해 답을 구하고 있습니다. 시간복잡도가 O(n^2) 인 부분은 아쉽지만, 차집합으로 공통된 부분을 빼준 과정을 배우고싶습니다.
위에 풀이과정과 비슷하게, lost와 reserve 의 공통된 부분을 제거한 풀이입니다. 차집합을 이용한 위 방식과 다르게 리스트 컨프리헨션을 사용한 부분을 비교하고자 두 풀이를 가져왔습니다.
