[프로그래머스] '합성수 찾기' - Java

<문제 제시>

<문제설명>
약수의 개수가 세 개 이상인 수를 합성수라고 합니다.
자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

<예시 입출력>

---

<문제 해결 과정>

먼저 합성수의 개념을 알고, 약수를 찾는 로직을 작성해야했다.

Try 1)

public static int solution(int n) {
    int answer = 0;

    List<Integer> temp = new ArrayList<>();
    int k = 0;
    int cnt = 0;

    //    	테스트케이스
    //    	
    //    	i = 1, n = 10
    //    	if(n % i == 0){
    //    	i = {1, 2, 5, 10} 

    // 1부터 ~ n까지 반복하면서
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++) {
            if(i % j == 0) {
                temp.add(k, j);
                k++;
            }

            if(k >= 3) {
                answer++;
                temp.clear();
                k = 0;
            }
        }
    }
    return answer;
}

주어진 수 n까지 반복하면서 0,1을 제외한 2부터 시작하는 반복문을 작성해보았다.

k를 통해 리스트의 인덱스를 직접 다루고, i % j == 0 인 값을 리스트에 추가해주었다.

만약 약수의 개수가 3개이상이되면 합성수이므로 answer값을 증가시키고 리스트를 다시 초기화 시켜주었다.

하지만 세부적인 로직이 부족하여 오답이었다.

>> 약수찾기 로직을 활용해 풀어보고자 하였지만 잘 되지 않았던 첫시도였다.

// 약수 찾기
if(n % i == 0) {
	temp.add(k, i);
	k++;
	System.out.println("temp_list = " + temp);
}

Solution 1)

약수찾기 로직을 활용하여, 이중 반복문 안에 break문도 추가하였다.

---

<전체코드>

public class composite_number {

	public static int solution(int n) {
        int answer = 0;
         
        int i,j;

        for(i = 2; i <= n; i++){
        	for(j = 2; j < i ; j++) {
        		if(i % j == 0) {
			        answer++;
			        break;
		        }
        	}
        }

        return answer;
    }
	
	public static void main(String[] args) {
		int n = 10;
		
		System.out.println(solution(n));
	}

}

---

break문을 통해 불필요한 인덱스 선언이나 리스트 선언, 리스트 초기화 부분을 없앨 수 있었다.

---

문제링크)
https://school.programmers.co.kr/learn/courses/30/lessons/120846

프로그래머스