[codility] MaxCounters

MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Task Score

100%

Correctness

100%

Performance

100%

---

correctness 100%에 performance 0% 결과.. 시간복잡도 제한이 O(N+M) 인데 O(N*M) 이 나와버려서 40대의 점수가 나와버렸다. ㅠㅠ

루프 하나에서 모든 값처리를 다 하려고 했던게 요인인 것 같다.

 
x
// you can also use imports, for example:
import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(int N, int[] A) {
        int[] result = new int [N];
        int max = 0;
        
        for (int i = 0; i < A.length; i++) {
            
            if (A[i] >= 1 && A[i] <= N) {
                result[A[i] - 1]++;
                
                if (max < result[A[i] - 1]) 
                    max = result[A[i] - 1];
            }
            
            if (A[i] > N) {
                final int MAX = max;
                Arrays.setAll(result, (inex) -> MAX);
            }
        }
        
        return result;
    }
}
​

 

다시 작성한 코드. 점수를 보고 너무 충격을 받아 내 것은 꺼두고 다른사람의 코드를 훑어보니 다들 temp를 하나 두고 하는 것 같았다. 그래서 나도 temp와 max 두개로 나누어 만들어놓고 시작했다.

위에서는 한 루프 내에서 increase(X)와 max counter를 순서대로 한 번에 처리하려고 했는데, 때가 왔을 때 값을 한방에 일괄적으로 맞춰주는 것이 아니라, max값을 정해놓고 매 순번마다 max값보다 작은지 큰지 체킹하고 값을 더해줬다. 그래도 값이 max값보다 작은 것들은 for loop를 한번 더 돌면서 체크해줬다.

다른사람의 코드를 훑어보고, 다시 문제를 풀어나가면서 더 유연하게, 융통성있게 생각하는 법을 연습해야겠다고 느꼈다.

 

 
x
// you can also use imports, for example:
// import java.util.*;
​
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
​
class Solution {
    public int[] solution(int N, int[] A) {
        int[] result = new int[N];
        int tempNum = 0;
        int maxNum = 0;
        
        for (int i = 0; i < A.length; i++) {
            
            if (A[i] > N) {
                maxNum = tempNum;
                continue;
            }
            
            if (result[A[i] - 1] < maxNum)
                result[A[i] - 1] = maxNum;
             
            result[A[i] - 1]++;
             
            if (result[A[i] - 1] > tempNum)
                tempNum = result[A[i] - 1];
        }
        
        for (int i = 0; i < N; i++) {
            
            if (result[i] < maxNum)
                result[i] = maxNum;
        }
        
        return result;
    }
}