프로그래머스 LV1 체육복

문제 유형 : 그리디(탐욕법)  => 그 순간마다 최선의 답을 찾는 알고리즘

문제 : 체육복 
https://school.programmers.co.kr/learn/courses/30/lessons/42862

프로그래머스

 

1. 처음 풀이 

처음 LV1이라 기존 풀던 LV3 보다 쉬울 것이라 생각했는데 생각보다 까다로웠다. 아직 갈 길이 먼 것 같다. 토이프로젝트 기간이 끝나면 알고리즘과 react 를 집중적으로 배워야 할 것 같다. 

 

처음 생각한 풀이는 다음과 같다. 

1)  reserve : 빌려줄 수 있는 친구들

     lost : 도난 당한 친구들 
2) reserve[0] + 1 = lost[0]  

   => lost[0] 을 reserve 배열에 더해줌 

3) reserve[0] - 1 = lost[0] 
   => lost[0] 을 reserve 배열에 더해줌

4) 만약 전체 학생 중에 1개씩만 가지고 있는 그냥 학생들 있다면
  => reserve 배열에 더해줌 
5) reserve 배열 count한 값을 return 

 

이런 식으로 reserve 배열 기준으로 시도를 했는데 4)도 그렇고 애초에 reserve 배열에 lost 배열의 요소를 더해주는 방법부터 어려웠다. 이럴 땐 반대로 생각해야 하는데 아직 그런 사고를 가지고 있지 못한 것 같다. 꾸준하게 암기하는 것이 답인 것 같다. 

2. FeedBack 

검색을 해보니 lost 배열을 기준으로 푸는 것 같았다. lost 배열에 있는 요소들을 제거해나가면서 전체 학생에서 lost 배열 길이 만큼 빼주면 되는 간단한 풀이가 있었다. 반대로 생각했으면 됐을텐데 이 부분이 좀 아쉽다. 

 

reserve[i] + 1  = lost[i] 
=> lost[i] 제거 해줌
reserve[i] - 1 = lost[i] 
=> lost[i] 제거 해줌

 

이런 식으로 문제를 풀었더니 다음과 같은 에러들이 떴다. 

 

3. 실패 코드

 

간단하게 reserve 배열 즉, 나눠줄 수 있는 사람 중에서 lost에 값이 있으면 lost를 제거해주는 것으로 적어봤는데 틀렸다. 

문제를 차근차근 읽어보니 이런 요구사항이 있었다. 

여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

저 코드에서는 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우를 생각하지 못했다. 만약 도난 당했으면 여벌이 없으므로 빌려줄 수가 없기 때문이다. 그래서 다음과 같이 생각해보았다. 앞서 Feedback 필기에서 언급했던 것을 적자면
1) reserve에 있는데 lost에도 있을 때 => 1개밖에 없어 못 빌려주는 상황임 

2) reserve에 있는데 lost에는 없을 때 => 빌려줄 수 있는 상황임

3) lost에 있는데 reserve에 없으면 => 진짜 잃어버린 거임  

4) lost에 있는데 reserve에 있을 때 => 1)과 같은 상황이기 때문에 pass 

 

이를 코드로 구현해서 풀어보았다. 

lost_student와 reserve_student를 정의하는 방법이 잘못되었음을 깨닫고 다시 코드를 짜보았다.

경우의 수를 2)과 3)으로 나누어 해주었더니 코드 실행은 성공했지만 본 제출때는 통과하지 못했다.

이유를 보니깐 체격순으로 번호를 매겼다 해서 오름차순으로 해주어나 생각했고 그렇게 진행한 결과에도 몇 가지 결과를 통과하지 못해서 이유를 보았다.  i + 1과 i - 1을 반대로 해주었더니 통과되었다. 아마 내가 먼저 앞 사람에게 빌려주고 나서 그 다음 for문을 돌렸어야 했는데 그 부분에서 충돌이 난 것 같았다. 

 

4. 정답 코드

5. feedback 

• reserve_student[i] 에서 반복문을 돌리는 것이 아닌 i in reserve_student 식으로 돌릴 수 있단 점을 잊지말자 
• if i - 1 == lost_student => lost_student = [1,2,3] 일 때 이 값들이 i-1과 정확히 일치해야 한다는 뜻이다. 
• if i -1 in lost_student => lost_student에 i-1 요소가 포함되어 있는 지 확인한다는 뜻이다. 위 문제에선 이것이 맞기 때문에 python 문법도 틈틈이 까먹지말고 봐주자. 
• 맞게 생각한 것 같은데 문제가 안풀리면 그 반대 경우도 생각해보자 reserve 배열 기준이 아닌 lost 배열 기준으로도 생각해보는 시도를 했다면 수월하게 풀 수 있었을 것이다. 
• 시간복잡도는 계산해봤을 때 sort() => O(nlogN) , for i in reserve => O(reserve) , for i in lost => O(lost) , for i in reserve_student => O(reserve_student) 모두 더했을 때 O(nlogN) 이다. (확인 필요)