[Programmers] 주사위 고르기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

순열과 이분 탐색을 통해 풀 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. A와 B가 주사위를 나누어 가지는 모든 경우의 수를 next_permutation 메서드를 통해 구현합니다.

1.1 여기서 주의할 점은 next_permutation 사용 시 [{1, 2}, {3, 4}], [{1, 2}, {4, 3}], [{2, 1}, {3, 4}], 그리고 [{2, 1}, {4, 3}] 모두 다른 순열로 취급합니다. 하지만 A와 B 입장에서는 네 가지 케이스 모두 같은 경우이므로 이를 적절히 예외처리를 해줘야 TLE가 발생하지 않습니다.

2. 1번을 통해 나눈 A와 B의 주사위들의 합산을 각각 Asums와 Bsums에 저장합니다. (func 메서드 참고)

3. 2번을 통해 구한 합산들을 단순 비교한다면 시스템 케이스 19번부터 시간초과로 통과가 안될 것입니다.

3.1 따라서 O(N^2) 보다 빠른 알고리즘을 떠올려야 하고 저는 Bsums를 정렬하고 각각의 A 주사위들의 합산에 대해 Bsums를 이분탐색하여 A가 이기는 경우의 수를 구했습니다. 이렇게 하면 정렬이 O(NlogN)이라고 가정했을 때 O(NlogN)으로 풀 수 있습니다.

3.2 또한 A 주사위들의 합산에도 중복이 있을 수 있으므로 이미 해당 합산이 몇 번 이길지 구한 전적이 있다면 O(N)만에 구할 수 있도록 map 객체인 sum2winCnt에 캐싱했습니다.

3.3 이렇게 최적화하더라도 시스템 케이스 19번부터는 4초가 넘기 때문에 사실상 시간 초과라고 해도 무방합니다. 이보다 더 효율적인 알고리즘이 있다면 댓글 작성 부탁 드립니다!

4. 1 ~ 3번을 통해 모든 경우의 수를 구하고 이 중 가장 승률이 높은 A 주사위 조합을 반환합니다.

 

* 이분 탐색 구현 코드는 백준 블로그에 잘 작성되어 있습니다!

 

 

개발환경: Programmers IDE  

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~