CodingTest: programmers 120910 나누어 떨어지는 숫자 배열

new-pow·2022년 11월 9일

👿 문제

문제 설명

array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

제한 사항

arr은 자연수를 담은 배열입니다.
정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
divisor는 자연수입니다.
array는 길이 1 이상인 배열입니다.

🔍 접근 방법

첫 시도

문제를 보자마자 이것은 출력하는 방식을 어떻게 하느냐가 중요한 문제라는 생각이 들었다. 배열은 리사이징이 불가능하기 때문에 연산할 때마다 배열을 카피해서 만들어주는 불상사를 겪고 싶지 않았다. 따라서 두개의 장치를 추가함으로써 첫번째 구현을 해볼까한다.

int cound 변수로 나눠 떨어지는 숫자를 구한다.
int[] arr를 한바퀴 체크한 후, 새로운 정답 배열을 만든다.
정답 배열을 정리한다.

의사코드

아마도 시간 복잡도 최악의 경우 O(n^2)(.sort를 사용하기 때문에), 최선의 경우 O(n 될 것같다.

class Solution {
    public int[] solution(int[] arr, int divisor) {
		// 1. 변수 생성
		int count = 0;
        
        // 2. divisor로 나눠떨어지는 숫자 체크
        for (i가 arr크기만큼돌기) {
        	if(나눠떨어지는가?) {
        		boolean[i] = true; count ++;
        	}
        }
        
        // 3-1. 만약 count가 0이라면 처리
        
        // 3-2. 0이 아니라면 정답 배열 생성
        int[] answer = new int[count];
        
        // 4. 정답 배열 채우기
        for (i가 arr크기만큼 돌기) {
        	if(boolean[i]) {
            	arr[i] 저장 
            }
        }
        
        // 5. 정렬하기
      
        
        return answer;
    }
}

제출 결과

import java.util.*;

class Solution {
    public int[] solution(int[] arr, int divisor) {
        int count = 0;
        int[] answer;
        
        for (int i=0; i<arr.length; i++) {
            if (arr[i]%divisor==0) {
                count++;
            }
        }
        
        if (count==0) {
            answer = new int[1];
            answer[0] = -1;
        } else {
            answer = new int[count];
            int inputCount = 0;
            for (int i=0; i<arr.length; i++) {
                if (arr[i]%divisor==0) {
                    answer[inputCount] = arr[i];
                    inputCount ++;
                }
            }

            Arrays.sort(answer);
        }
        
        return answer;
    }
}

테스트 1 〉	통과 (0.41ms, 78.4MB)
테스트 2 〉	통과 (0.38ms, 74.8MB)
테스트 3 〉	통과 (0.37ms, 73.3MB)
테스트 4 〉	통과 (0.48ms, 74.6MB)
테스트 5 〉	통과 (0.39ms, 77.1MB)
테스트 6 〉	통과 (1.29ms, 80.7MB)
테스트 7 〉	통과 (0.09ms, 74.1MB)
테스트 8 〉	통과 (0.03ms, 77.9MB)
테스트 9 〉	통과 (0.65ms, 72.6MB)
테스트 10 〉	통과 (0.64ms, 72.3MB)
테스트 11 〉	통과 (0.36ms, 72.6MB)
테스트 12 〉	통과 (0.40ms, 72.9MB)
테스트 13 〉	통과 (0.17ms, 80MB)
테스트 14 〉	통과 (0.66ms, 77MB)
테스트 15 〉	통과 (0.55ms, 82.8MB)
테스트 16 〉	통과 (0.47ms, 76.7MB)