프로그래머스 Lv2 숫자 블록 문제

• 프로래머스 Lv2 숫자블록 문제
  • 문제를 읽고 난 후의 분석
    • 최소 공배수를 이용한 규칙 탐색 + 주어진 범위만 검사하여 메모리 절약
  • 해당 문제의 난이도 상승 원인
    • 약 10억이라는 번호가 존재
    • 내가 문제의 지문을 놓침
    • 효율성을 만족하기 위한 코드 구상이 어려웠음
  • 해당 문제를 해결한 방법
    • 최대 블럭 번호인 10,000,000를 이용한 제한점을 두어 이를 만족할 때만 값을 반환하도록 + 만약 소수라면 1을 반환하도록 기능을 작성
  • 해당 문제를 해결였던 과정
    1. 숫자들의 최소 공배수에 대한 규칙이 있을 것 같단 예상이 들어 1 ~ 200 까지의 각 자리수에 대한 최대 공약수 테이블을 만들어 비교
    2. 테이블 생성 후 짝수번류는 (해당 짝수 % 2) + (해당 짝수를 10을 몫으로 나눈 후 값) * 5라는 규칙을 가진다는 것을 확인하였고 홀수는 일정한 규칙이 발견되지 않음
    3. 그래서 홀수에 대한 다른 방법을 찾으려는 중 n 을 루트화 후(==sqrt) 나온 수를 체크하여 그것보다 작은 홀수들을 오름차순으로 정렬하여 체크해야 한다는 것을 확인
    4. 위에서 분석한 내용을 기반으로 코드 작성 후 코드 제출로 테스트 해보았으나 정확성에선 1개 오류 + 효율성 시간초과로 에러
    5. 무언가 놓친게 있나 문제를 다시 확인하니 추가 제한사항 발견(블럭 번호의 최대치는 10,000,000)하였고 내코드 에선 최대 500,000,000의 블럭번호까지 존재하여 정확성에서 오류가 발생하였던 것
    6. 또한 효율성이 계속 오류가 나던 원인도 이와 연관되어 계속 실패로 뜨고 있었음
    7. 최대 블럭번호를 10,000,000까지 제한하도록하는 조건을 걸고 (target / i)를 했을 때 처음으로 10,000,000이하가 되는 경우 해당 i 값을 반환하도록 코드 수정하여 효율성도 통과됨을 확인
  • 문제의 핵심
    • 무조건 나눴을 때 나머지가 0인 것이 정답이 아닌, 10,000,000 이하라는 조건을 만족하면서 효율성까지 고려한 코드 설계가 중요

 import javax.xml.stream.events.StartDocument;
import java.util.concurrent.LinkedTransferQueue;

public class Lv2NumBlock {
    public static void main(String[] args){
        solution(1, 10);
    }

    // 1000000000
    // 10000000

    public static int gcd(long target){
        if(target == 1) return 0;
        int returnVal = 1;

        for(int i = 2; i * i <= target; i++){
            if(target % i == 0){
                if(target / i <= 10000000){
                    return (int)(target / i);
                }
                returnVal = i;
            }
        }

        return returnVal;
    }

    public static int[] solution(long begin, long end){
        int[] table = new int[(int)(end - begin + 1)];

        for(int i = (int)begin; i <= (int)end; i++){
            int idx = (int)(i - begin);
            table[idx] = gcd(i);
        }

        return table;
    }
}