코데 대비3 - 조합,소수구하기,Collection 요소 삭제시 주의점

조합(Combination)

순서를 고려하지 않고 n개 중에서 r개를 뽑는 경우의 수

 

예시: [1, 2, 3]에서 2개 뽑기
결과: [1,2], [1,3], [2,3]  (총 3개)

❌ [2,1]은 [1,2]와 같은 조합이므로 제외!

 

순열과의 차이

• 순열: [1,2]와 [2,1]은 다름
• 조합: [1,2]와 [2,1]은 같음

public class prac {
    static int[] array = {1, 2, 3};
    static int n = array.length;
    static int r = 2;
    static int[] result = new int[r];

    public static void main(String[] args) {
        combination(0,0);
    }

    public static void combination(int depth, int startIndex) { // 조합은 startIndex가 매개변수로 추가된다.
        if (depth == r) {
            System.out.println(Arrays.toString(result));
            return;
        }

        for (int i = startIndex; i < n; i++) {
            result[depth] = array[i];
            combination(depth+1,i+1);
        }
    }
}
        /*
        
         depth는 재귀의 깊이를 의미한다.
         하나를 선택할때마다 depth가 증가하는것은 그 다음 재귀로 들어가게 됨을 의미한다.
         그래서 depth와 r이 같으면 다 뽑은것이다. 

         depth 1  -> [ 1, 2, 3, 4, 5 ] 를 반복문을 돌면서 하나를 선택하거나 선택하지않거나
         depth 2  -> [ 1, 2, 3, 4, 5 ] 를 반복문을 돌면서 하나를 선택하거나 선택하지않거나
         depth 3  -> [ 1, 2, 3, 4, 5 ] 를 반복문을 돌면서 하나를 선택하거나 선택하지않거나
         
         물론 startIndex를 이용해서 반복문을 돌기에 이전 depth선택한것의 그 다음부터 살펴본다.
         
         */

 

조합 코드 특징

조합은 순서를 고려하지 않고 선택하는 것이니까 이전 재귀스택에서 뽑힌 요소의 오른쪽으로만 살피면서 모든 경우를 살핀다.

예를들어서 {1,2,3}이 있고 2개를 뽑는 모든 경우의수를 살펴본다고 할때

 

진행순서는

첫번째 자리에 1을 뽑고 1이후의 2,3만 살펴보면 되고

반복문이 다음 인덱스로 진행되어서 첫번째 자리에 2를 뽑았다면 2이후의 3만 살펴보면 된다.

(= 조합은 순서를 고려하지 않으니까)

이전 재귀스택에서
1을 선택했다면?
  → 1은 다시 선택 안하고 다음 선택은 2, 3 중에서만 해야하니까 1의 대한 인덱스에 1을 더해서 시작인덱스로 전달한다.
  
2를 선택했다면?
  → 1,2는 다시 선택 안하고 다음 선택은 3만 해야하니까 2의 대한 인덱스에 1을 더해서 시작인덱스로 전달한다.
  
3을 선택했다면?
  → 1,2,3는 다시 선택 안해야하니까 3의 대한 인덱스에 1을 더해서 시작인덱스로 전달한다.

 

 

조합에서는 순서를 고려하지않고, 중복을 방지할 수 있는 수단으로 매개변수 StartIndex가 추가되었다.

 

반복문의 시작인덱스를 관리해서 순서를 고려하지않는 모든 경우의 수를 찾을 수 있는거고,

StartIndex의 값을 조절해서 중복이 가능하거나 못하게 만들 수 있다.

 

 

중복 조합

public class prac {
    static int[] array = {1, 2, 3};
    static int n = array.length;
    static int r = 2;
    static int[] result = new int[r];

    public static void main(String[] args) {
        combinationWithDuplicates(0,0);
    }

    public static void combinationWithDuplicates(int depth, int startIndex) {
        if (depth == r) {
            System.out.println(Arrays.toString(result));
            return;
        }

        for (int i = startIndex; i < n; i++) {
            result[depth] = array[i];
            combinationWithDuplicates(depth+1,i); // 중복을 허용하기위해 방금 뽑은 요소의 인덱스를 시작 인덱스로 전달해준다.
        }
    }
}

 

일반 조합과 중복조합의 차이는 단 한글자 차이가 난다.

전달하는 StartIndex에 값을 방금 뽑은 요소의 인덱스로 전달해주면 된다. 그러면 중복요소의 경우까지 처리된다.

combinationWithRepetition(depth + 1, i);  // 다음은 i부터 (자기 자신 포함!)

 

차이점:

• 일반조합: 이전 요소의 오른쪽으로만 진행 + 자기 자신 제외
• 중복조합: 이전 요소의 오른쪽으로만 진행 + 자기 자신 포함

---

소수구하기 ( Prime )

public boolean isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

 

소수는 1과 자기자신을 약수로 가지는 수이다.

그래서 1은 소수가 아니다.

2로 나눠지는 짝수들은 소수가 아니다.

 

1,2,짝수들은 미리 검사하고

홀수들에 대해서만 소수인지 검사한다.

i * i <= n

로 제곱근까지만 검사해서 검사 범위를 줄인다.  ( 약수는 항상 Pari(쌍)으로 존재하기 때문이다 )

 

---

Collection 주의점

 

컬렉션 순회 중 요소 삭제 시 주의사항

 

List나 Set 같은 Collection을 순회하면서 특정 요소를 삭제해야 할 때가 있다.

이때 평소처럼 for문을 사용하면 예상치 못한 에러나 버그를 마주하게 된다.

 

향상된 for문(for-each) 사용 시: 에러 발생

향상된 for문 내에서 list.remove() 등을 호출하면 ConcurrentModificationException 예외가 발생하며

프로그램이 강제 종료된다.

• 원인: 향상된 for문은 내부적으로 Iterator를 사용한다.
  순회 도중 컬렉션이 직접 수정되면, Iterator가 관리하는 상태 값과 실제 컬렉션의 상태가 달라져
  "Fail-Fast" 전략에 의해 예외를 던진다.

 

일반 index for문 사용 시: 논리적 오류(Bug)

일반적인 for (int i = 0; i < list.size(); i++) 방식은 예외는 발생하지 않지만, 데이터가 누락되는 치명적인 버그가 생길 수 있다

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 2, 3));

for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == 2) {
        list.remove(i);
    }
}
// 결과: [1, 2, 3] (연속된 '2' 중 하나가 삭제되지 않고 남음)

• 원인: 리스트의 요소를 삭제하면 뒤에 있던 데이터들이 앞으로 한 칸씩 당겨진다.
  하지만 인덱스 i는 다음 루프에서 그대로 증가하기 때문에, 당겨져 온 요소를 검사하지 못하고 건너뛰게 된다.

 

해결방안

① Java 8 removeIf() (가장 권장)

별도의 루프 없이 조건식(람다)만 전달하면 된다. 가독성이 가장 좋고 안전하다.

// List
list.removeIf(num -> num == 2);

// Set
set.removeIf(item -> item.equals("B"));

// Map ( EntrySet을 이용한 조건 삭제 (가장 많이 사용) )
Map<Integer, String> map = new HashMap<>();
map.put(1, "Apple");
map.put(2, "Banana");

map.entrySet().removeIf(entry -> entry.getValue().equals("Banana"));

// KeySet을 이용한 삭제 ( 특정 키 값을 기준으로 삭제할 때 유용하다. )
map.keySet().removeIf(key -> key == 1);

// Values를 이용한 삭제 ( value는 key와 다르게 중복값을 가지고있다. 그래서 조건에 맞는 모든 요소들이 지워진다.)
map.values().removeIf(value -> value > 25);

 

② Iterator 직접 사용

Iterator 객체의 remove() 메서드를 사용하면 순회 상태를 유지하면서 안전하게 삭제할 수 있다.

// List
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 2) {
        it.remove(); 
    }
}

// Set 
Iterator<String> it = set.iterator();
while (it.hasNext()) {
    if (it.next().equals("B")) {
        it.remove();
    }
}