[ 순열 ] 순열의 중복허용 여부

관련문제 ( 프로그래머스 - 옹알이[1] )

 

 

순열과 조합

Permutation 순열

순열은 집합의 원소들로 만들 수 있는 모든 가능한 순서를 고려한 배열.

순열은 보통 순서가 중요한 문제에서 사용되며, 예를 들어 경주에서 상위 3명을 예측하거나, 암호를 풀 때 사용할 수 있다.

 

Combination 조합

조합은 집합의 원소들로 만들 수 있는 모든 가능한 부분 집합. (순서는 고려하지 않음)

조합은 보통 순서가 중요하지 않은 문제에서 사용되며, 예를 들어 로또 번호를 선택하거나 팀을 구성하는 경우 사용할 수 있다. 

 

 

---

순서의 중요성

순서의 중요성은 선택한 원소들이 어떤 순서로 배열되는지를 고려할 것인지를 결정한다.

 

 

순서가 중요한 경우 : 순열

A,B,C 세 개의 글자를 사용해 만들 수 있는 두 글자의 문자열을 만든다 가정했을때, 이런 경우 순서가 중요하기에 "AB" 와 "BA"는 다른 문자열로 취급된다.

 

순서가 중요하지 않은 경우 : 조합

A,B,C 세 개의 글자 중, 두 개의 글자를 선택한다고 가정했을때, 순서가 중요하지 않기때문에 "AB", "BA" 는 같은 조합으로 취급된다.

 

중복을 허용하면서 순서가 중요한 경우 : 중복을 허용하는 순열

A,B,C 세 개의 글자를 사용해 만들 수 있는 두 글자의 문자열을  중복을 허용해서 만든다 가정했을 때, 순서가 중요하므로 "AA","AB","BA"는 모두 다른 문자열로 취급된다. 그 결과, 가능한 문자열은 "AA", "AB", "AC", "BA", "BB", "BC", "CA", "CB", "CC" 총 9개가 된다.

 

중복을 허용하면서 순서가 중요하지 않은 경우 : 중복을 허용하는 조합

A,B,C 세 개의 글자 중, 두 개의 글자를 선택하는데 중복을 허용한다고 가정했을때, 순서가 중요하지 않으므로 "AA", "AB"와 "BA", "AC"와 "CA", "BB", "BC"와 "CB", "CC"는 같은 조합으로 취급된다.  그 결과, 가능한 조합은 "AA", "AB", "AC", "BB", "BC", "CC" 총 6개가 된다.

 

 

---

 

중복허용순열

import java.util.ArrayList;
import java.util.List;

class Solution {
    public static void main(String[] args) {
        String[] arr = {"a", "b", "c"};
        List<String> permutations = generatePermutationsWithDuplicates(arr);
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }

    public static List<String> generatePermutationsWithDuplicates(String[] arr) {
        List<String> permutations = new ArrayList<>();
        backtrackPermutationsWithDuplicates(arr, permutations, new StringBuilder());
        return permutations;
    }

    public static void backtrackPermutationsWithDuplicates(String[] arr, List<String> permutations, StringBuilder current) {
        if (current.length() == arr.length) {
            permutations.add(current.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            current.append(arr[i]);
            backtrackPermutationsWithDuplicates(arr, permutations, current);
            current.deleteCharAt(current.length() - 1);
        }
    }
}

 

---

 

중복을 허용하지 않는 순열

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public static void main(String[] args) {
        String[] arr = {"a", "b", "c"};
        List<String> permutations = generatePermutationsWithoutDuplicates(arr);
        for (String permutation : permutations) {
            System.out.println(permutation);
        }
    }

    public static List<String> generatePermutationsWithoutDuplicates(String[] arr) {
        List<String> permutations = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        backtrackPermutationsWithoutDuplicates(arr, permutations, new StringBuilder(), visited);
        return permutations;
    }

    public static void backtrackPermutationsWithoutDuplicates(String[] arr, List<String> permutations, StringBuilder current, Set<Integer> visited) {
        if (current.length() == arr.length) {
            permutations.add(current.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (visited.contains(i)) {
                continue;
            }
            visited.add(i);
            current.append(arr[i]);
            backtrackPermutationsWithoutDuplicates(arr, permutations, current, visited);
            current.deleteCharAt(current.length() - 1);
            visited.remove(i);
        }
    }
}

 

 

- 중복을 허용하는 순열의 코드

backtrack... 메서드에서 요소의 선택과 제거를 반복한다. 각 재귀호출에서는 모든 요소를 선택하고 다음 재귀호출에서는 요소를 제거하여 순열을 생성한다. 

 

- 중복을 허용하지 않는 순열의 코드

backtrack... 메서드에서 요소의 선택과 제거를 반복한다. 각 재귀호출에서는 선택되지 않은 요소들 중 하나를 선택하고, 선택된 요소를 표시해 중복선택을 방지한다.

 

순서에 따라 중복을 허용하는 순열과 중복을 허용하지 않는 순열의 코드의 차이는 요소의 선택과 방문 여부를 기록하는 부분이다. 중복을 허용하는 순열은 재귀적으로 모든요소를 선택하며, 선택된 요소를 기록하지 않기에 재귀호출 시 모든 요소를 선택할 수 있다. 중복을 허용하지 않는 순열은 재귀호출 시 이미 선택된 요소를 방문표시하여 다시 선택하지 않도록 한다. 일반적으로 Set이나 배열을 사용해 방문한 요소를 기록해 중복선택을 방지하고 중복을 허용하지 않는 순열을 생성한다.

 

 

 

 

---

 

 

프로그래머스 Lv0 문제 -  옹알이[1] 

 

 

나의 풀이  :  중복을 허용하는 순열

permute 메서드는 중복을 허용하는 순열을 생성하는 역할
backtrack 메서드는 재귀적으로 순열을 생성하는 로직을 구현하는 역할
delete 메서드는 시작인덱스와 끝인덱스를 인자로 받아 str에서 특정 범위의 문자열을 삭제하는 메서드

 

재귀호출을 이용해 4개의 옹알이 문자열의 순열을 생성한다. permute 메서드는 arr 배열의 요소들을 중복을 허용해 순열로 만들어 리스트에 저장하는 역할을 한다. 이 메서드는 backtrack 메서드를 호출해 순열을 생성하고 결과를 리스트에 추가한다. backtrack 메서드는 재귀적으로 순열을 생성하는 핵심로직을 담고있다. 이 메서드는 현재까지 선택한 요소를 기준으로 남은 요소들을 선택해 순열을 만들어내는데, 이미 선택된 요소는 방문표시를 하여 중복선택을 방지한다. 그리고 재귀 호출 전 현재 선택된 요소를 리스트에 추가하고, 재귀 호출후에는 리스트에서 제거해 순열을 관리한다. delete 메서드는 재귀 호출 이후 이전에 추가된 문자열을 제거해 이전상태로 돌려놓는 역할을 한다. 이를 통해 재귀 호출이 이전상태를 유지하고 새로운 조합을 생성할 수 있도록 한다.

 

 

 

import java.util.*;

class Solution {
    public int solution(String[] babbling) {
        int count = 0;
        String[] arr = {"aya", "ye", "woo", "ma"};
        List<String> list = permute(arr);

        for(String s : babbling) 
            if(list.contains(s)) count++;
        return count;
    }

    public List<String> permute (String[] arr) {
        List<String> list = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        backtrack(arr, list, new StringBuilder(), visited);
        return list;
    }

    public void backtrack(String[] arr, List<String> list, StringBuilder str, Set<Integer> visited) {
        list.add(str.toString());

        for(int i = 0; i < arr.length; i++){ 
            if(visited.contains(i)) continue;
            visited.add(i);
            int lenBefore = str.length();
            str.append(arr[i]);
            backtrack(arr, list, str, visited);
            str.delete(lenBefore, str.length());
            visited.remove(i);
        } 
    }
}

 

---

 

 

 

 

다른사람 풀이  :  replace()

 

* replace 메서드는 단순 문자열 치환에 사용되고 replaceAll 메서드는 정규식을 이용한 치환에 사용된다.

 

replace 메서드
replace 메서드를 사용해 모든 해당 문자열을 치환한다. replace 메서드는 문자열 내에서 특정패턴을 모두 찾아 다른 문자열로 치환한다. 여러번 반복된 패턴도 모두 치환된다. 예를 들어, "aya woo ye ma".replace("aya", "1")의 결과는 "1 woo ye ma"가 된다.

 

replaceAll 메서드
replaceAll 메서드는 정규식을 이용해 문자열내에서 패턴을 찾아 다른 문자열로 치환한다. 예를 들어, "aya woo ye ma".replaceAll("a|w", "1")의 결과는 "1y1 1oo ye ma"가 됩니다. 정규식을 사용하여 패턴을 더 복잡하게 지정할 수 있습니다.

 

 

class Solution {
    public int solution(String[] babbling) {
        int answer = 0;

        for(int i =0; i < babbling.length; i++) {
            babbling[i] = babbling[i].replace("aya", "1");
            babbling[i] = babbling[i].replace("woo", "1");
            babbling[i] = babbling[i].replace("ye", "1");
            babbling[i] = babbling[i].replace("ma", "1");
            babbling[i] = babbling[i].replace("1", "");
            if(babbling[i].isEmpty()) {
                answer = answer + 1;
            }
        }

        return answer;
    }
}

 

 

---

 

 

 

다른사람 풀이  :  replaceFirst , replaceAll

replaceFirst 메서드
replace 메서드는 첫번째 발견된 패턴만 치환하는 메서드이다.

 

 replaceFirst (speak, " ") 메서드를 이용해 speak 문자열을 첫번째로 만나는 위치에서만 공백 문자로 치환한다. repBabb 문자열에서 모든 공백을 제거한 결과가 빈 문자열인 경우, 즉 "aya","ye","woo","ma" 가 모두 삭제됐을때, answer값을 1 증가시킨다. 반복이 완료되면 answer 값을 반환한다. 이 코드는 입력된 문자열 배열에서 특정 패턴들을 삭제하고, 삭제된 문자열을 개수를 카운트하는 방식으로 작동한다. replaceFirst 메서드를 사용해 해당 패턴을 첫번째로 만나는 위치에서만 치환하므로, 중복되는 패턴은 하나만 삭제된다. 이를 통해 "aya","ye","woo","ma"가 중복으로 존재할 때도 각각 한번만 삭제되므로 answer값은 삭제된 문자열을 개수가 된다.

 

class Solution {
    public int solution(String[] babbling) {
        int answer = 0;
        String[] speakList = {"aya", "ye", "woo", "ma"};
        String repBabb;
        for(String babb : babbling){
            repBabb = babb;
            for(String speak : speakList){
                repBabb = repBabb.replaceFirst(speak, " ");
            }
            if(repBabb.replaceAll(" ","").equals("")){
                answer++;
            }
        }

        return answer;
    }
}