[이코테] 그리디_모험가 길드(파이썬/자바스크립트)

이번 글은 '이것이 취업을 위한 코딩테스트이다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

---

문제

 

---

접근 과정

 문제를 보면 공포도가 1, 2, 3인 모험가를 1그룹, 나머지 공포도가 2인 모험가 둘을 2그룹에 묶어라고 나와 있어서 [1, 2, 3]과 [2, 2]를 어떻게 분리할지 고민했다. 즉 접근 자체가 완전히 잘못되었다. 단순히 '현재 탐색하고 있는 모험가의 공포도'와 '현재 그룹에 포함된 모험가 수'의 관계를 활용하여 풀면 되는 문제였다.

 자세한 해설은 모범 답안 코드를 보고 나서 하겠다.

---

정답 코드

나의 풀이

풀이 1 Python Ver.

풀이 2 JavaScript Ver.

문제 해설

 문제에서 요구하는 정답은 여행을 떠날 수 있는 그룹의 최댓값이다. 즉, 주어진 공포도를 활용해서 최대한 그룹을 많이 만들면 되는 것이다. 그룹을 최대한 많이 만들기 위해서는 공포도를 낮은 것부터 그룹을 결성해나가야 한다. 왜냐하면 공포도가 1일 경우 1명만 있어도 여행을 떠날 수 있지만, 3이라면 최소 3명은 있어야 여행을 떠날 수 있기 때문에 그룹원이 더 많이 필요해지고, 결성할 수 있는 그룹의 수도 줄어든다.

 우선 오름차순으로 정렬한 data를 for문으로 탐색하며 '현재 그룹에 포함된 모험가의 수(count)'가 '현재 확인하고 있는 공포도(i)'에 달한다면 하나의 그룹을 결성하고 '현재 그룹에 포함된 모험가의 수'를 초기화하는 식으로 코드를 짜면 된다.

 위의 for문 안에서 print로 변수를 출력해보면 다음과 같이 나온다.

1회차
공포도(i) 1
현재 모험가 수(count) 1
총 그룹 수(result) 1

2회차
공포도(i) 2
현재 모험가 수(count) 1

3회차
공포도(i) 2
현재 모험가 수(count) 2
총 그룹 수(result) 2

4회차
공포도(i) 2
현재 모험가 수(count) 1

5회차
공포도(i) 3
현재 모험가 수(count) 2

 

 1회차 때 공포도(i)가 1이고 현재 모험가 수(count)도 1이므로 그룹 결성 요건을 충족한다. 따라서 새로운 그룹을 생성 (result += 1)하고 현재 모험가 수(count)를 초기화한다. 2회차의 공포도는 2라서 여행을 떠나려면 그룹 구성원이 2명 이상 되어야 한다. 따라서 그룹 구성원이 공포도에 미칠 때까지 기다려야 한다. 3회차의 공포도는 2회차와 마찬가지로 2이고 이는 그룹 구성원이 2이면 여행을 떠날 수 있다는 뜻이다. 이때 현재 모험가 수가 2가 되므로 앞선 1회차와 같이 그룹 결성 요건을 충족했으므로 새로운 그룹을 생성하고 현재 모험가 수를 초기화한다. 4회차와 5회차는 그룹 결성 요건을 충족하지 못했으므로 넘어간다.

---

함께 보기

문제 해설 영상