-
[codility] MaxCounters개발관련 2023. 8. 8. 14:46
(문제) 정수 N, 배열 A가 주어졌을 때 아래 연산이 끝난 후 N의 크기를 가지는 카운터 배열 반환하는 함수 작성
- A[K] = X (1 <= X <= N) 카운터 배열 1 증가
- A[K] = N + 1 일 때 카운터 배열을 max Count로 채우기
(my solution)
- 문제를 이해하는데 시간이 오래 걸렸다.
- 22% => 로직 오류. 카운터 값을 증가시킬 때마다 Max값을 비교하여 maxCount 값을 저장해줘야 함
- 77% => 성능 문제.
- 33% => 로직 오류. maxCount 값 초기화를 안해줌.
- 최종: 88% (large_random2 성능테스트 통과하지 못함)
- 시간 복잡도: O(N^2) => 최악일 경우
package codility.tasks; import java.util.HashMap; import java.util.Map; public class MaxCounter { public static int[] solution(int N, int[] A) { HashMap<Integer, Integer> counterHash = new HashMap<>(A.length); int[] counters = new int[N]; int maxCount = 0; int base = 0; for (int i = 0; i < A.length; ++i) { int num = A[i]; if (num == N + 1) { base += maxCount; counterHash.clear(); maxCount = 0; } else if (num >= 1 && num <= N) { if (counterHash.containsKey(num)) { counterHash.put(num, counterHash.get(num) + 1); } else { counterHash.put(num, 1); } maxCount = Math.max(counterHash.get(num), maxCount); } } if (base > 0) { for (int c = 0; c < counters.length; ++c) { counters[c] += base; } } for (Map.Entry<Integer, Integer> e : counterHash.entrySet()) { counters[e.getKey() - 1] += e.getValue(); } return counters; } }
(chatGPT)
- Max 함수와 N + 1이 나오기 전 구간의 lastMaxCounter 값을 기억하고 있다가 활용하면 쉽게 풀 수 있는 문제인데 그 생각을 못했다.
- 시간복잡도 : O(N + A배열의 길이)
class Solution { public int[] solution(int N, int[] A) { int[] counters = new int[N]; int maxCounter = 0; int lastMaxCounter = 0; for (int i = 0; i < A.length; i++) { int operation = A[i]; if (operation >= 1 && operation <= N) { // increase(X) operation counters[operation - 1] = Math.max(counters[operation - 1], lastMaxCounter); counters[operation - 1]++; maxCounter = Math.max(maxCounter, counters[operation - 1]); } else if (operation == N + 1) { // max counter operation lastMaxCounter = maxCounter; } } // Update counters that haven't been increased by max counter operation for (int i = 0; i < counters.length; i++) { counters[i] = Math.max(counters[i], lastMaxCounter); } return counters; } }
테스트 케이스.... 테스트 케이스..... 테스트 케이스.....
문제의 핵심을 제대로 이해하고 테스트 케이스를 다양하게 생각하자.
'개발관련' 카테고리의 다른 글
[codility] MissingInteger (0) 2023.08.21 [기사] python GIL 삭제된다. (0) 2023.08.12 [codility] PermCheck (0) 2023.08.04 [codility] FrogRiverOne (0) 2023.08.03 [python] 3.11 얼마나 빨라진거야? 파이썬 업그레이드 3분 정리! (0) 2023.08.03