[Java]문자 반복 찾기 없이 가장 긴 하위 문자열 찾기

 

https://examples.javacodegeeks.com/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters

안녕하세요. 이번 자습서에서는 데이터 구조에 대한 주요 질문 중 하나인 문자 반복 찾기 없이 가장 긴 하위 문자열 찾기에 대한 구현 해보려고 합니다.

 

1. 소개

구현은 다음과 같은 세 가지 부분에 대해서 알아 볼 것입니다.

 

Brute force 방법 – 주어진 문자열에 포함 된 유일 문자를 포함하는 하위 문자열을 생성하고 해당 문자의 최대 개수를 반환하는 가장 간단한 방법

슬라이딩 윈도우 방법 – 반복 가능한 작업들의 성능을 O(N^2)로 향상

최적화된 슬라이딩 윈도우 방법 - 복잡도 O(1)에 근접하도록 라이딩 윈도우로 HashSet을 사용

 

2. 연습

여기에서 몇 가지 연습을 위한 도구을 살펴보겠습니다. 로컬 컴퓨터에 Java 1.8 이상이 이미 설치되어 있다고 가정합니다.

나는 내가 선호하는 IDE 인 JetBrains IntelliJ IDEA를 사용하고 있습니다.

당신이 원하는 IDE를 자유롭게 선택할 수 있습니다.

 

2.1 구현 클래스 만들기

위에서 설명한 위의 3가지 방법의 구현을 보여주는 java 파일을 만듭니다. 알고리즘 요구 사항에 따라 코드를 자유롭게 변경할 수 있습니다.

 

구현 클래스

package com.practice;
 
/*
 * jcg : category: core java
 * 1. brute force method
 * 2. sliding window method
 * 3. sliding window optimized
 */
 
class Bruteforce {
 
  // 루프를 이용해서 처음부터 끝까지 문자열의 모든 하위 문자열을 찾습니다.
  // 하위 문자열에 모든 유일 문자가 포함되어 있는지 확인하려면 모든 문자를 세트에 하나씩 넣습니다.
  // 세트에 문자가 있으면 해당 문자열을 건너뛰고 그렇지 않으면 해당 문자의 길이를 고려합니다.
  public long bruteforce(String str) {
    int n = str.length();
    int res = 0;
 
    for (int i = 0; i < n; i++) {
      for (int j = i; j < n; j++) {
        if (checkRepetition(str, i, j)) {
          res = Math.max(res, j - i + 1);
        }
      }
    }
    return res;
  }
 
  private boolean checkRepetition(String s, int start, int end) {
    int[] chars = new int[128];
 
    for (int i = start; i <= end; i++) {
      char c = s.charAt(i);
      chars++;
      if (chars > 1) {
        return false;
      }
    }
    return true;
  }
}
 
class SlidingWindow {
 
  

  // 이 접근 방식에서는 하위 문자열을 고려할 필요를 건너뛰고 하위 문자열에 중복 문자가 포함되어 있는지 확인합니다.
  // 우리는 반복 작업을 개선하는 데 중점을 둘 것입니다.
  // index에서 j-1 인 하위문자열에 중복 문자가 없는지 이미 확인된 다음 
  // s[j]가 s[i][j]의 하위 문자열인지 확인을 단순화합니다.
  public long slidingwindow(String str) {
    int n = str.length();
    int res = 0;
 
    for (int i = 0; i < n; i++) {
      boolean[] visited = new boolean[256];
      for (int j = i; j < n; j++) {
        if (visited[str.charAt(j)]) {
          break;
        } else {
          res = Math.max(res, j - i + 1);
          visited[str.charAt(j)] = true;
        }
      }
      visited[str.charAt(i)] = false;
    }
    return res;
  }
}
 
class OptimizedSlidingWindow {
 
  // 하위 문자열이 다른 문자열을 사용하는지 확인하는 슬라이딩 방식에서 복잡성은 o(n^2) 번입니다.
  // 이를 더 개선하기 위해 HashSet을 슬라이딩 윈도우로 사용할 수 있습니다. 여기서 우리는
  // 해당 문자를 이미 방문했고 현재 창에 있다면 복잡도는 o(1)에서 수행할 수 있습니다.
  // 여기에서 우리는 문자열에서 반복되지 않는 최대 하위 문자열을 추적하기 위해 
  // left 및 right 포인터를 사용합니다.
  public long optimizedslidingwindow(String str) {
    int[] chars = new int[128];
    int left = 0;
    int right = 0;
    int res = 0;
 
    while (right < str.length()) {
      char r = str.charAt(right);
      chars[r]++;
      while (chars[r] > 1) {
        char l = str.charAt(left);
        chars[l]--;
        left++;
      }
      res = Math.max(res, right - left + 1);
      right++;
    }
    return res;
  }
}
 
public class LongestStringWithoutRepeatingCharactersEx {
 
  public static void main(String[] args) {
    Bruteforce bf = new Bruteforce();
    System.out.println("\nBruteforce method = " + bf.bruteforce("enjoyalgorithms"));
 
    SlidingWindow sd = new SlidingWindow();
    System.out.println("\nSlidingwindow method = " + sd.slidingwindow("enjoyalgorithms"));
 
    OptimizedSlidingWindow osd = new OptimizedSlidingWindow();
    System.out.println(
        "\nOptimizedslidingwindow method = " + osd.optimizedslidingwindow("enjoyalgorithms"));
  }
}

 

3. 데모

파일을 java 파일로 실행하고 잘 설정 했다면, IDE 콘솔에 다음 로그가 표시 될 것입니다

자습서의 끝이네요. 이 기사가 여러분이 찾고 있는 모든 것을 제공했기를 바랄께요. 행복하게 학습하시고 공유하는 것도 잊지 마세요!

 

4. 요약

이 자습서에서는 반복 문자 찾기 없이 가장 긴 하위 문자열을 찾는 실용적인 구현에 대해 논의해 보았습니다. 다운로드 섹션에서 여기서 사용 된 소스 코드를 다운로드할 수 있습니다.

 

5. 프로젝트 다운로드

반복 문자 찾기 없이 가장 긴 하위 문자열을 찾기 위한 실제 구현을 이해하기 위한 자습서였습니다.

 

 

이상.