[Algorithm] 사막에서 만난 지니 (SW Expert Academy – 4747)

By | 2018-07-29

출처

  • https://www.swexpertacademy.com

난이도

  • 하 – 중 – (상) – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

  • 물건의 종류를 주고 각 물건의 값어치를 Input으로 준다. 주어진 물건을 3개의 그룹으로 나누어서, 모든 그룹에 속한 물건 값어치 합이 똑같아지는 답을 찾는 문제이다.
  • SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 상세히 문제를 설명하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

  • 처음 문제를 읽고는 정말 어렵지 않을 것 같았다. 단순히 전체 값어치의 합을 3으로 나누어서 그룹 2개를 만들면 하나가 같아질 거라고 판단했다. 그래서 findSub Recursive 함수를 만들어서 그룹 3개를 생성하였다. 하지만, 단순히 findSub으로 값어치의 합이 1/3되는 부분을 찾게 되면 1개의 그룹은 항상 1/3 값어치를 가지는 그룹이 생성되는 반면 나머지 2개의 그룹은 같은 값어치를 가지는 그룹을 만들지 못하는 경우가 발생한다.
  • 그래서 다음으로 진행한 방법이 Quick Sort를 사용하여 물건의 값어치가 큰 것부터 순서대로 정렬하였다. 그리고 findSub함수를 사용하여 값어치가 큰 것부터 물건의 그룹을 나뉘도록 코드를 구현하였다. 큰 값어치부터 정렬을 하다 보면 3개의 그룹으로 나뉠 때 작은 값어치를 가진 물건으로 인해서 정확하게 3그룹으로 나누지 못하는 문제를 해결할 수 있었다.

코드

  • Quick Sort 함수를 사용하여 값어치를 정렬 후 Recursive 함수를 사용하여 Group을 3개로 나누는 코드
  • 실행 시간: 89ms (제일 빠른 코드 대비 대략 10% (81ms) 느림. Quick Sort 대신 Priority Queue를 사용해 보았는데 3ms 정도 성능향상이 있음)

 

Leave a Reply

Your email address will not be published. Required fields are marked *