메이플 코어강화 컨텐츠 코딩테스트 버전

코강유틸 프로젝트를 만들면서 가장 핵심 기능인 코어조합을 어떤 식으로 생성할지에 대한 문제를 고민했었다.

취업준비를 하면서 자소서를 작성하는데 자신이 제작한 프로젝트를 서술하라고 할때마다 코어강화 문제를 말로 길게 서술해봤자 메이플을 하지 않는 사람들은 이해하지 못할 것이라 생각이 들었다.

코어강화 컨텐츠를 메이플을 하지 않는 사람들도 문제를 파악할 수 있도록 코딩테스트 형식으로 서술해보았다.

 

문제

5가지 input이 주어진다.

상자유형(box_list), 필수과일(prefer_fruit), 과일 선호도(preference), 과일중첩 제한(limit), 사용 상자수(box_count)

라벨링=> 석류=0, 감=1, 오렌지=2, 사과=3, 배=4, 포도=5, 파인애플=6

어느 과일가게 사장님은 특별한 규칙을 가지는 과일포장 상자를 이용하여 손님들에게 과일을 담아 판매한다.

손님들은 반드시 구매할 과일들이 무엇인지, 각 과일의 과일 선호도가 어떻게 되는지, 같은 종류의 과일이 몇개 초과로 담겨있으면 안되는지, 구매할 상자 수가 몇개인지 작성하여 사장님께 드린다.

과일가게 사장님은 손님이 작성한 정보를 바탕으로 어떤 상자유형을 이용하여 손님께 포장하여 판매할지 결정한다.

 

과일포장 상자의 규칙은 다음과 같다.

상자

3가지 종류의 과일을 담을 수 있는 상자가 있다. 옆의 이미지는 상자를 나타낸 것이다.

상자는 다음과 같은 규칙을 가진다.

 

1. 상자에 담긴 3개의 과일 중 해당 상자를 대표하는 과일이 있다.

2. 한 상자에 같은 과일이 들어가 있지는 않는다.

3.상자는 길이가 3인 리스트로 주어지며 리스트 요소는 0이상의 정수이다. ex)[3,2,5]

4.상자리스트의 가장 앞의 요소는 대표과일을 나타낸다.

5.상자는 항상 가득차 있다.(3개의 과일이 모두 존재한다.)

 

예를 들어보자.

해당 상자의 대표과일은 사과이고 상자안에는 사과, 오렌지, 포도가 들어있다.

표현방식은 [3,2,5]이다.(라벨링 참조)

 

 

 

 

 

과일가게 사장님이 보유한 과일포장 상자들은 box_list로 주어진다. box_list는 상자(리스트)를 요소로 가지는 리스트이다.

ex) box_list=[[3,2,5],[5,2,3]]라면 사과를 대표로 하는 사과, 오렌지,포도 박스,  포도를 대표로 하는 사과,오렌지,포도 박스를 가지고 있다. 

 

손님들이 작성하는 정보는 다음과 같다.

 

1.prefer_fruit

자신이 반드시 사야하는 과일이 사과,포도라면 prefer_fruit=[3,5]로 작성한다. prefer_fruit의 크기는 가변적이고 반드시 1개 이상은 있다.

 

2.preference

각 과일의 선호도는 1~25의 범위로 점수를 매겨 preference에 작성한다. preference는 리스트형식이며 주어진 과일 종류 갯수의 크기이다.

예를들어 preference=[10,5,2,7,15,20,1]로 주어진다면 라벨링을 index로 접근하여 생각해본다면 포도를 선호, 파인애플을 싫어하는 것이다.

 

3.limit

특정 과일이 지나치게 겹쳐 포장되는 것을 방지하기 위해서 포장된 과일들 중에서 n개 이상 포함되지 않기 위해서 limit=n으로 기입한다.

예를들어 limit=2이라고 지정하면 포장된 과일 중 어떤 과일이라도 3개 이상 포장되어 있으면 안된다는 것이다.

[3,2,5],[5,2,3]상자를 포장에 쓴다면 사과, 오렌지, 포도가 각각 2개씩 포장에 포함되었으므로 limit=2를 만족한다.

[3,2,5],[5,2,3][0,2,1]상자를 포장에 쓴다면 오렌지 3개가 포장에 포함되었기 때문에 limit=2를 만족하지 못한다.

limit는 2,3,4,5 중 하나의 값이 주어진다.

 

4.box_count

포장에 사용하는 상자의 개수를 나타낸다.

box_list=[3,2,5],[5,2,3][0,2,1],[4,1,2]일 때

box_count=2이라면 만들 수 있는 조합은 (0,1),(0,2),(0,3),(1,2),(1,3),(2,3)로 6가지이다 (조합개념)

box_count=3이라면 만들 수 있는 조합은 (0,1,2),(0,1,3),(0,2,3),(1,2,3)로 4가지이다 (조합개념)

 

사장님은 위 손님이 작성한 정보를 토대로 포장을 하는데 한가지 규칙을 더 고려해서 포장한다.

포장에 사용할 상자의 조합을 생각할 때 다음의 규칙을 따라야 한다.

1. 대표과일이 겹치지 않도록 포장상자를 선택하여 포장해야된다.

   [3,2,5],[3,2,4]의 상자는 두개다 사과를 대표로 하는 포장상자이다. 두 상자는 동시에 포장에 이용될 수 없다.

 

2. 손님이 반드시 사야하는 과일(prefer_fruit)을 대표과일로 사용하는 상자를 우선적으로 포장에 사용하며 대표과일로 사용한 상자가 많을수록 우선순위가 높다.

ex) prefer_fruit=[3,5]이고 [3,2,5],[5,2,4] 조합은 [3,2,5],[4,2,5] 조합보다 우선순위가 높다

 

3. 사장님은 손님이 포장된 필수 과일들의 선호도 합계가 가장 높은 조합을 받을 수 있도록 포장한다. 만약 선호도가 같은 조합이 여러개 존재하면 필수가 아닌 과일들의 선호도까지 합산하여 가장 높은 선호도를 만드는 포장을 한다.

전체 선호도까지 동일하다면 동일한 조합방식을 전부 return한다.

설명은 아래의 예시에서 서술한다.

 

ex)

            0번째  1번째   2번째  3번째  4번째 상자 (0부터 시작!)

box_list=[[3,2,5], [3,2,4], [5,2,3], [0,2,1], [4,0,5]]

prefer_fruit=[3,5]

preference=[10,5,2,7,15,20,1]

limit=2

box_count=3

 

단순히 생각하면 박스 3개를 사용해서 만들 수 있는 조합은 10가지이다. 그중 사용하지 못하는 조합을 처리하면,

01번째조합 0,1,2 : 0번째 상자, 1번째 상자는 사과를 대표로하는 상자이므로 동시에 포장에 사용할 수 없다. {1}

02번째조합 0,1,3 : 0번째 상자, 1번째 상자는 사과를 대표로하는 상자이므로 동시에 포장에 사용할 수 없다. {1}

03번째조합 0,1,4 : 0번째 상자, 1번째 상자는 사과를 대표로하는 상자이므로 동시에 포장에 사용할 수 없다. {1}

04번째조합 0,2,3 : 0번째 상자의 대표과일 3, 2번째 대표과일 5번이 prefer_fruit에 포함됨 (2개포함) {3}

05번째조합 0,2,4 : 0번째 상자의 대표과일 3, 2번째 대표과일 5번이 prefer_fruit에 포함됨 (2개포함) {3}

06번째조합 0,3,4 : 만들 수 있는 조합이지만 4,5,7,8번째 조합보다 우선순위 떨어짐(1개포함) {2}

07번째조합 1,2,3 : 1번째 상자의 대표과일 3, 2번째 대표과일 5번이 prefer_fruit에 포함됨 (2개포함) {3}

08번째조합 1,2,4 : 1번째 상자의 대표과일 3, 2번째 대표과일 5번이 prefer_fruit에 포함됨 (2개포함) {4}

09번째조합 1,3,4 : 만들 수 있는 조합이지만 4,5,7,8번째 조합보다 우선순위 떨어짐(1개포함) {2}

10번째조합 2,3,4 : 만들 수 있는 조합이지만 4,5,7,8번째 조합보다 우선순위 떨어짐(1개포함) {2}

 

{1}: 사과(3)를 대표로하는 박스 두개가 존재하는 조합은 규칙에 어긋난다.

{2}: 4,5,7,8번째 조합에서 필수과일을 대표로사용하는 박스 수 2개 조합이 있기 때문에 우선순위 떨어짐

{3}: limit=2 조건에서 필터된 조합 예를들어 4번째 조합은 오렌지가 3개가 들어있어 안된다.

 

조건을 충족하는 조합은 8번조합으로 1,2,4번째 상자[[3,2,4],[5,2,3],[4,0,5]]를 return한다.

 

 

만약에 limit=3이였다면 {3}로 필터된 4,5,7번 조합도 고려해야된다.

7번 8번 조합만 limit=3이였을 때로 고려해보자.

 

7번 조합은 [[3,2,4],[5,2,3],[0,2,1]] 석류 1개, 감 1개, 오렌지 3개, 사과 2개, 배 1개, 포도 1개

8번 조합은 [[3,2,4],[5,2,3],[4,0,5]] 석류 1개, 오렌지 2개, 사과 2개, 배 2개, 포도 2개

로 포장된다. preference=[10,5,2,7,15,20,1]를 적용해보면 

석류=10, 감=5, 오렌지=2, 사과=7, 배=15, 포도=20, 파인애플=1로 점수를 둬서 계산하면

7번 조합의 선호도 합계= 10*1+5*1+2*3+7*2+15*1+20*1=70

8번 조합의 선호도 합계= 10*1+2*2+7*2+15*2+20*2=98

 

선호도 합계가 7번 조합보다 8번 조합이 더 크기 때문에 8번 조합을 선택한다. 

 

 

============================================================================

메이플 유저 길라잡이

상자유형(코어종류), 필수과일(필수스킬), 과일 선호도(스킬레벨), 과일중첩 제한(n중첩), 사용 상자수(n코어)

과일종류= 스킬

 

전체적인 데이터 전처리를 한 다음 문제를 코딩테스트 유형으로 바꿔보았습니다.

해당 문제를 해결하기 전까지의 데이터처리가 더 힘들더군요......