[스터디 과제] 1. 배열 과제_(배열에서 가장 많이 반복된 숫자와 해당 숫자가 반복된 빈도수를 리턴 )

1. 문제

• 배열만을 사용해서 아래의 조건에 부합하는 메서드를 완성하세요
• 주어진 배열에서 가장 많이 반복된 숫자와 해당 숫자가 반복된 빈도수를 정수형 배열로 리턴하는 메서드를 완성하세요
  • ex) 배열에서 2가 4번 나온 경우, [2, 4] 를 리턴
• 특정 숫자가 동일한 빈도수로 나왔다면 제일 작은 숫자와 빈도수를 리턴합니다

---

import java.util.*;

public class Assignment01 {
  public static void main (String[] args) {
        int[] tc1 = new int[]{1, 2, 3, 2, 2, 4, 5, 2, 6, 4};
        int[] tc2 = new int[]{1, 2, 3, 4, 5};
        int[] tc3 = new int[]{1, 2, 2, 3, 3};

        System.out.println(Arrays.toString(solution(tc1))); // [2, 4]
        System.out.println(Arrays.toString(solution(tc2))); // [1, 1]
        System.out.println(Arrays.toString(solution(tc3))); // [2, 2]
  }
  public static int[] solution(int[] arr) {
     int maxCount = 0; //최대 등장 횟수
     int minNumber = Integer.MAX_VALUE; // 최대 등장 횟수의 숫자 중 가장 작은 값
     
     //배열 순회
     for (int i = 0; i < arr.length; i++) {
        int count = 0;
        
        // 현재 숫자의 등장 횟수 계산
        for (int j = 0; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                  count++;
            }
        }
        
        // 최대 등장 횟수 갱신
        if (count > maxCount || (count == maxCount && arr[i] < minNumber)) {
            maxCount = count;
            minNumber = arr[i];
        }
     }
     
     // 결과 반환
     return new int[]{minNumber, maxCount};
  }
}

 

2. 풀이 :

1. 외부 반복문 :

배열의 각 요소를 선택하여 기준으로 삼는다.

예를 들어, 첫 번째 숫자 1을 기준으로 배열에서 몇 번 나왔는지 확인한다. 

 

2. 내부 반복문 :

기준 숫자와 배열의 모든 숫자를 비교하며 등장 횟수를 세어준다. 

 

3. 최댓값 비교 및 갱신 :

만약 현재 숫자의 등장 횟수가 maxCount보다 크면 새로운 값을 기록한다. 

등장 횟수가 동일한 경우 숫자가 더 작은 경우로 갱신한다. 

이 조건문은 현재 숫자가 "최대 등장 횟수와 비교하여 더 크거나, 또는 등장 횟수가 같으면서 숫자가 더 작은 경우"를 확인한다.

 3.1 count > maxCount :

현재 숫자가 지금까지 본 숫자들보다 더 많이 나왔는지 확인하는 조건이다.

 3.2 count == maxCount && arr[i] < minNumber :

현재 숫자가 지금까지 최고 등장 횟수와 같은데, 숫자가 더 작은지 확인하는 조건이다.

예를 들어, 2와 3이 둘다 4번 나왔는데, 숫자가 더 작은 2를 우선 선택한다.

 

<나의 초기 접근 방식에 대한 분석>
나의 초기 논리적 접근 방식은,
1. 배열을 순회하며 각 요소를 기준으로 나머지 요소와 비교
2. 각 숫자의 등장 횟수를 세고, 등장 횟수가 최대인 숫자를 찾음.
3. 등장 횟수가 같다면 숫자가 더 작은 것을 선택함.

잘한점 :
1. 올바른 문제 정의:
for문으로 배열을 순회하며 각 숫자의 등장 횟수를 확인하려는 아이디어.
최댓값을 비교하면서 등장 횟수를 갱신하고 결과를 반환하려는 접근은 문제를 정확히 이해하고 있다는 증거였다.

2. 조건 비교의 개념
i번째 요소와 나머지 요소를 비교하려는 것은 배열의 등장 횟수를 계산하는 직관적인 방법이다.
"최대 등장 횟수"를 갱신하며 답을 찾으려는 방향은 문제를 올바르게 풀기 위한 핵심이다.


부족했던 점 :
1. 효율성 부족 :
i번째 요소를 기준으로 나머지 모든 요소를 확인하는 방식은 이중 반복문이 필요한데 그것을 못하였다.
배열의 크기가 클 경우 , 성능이 매우 떨어질수 있다.
등장 횟수를 확인할 때 HashMap과 같은 효율적인 데이터 구조를 활용하지 못핬다.

2. 명확하지 않은 조건 설명. 
“i번째 요소와 나머지 요소들과 같은지 메서드를 가지고 확인해야 한다”라는 접근은 이해 가능하지만, 이를 코드로 구현할 때 조건을 구체적으로 정의하지 않았다.
예 : 등장 횟수를 비교하면서 최댓값을 갱신하는 조건(if)을 분명히 해야 한다.

3. 결과 반환의 구체성 부족.
등장 횟수가 동일할 경우, 숫자가 더 작은 것을 선택한다는 문제 조건이 명확히 포함되지 않았다.
• 등장 횟수를 확인하고 갱신하는 로직이 더 구체적으로 필요하다.

 

보완 방안

1. 효율적인 등장 횟수 계산 :

배열 전체를 순회하면서 등장 횟수를 효율적으로 계산할 수 있는 방법(예 : HashMap 사용)을 배우고 적용해야 한다.

이렇게 하면 모든 숫자의 등장 횟수를 한 번의 순회로 계산할 수 있다.

 

2. 조건의 명확화 :

등장 횟수가 최대값보다 큰 경우와, 동일한 경우 더 작은 숫자를 선택하는 조건을 명확히 구현한다.

이를 위해 조건문을 나누어 가독성을 높이는 것이 중요하다.

 

3. 단계별 풀이로 논리를 분리 :

1단계 : 각 숫자의 등장 횟수를 계산한다.

2단계 : 가장 많이 등장한 숫자와 등장 횟수를 찾는다.

이 과정을 명확히 나누어 단계별로 작성하면 논리가 더 쉽게 정리된다.

---

3. 효율성을 고려한 시간 복잡도를 줄인 코드

 

주요 아이디어 :

1. HashMap 사용 :

숫자별 등장 횟수를 저장한다.

HashMap의 키는 숫자, 값은 해당 숫자의 등장 횟수이다.

 

2. 한 번의 순회로 최대값 찾기 :

HashMap에 저장된 값들을 순회하며 최대 등장 횟수와 해당 숫자를 찾는다.

등장 횟수가 동일할 경우 더 작은 숫자를 선택한다.

 

import java.util.*;

public class Assignment01 {
    public static void main(String[] args) {
        int[] tc1 = new int[]{1, 2, 3, 2, 2, 4, 5, 2, 6, 4};
        int[] tc2 = new int[]{1, 2, 3, 4, 5};
        int[] tc3 = new int[]{1, 2, 2, 3, 3};

        System.out.println(Arrays.toString(solution(tc1))); // [2, 4]
        System.out.println(Arrays.toString(solution(tc2))); // [1, 1]
        System.out.println(Arrays.toString(solution(tc3))); // [2, 2]
    }

    public static int[] solution(int[] arr) {
       //숫자별 등장 횟수를 저장할 HashMap
       Map<Integer, Integer> frequencyMap = new HashMap<>();
       
       // 배열 순회하며 등장 횟수 계산
       for (int num : arr) {
           frequencyMap.put(num, frequencyMap.getOrDefault(num,0)+1);
       }
       
       // 최대 등장 횟수와 해당 숫자 초기화
       int maxCount = 0;
       int minNumber = Integer.MAX_VALUE;
       
       // HashMap 순회하며 최대 등장 횟수와 숫자 찾기
       for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int number = entry.getKey();
            int count = entry.getValue();
            
            // 최대 등장 횟수 갱신 또는 동일 횟수일 때 더 작은 숫자 선택
            if (count > maxCount || (count == maxCount && number < minNumber)) {
                 maxCount = count;
                 minNumber = number;
            }
       }
       
       // 결과 반환
       return new int[]{minNumber,maxCount};
    }

 

풀이 :

1. HashMap에 등장 횟수 저장 :

frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) +1)를 사용하여 숫자의 등장 횟수를 계산한다.

frequencyMap.getOrDefaut(num, 0)는 num이라는 숫자가 이미 frequencyMap에 있으면, 그 숫자가 나온 횟수를 가져온다.

없다면, 기본값 0을 가져온다.  그 횟수에 1을 더해서 현재 숫자가 나온 횟수를 업데이트 한다. 

 

위 문법을 여러줄로 나누어서 단계별로 작성하면 이렇다. 

if (frequencyMap.containsKey(num)) { //숫자가 이미 있는지 확인
    int count = frequencyMap.get(num); // 숫자가 나온 횟수를 가져옴
    frequencyMap.put(num, count +1); // 횟수를 1을 더해서 저장
} else {
   frequencyMap.put(num, 1); // 처음 등장한 숫자는 1로 저장
}

 

<단계별 설명>

1. frequencyMap.containsKey(num) :

num이라는 숫자가 이미 기록되어 있는지 확인

예 : frequencyMap에 2가 이미 들어 있다면 true, 없으면 falsue를 반환

 

2. 숫자가 있으면 횟수를 가져와서 1증가 :

frequencyMap.get(num)은 num이 나온 횟수를 가져온다.

가져온 값에 1을 더해서 다시 저장한다.

 

3. 숫자가 없으면 1로 초기화

frequencyMap.put(num, 1)은 처음 등장한 숫자를 기록하고 횟수를 1로 저장

---

4. 단순화된 버전의 코드 

import java.util.*;

public class Assignment01 {
    public static void main(String[] args) {
        int[] tc1 = new int[]{1, 2, 3, 2, 2, 4, 5, 2, 6, 4};
        int[] tc2 = new int[]{1, 2, 3, 4, 5};
        int[] tc3 = new int[]{1, 2, 2, 3, 3};

        System.out.println(Arrays.toString(solution(tc1))); // [2, 4]
        System.out.println(Arrays.toString(solution(tc2))); // [1, 1]
        System.out.println(Arrays.toString(solution(tc3))); // [2, 2]
    }
    
    public static int[] solution(int[] arr) {
       // 숫자별 등장 횟수를 저장할 HashMap
       Map<Integer,Integer> frequencyMap = new HashMap<>();
       
       // 배열 순회하며 등장 횟수 계산
       for (int num : arr) {
           if (frequencyMap.containsKey(num)) { // 숫자가 이미 있는지 확인
               int count = frequencyMap.get(num); //등장 횟수를 가져옴
               frequencyMap.put(num, count+1); // 횟수에 1을 더해서 저장
       } else {
           frequencyMap.put(num, 1); // 처음 등장한 숫자는 1로 저장
       }
    }
    
    //최대 등장 횟수와 해당 숫자 초기화
    int maxCount = 0;
    int minNumber = Integer.MAX_VALUE;
    
    // HashMap 순회하며 최대 등장 횟수와 숫자 찾기
    for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
         int number = entry.getKey();
         int count = entry.getValue();
         
         // 최대 등장 횟수 갱신 또는 동일 횟수일 때 더 작은 숫자 선택
         if (count > maxCount || (count == maxCount && number < minNumber)) {
             maxCount = count;
             minNumber = number;
         }
      }
    
    //결과 반환
    return new int[]{minNumber, maxCount};
    
    }

 

---

5. 원래 문법 vs 단계별 코드

 

원래 문법 :

frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) +1);

 

 

단계별 코드 :

if (frequencyMap.containsKey(num)) {
    int count = frequencyMap.get(num);
    frequencyMap.put(num, count +1);
} else {
     frequencyMap.put(num, 1);
}