[TIL#19] Study] 코딩 테스트 8

처음으로 시간초과가 났던 문제이다. 그리고 소위 말하는 '끌어온다'는 것이 뭔지 경험했다. 지금까지 기본기를 익힌다는 느낌으로 처음 생각한 것을 끝까지 구현한다는 자세로 임했다. 하지만 한편으로는 좋은 코드 짜왔다 할 수 없었다는 것을 깨달았다.

그리고 잘 짠 코드란 '필요한 것을 딱 필요한 만큼 사용한 가독성 좋은 코드' 임을 다시금 깨닫고 이 또한 중요한 기본기이며 앞으로 이를 잘 인지하고 코딩해야겠다 다짐했다.

 

기사단원의 무기

1. 끌어온 코드

    public int solution(int number, int limit, int power) {   // 리스트로 억지로 끌어온 답.
        int answer = 0;
        List<Integer> knightDmg = new ArrayList<>();
        List<Integer> needIron = new ArrayList<>();

        for (int i = 1; i <= number; i++) {			// 1부터 int number 까지

            for (int j = 1; j <= i; j++) {			// 각 숫자의

                if (i % j == 0) {					// 약수를 구한다
                    knightDmg.add(j);				// knightDmg에 저장한다
                }
            }
            needIron.add(knightDmg.size());			// 각 숫자의 약수의 개수를 저장
            knightDmg.clear();
        }
        for (int dmg : needIron) {					// 각 숫자 약수의 개수를 출력
            if (dmg > limit) {						// int limit 보다 크면
                dmg = power;						// 해당 개수를 int power로 치환
            }
            answer += dmg;							// 총 dmg를 구한다.
        }
        return answer;
    }

 

• 처음에는 리스트를 좀 더 사용하고 싶어서 리스트로 했고 불필요한 부분들과 한 가지 문제도 발생했었다.
  
  1. 문제점
     • 각 숫자의 약수의 개수를 저장하는 단계에서 값이 중첩되었다. 이유는 반복문을 돌리면서 이전의 값들을 초기화하지 않았기 때문이다.
     • 초기화하는 방법으로는 1) knightDmg 리스트를 반복문 안에서 선언 생성하거나, 2) 값을 입력하고 knightDmg를 초기화는 방법이 있었다.
     • 하여 공정과정이 조금 더 적은 2) 번을 선택하여 해결했다. 반복문 이해도와 로직 해석 능력 부족이 원인이라 생각된다.
  2. 불필요한 부분
     • 리스트 1개로도 해결이 가능하다. 사실 리스트가 필요 없다. 배열로 충분히 해결할 수 있는 문제이다. 그에 대한 답은 다음 코드로 설명하겠다.

 

2. 본인이 생각하는 정석 코드

    public static int solution(int number, int limit, int power) {
        int answer = 0;                       //  정석이지만 시간초과
        int[] knightDmg = new int[number];			// int number 길이의 배열 생성

        for (int i = 1; i <= number; i++) {			// 1부터 int number 까지
            int count = 0;
            for (int j = 1; j <= i; j++) {			// 각 숫자의
                if (i % j == 0) {					    // 약수를 구하고
                    count++;                          // 카운트 한다
                }
            }
            knightDmg[i - 1] = count;                 // 각 숫자의 배열에 카운트를 저장한다
        }
        for (int needIron : knightDmg) {
            if (needIron > limit) {
                needIron = power;
            }
            answer += needIron;
        }
        return answer;
    }

 

• 이처럼 배열을 생성하고 약수를 구할 때마다 int count 를 하나씩 중첩시키고 해당 숫자의 배열에 저장하면 리스트 없이 문제를 해결할 수 있다.
• 하지만 1부터 number까지 약수를 구한다고 반복문을 돌려야하는 특성상 시간복잡도 이슈로 인해 실패. 여기서부터는 수학적 지식이 조금 필요한 부분이다. 찾아보니 약수를 구하는 공식이 있었다.
• 약수 구하는 공식 
  1. 제곱근 이하의 숫자중에 n 을 i로 나눈 나머지의 값이 0이면
  2. i는 n의 약수이다.
  3. n을 i로 나눈 값도 n의 약수이다.
     ex) n = 10, n의 제곱근은 √10(= 3.162... int 형변환 시 3)
           10 % 1 = 0, 10 % 2 = 0 /// i = 1과 2
           10 / 1 = 10, 10 / 2 = 5 /// 10의 약수는 1, 2, 5, 10
• Java에서 제곱근을 구하는 메서드는 Math.sqrt(n); 이다.

 

3. 시간 복잡도 해결 코드

 

    public static int solution(int number, int limit, int power) {

        int answer = 0;
        int [] knightDmg = new int[number];

        for (int i = 1; i <= number; i++) {             // 1부터 number까지
            Set<Integer> Dmg = new HashSet<>();         // 중복되는 약수를 제거하기 위한 Set 사용
            for (int j = 1; j <= Math.sqrt(i); j++) {  // 약수 구하는 공식 구현
                if (i % j == 0) {
                    Dmg.add(i / j);
                    Dmg.add(j);
                }
                knightDmg[i-1] = Dmg.size();            // 구한 약수의 개수를 저장
            }
        }

        for (int needIron : knightDmg) {
            if (needIron > limit) {
                needIron = power;
            }
            answer += needIron;
        }
        return answer;
    }
}

 

• 여기서 문제점은 number 가 4, 9 등과 같이 중복되는 약수를 가진 숫자들은 모두 약수의 개수가 1개씩 더 집계된다.
• 중복을 허용하지 않는 컬렉션 Set 을 사용하여 중복된 약수를 제거하고 이를 저장한다.
• 2번 코드와 비교하면 반복문 실행 횟수가 굉장히 많이 감소하여 시간복잡도 이슈를 해결할 수 있다.