Codility Lessons 6 완료

4번 문제(NumberOfDiscIntersections) 어렵다! 저번 주 일요일 오후를 다 썼는데 정확도 100점, 성능 점수 25점으로 총점 62점까지가 한계였다. 결국, 컨닝을 하기로 하고 구글링을 했는데, 2010년도 챌린지 문제였네. 그래, 어렵더라. 여러 가지 솔루션이 있는데 정말 참신하다고 생각되는 솔루션이 2개 있어서 그걸 읽고 이해한 후에 다시 풀었다.

첫 번째는 두께로 접근해서 풀이한 방법이었는데 자바로 돌리면 성능 점수 62점으로 총점 81점이 나온다. 언어에서 pair 를 지원하지 않으니 객체를 만들어서 돌렸는데 객체 생성 비용에서 걸리는 것이 아닌가 생각한다.

두 번째는 원의 앞, 뒤를 주어진 배열 크기로 다 잘라내고, 시작점의 개수, 끝점의 개수를 카운팅하여 모아두고 해당 카운트들을 기반으로 조합 경우의 수를 찾는다.

둘 다 코드와 설명을 보고서 이해했지 시간을 더 사용했어도 저런 방법을 혼자 찾지는 못했을 것 같다. 개인적으로 첫 번째 문제 풀이 방식이 마음에 드는데 성능 이슈를 해결하지 못해서 아쉽다.

개인 GitHub 에 모두 올라가 있고 4번 문제 풀이만 종류별로 4개를 올려두었다.

Codility Lesson 6 Sorting

1. Distinct

2. MaxProductOfThree

3. Triangle

4. NumberOfDiscIntersections