GRIND75- Week 8

중위순회 하면 오름차순으로 들어간다

 

 

 

 

#2

 

 

better, faster solution :)

이 코드에서 주어진 두 문자열 `s`와 `t`로부터 `t`의 모든 문자가 포함된 `s`의 최소 윈도우 문자열을 찾습니다. 코드를 단계별로 설명해 드리겠습니다.

### 코드 설명:

1. **예외 처리**:
   ```java
   if(s==null || t==null || s.length()==0 || t.length()==0 || s.length()<t.length()){
       return new String();
   }
   ```
   여기서는 `s`나 `t`가 null이거나 길이가 0일 때, 혹은 `s`의 길이가 `t`보다 짧으면 빈 문자열을 반환합니다. 이는 `t`의 모든 문자를 `s`에서 찾을 수 없는 경우를 처리하기 위한 것입니다.

2. **필요한 문자 개수 카운팅**:
   ```java
   int count = t.length();
   int []cnt = new int[128];
   for(char ch : t.toCharArray()){
       cnt[ch]++;
   }
   ```
   `count`는 `t`에서 필요한 총 문자 수를 나타냅니다. `cnt` 배열은 ASCII 값을 기반으로 각 문자의 개수를 저장합니다. 여기서 `t`의 각 문자를 반복하며 `cnt` 배열에 해당 문자의 빈도를 증가시킵니다.

3. **윈도우 탐색**:
   ```java
   char []ch = s.toCharArray();
   int strt = 0, end = 0, min = Integer.MAX_VALUE, idx = 0;
   ```
   - `strt`와 `end`는 슬라이딩 윈도우의 시작과 끝을 나타내는 포인터입니다.
   - `min`은 최소 윈도우 길이를 저장하는 변수입니다.
   - `idx`는 최소 윈도우의 시작 위치를 저장합니다.

4. **윈도우 확장**:
   ```java
   while(end < ch.length){
       if(cnt[ch[end++]]-- > 0){
           count--;
       }
   ```
   `end` 포인터를 확장하면서 `s`의 현재 문자가 `cnt` 배열에 기록된 값보다 많다면 `count`를 감소시킵니다. 이는 `t`의 필요한 문자가 포함된 경우를 확인하는 것입니다.

5. **윈도우 축소**:
   ```java
   while(count == 0){
       if(end - strt < min){
           idx = strt;
           min = end - strt;
       }
       if(cnt[ch[strt++]]++ == 0){
           count++;
       }
   }
   ```
   - `count`가 0이면 현재 윈도우에 `t`의 모든 문자가 포함된 상태입니다.
   - 이때, 현재 윈도우의 길이(`end - strt`)가 `min`보다 작다면 `min`과 `idx`를 갱신합니다.
   - `strt` 포인터를 증가시키면서 윈도우를 축소하고, 만약 `cnt[ch[strt]]`가 0이라면 `count`를 증가시킵니다. 이는 `t`의 문자가 더 이상 포함되지 않는 경우를 처리하는 것입니다.

6. **결과 반환**:
   ```java
   return min == Integer.MAX_VALUE ? new String() : new String(ch, idx, min);
   ```
   - `min`이 초기값 `Integer.MAX_VALUE`라면 유효한 윈도우가 없으므로 빈 문자열을 반환합니다.
   - 그렇지 않으면 `s`의 `idx`부터 `min` 길이만큼의 서브 문자열을 반환합니다.

### 요약
이 코드는 `t`의 모든 문자가 포함된 `s`의 최소 윈도우를 찾기 위해 슬라이딩 윈도우와 카운팅 배열을 활용합니다.

 

 

 

 

#3