문자열에서 반복되는 문자 제거

1. 개요

이 자습서에서는 문자열에서 반복되는 문자를 제거하는 방법에 대한 Java의 여러 기술에 대해 설명합니다.

각 기술에 대해 시간 및 공간 복잡성에 대해서도 간략히 설명합니다.

2. 구별 사용

Java 8에 도입 된 고유 한 방법을 사용하여 문자열에서 중복을 제거하는 것으로 시작하겠습니다 .

아래에서는 주어진 문자열 객체에서 Int S tream 의 인스턴스를 얻습니다 . 그런 다음 고유 한 방법을 사용 하여 중복을 제거합니다. 마지막으로 forEach 메서드를 호출하여 고유 한 문자를 반복하고 StringBuilder에 추가합니다 .

StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));

시간 복잡도 : O (n) – 루프의 실행 시간은 입력 문자열의 크기에 정비례합니다.

보조 공간 : O (n)distinct 는 내부적 으로 LinkedHashSet을 사용 하고 결과 문자열을 StringBuilder 객체 에 저장하기 때문에

순서 유지 : 예 – LinkedHashSet 이 요소의 순서를 유지하므로

그리고 Java 8이 우리를 위해이 작업을 훌륭하게 수행하는 것은 좋지만 우리 자신의 노력과 비교해 봅시다.

3. indexOf 사용

문자열에서 중복을 제거하는 순진한 접근 방식은 단순히 입력을 반복하고 indexOf 메서드를 사용 하여 현재 문자가 결과 문자열에 이미 존재하는지 확인하는 것입니다 .

StringBuilder sb = new StringBuilder(); int idx; for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); idx = str.indexOf(c, i + 1); if (idx == -1) { sb.append(c); } } 

시간 복잡성 : O (n * n) – 각 문자에 대해 indexOf 메서드가 나머지 문자열을 통해 실행됩니다.

보조 공간 : O (n)StringBuilder 를 사용하여 결과를 저장 하므로 선형 공간이 필요합니다.

주문 유지 :

이 방법은 첫 번째 방법과 동일한 공간 복잡성을 갖지만 성능이 훨씬 느립니다.

4. 문자 배열 사용

문자열을 문자 배열 로 변환 한 다음 각 문자를 반복하고 모든 후속 문자와 비교하여 문자열에서 중복을 제거 할 수도 있습니다 .

아래에서 볼 수 있듯이 두 개의 for 루프를 만들고 각 요소가 문자열에서 반복되는지 확인하고 있습니다. 중복이 발견되면 StringBuilder에 추가하지 않습니다 .

char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); boolean repeatedChar; for (int i = 0; i < chars.length; i++) { repeatedChar = false; for (int j = i + 1; j < chars.length; j++) { if (chars[i] == chars[j]) { repeatedChar = true; break; } } if (!repeatedChar) { sb.append(chars[i]); } } 

시간 복잡성 : O (n * n) – 입력 문자열을 순회하는 내부 및 외부 루프가 있습니다.

보조 공간 : O (n)chars 변수가 문자열 입력의 새 사본 을 저장하고 결과를 저장하기 위해 StringBuilder 를 사용 하므로 선형 공간이 필요합니다.

주문 유지 :

다시 말하지만 두 번째 시도는 Core Java 제품에 비해 성능이 좋지 않지만 다음 시도에서 얻을 수있는 위치를 살펴 보겠습니다.

5. 정렬 사용

또는 입력 문자열을 정렬하여 중복 된 항목을 그룹화하여 반복되는 문자를 제거 할 수 있습니다. 그렇게하려면 문자열을 char a rray 로 변환 하고 Arrays를 사용하여 정렬해야합니다 . 정렬 방법 . 마지막으로 정렬 된 char 배열을 반복합니다 .

반복 할 때마다 배열의 각 요소를 이전 요소와 비교할 것입니다. 요소가 다르면 현재 문자를 StringBuilder에 추가합니다 .

StringBuilder sb = new StringBuilder(); if(!str.isEmpty()) { char[] chars = str.toCharArray(); Arrays.sort(chars); sb.append(chars[0]); for (int i = 1; i < chars.length; i++) { if (chars[i] != chars[i - 1]) { sb.append(chars[i]); } } }

시간 복잡성 : O (n log n) – 정렬은 많은 데이터 세트에서 O (n log n) 성능을 제공하는 이중 피벗 Quicksort를 사용합니다.

보조 공간 : O (n)toCharArray 메서드가 입력 문자열 의 복사본을 만들기 때문에

주문 유지 : 아니오

마지막 시도로 다시 시도해 봅시다.

6. 세트 사용

Another way to remove repeated characters from a string is through the use of a Set. If we do not care about the order of characters in our output string we can use a HashSet.Otherwise, we can use a LinkedHashSet to maintain the insertion order.

In both cases, we'll loop over the input string and add each character to the Set. Once the characters are inserted into the set, we'll iterate over it to add them to the StringBuilder and return the resulting string:

StringBuilder sb = new StringBuilder(); Set linkedHashSet = new LinkedHashSet(); for (int i = 0; i < str.length(); i++) { linkedHashSet.add(str.charAt(i)); } for (Character c : linkedHashSet) { sb.append(c); } 

Time Complexity: O(n) – runtime of the loop is directly proportional to the size of the input string

보조 공간 : O (n)세트 에 필요한 공간 은 입력 문자열의 크기에 따라 다릅니다. 또한 결과를 저장하기 위해 StringBuilder 를 사용하고 있습니다.

순서 유지 : LinkedHashSet – 예, HashSet – 아니오

이제 우리는 Core Java 접근 방식과 일치했습니다! 이것이 분명한 것과 매우 유사하다는 것을 알아내는 것은 그리 충격적이지 않습니다.

7. 결론

이 기사에서는 Java의 문자열에서 반복되는 문자를 제거하는 몇 가지 방법을 다뤘습니다. 또한 이러한 각 방법의 시간 및 공간 복잡성도 조사했습니다.

항상 그렇듯이 코드 조각은 GitHub에서 찾을 수 있습니다.