서브스트링

문자열 s 중에서 부분 문자열을 추출하여 찾아보는 문제였다.

처음에는 문자열을 순회하면서 index이동을 시키는 방향으로 고민하여 해결하였는데

가능한 모든 문자열을 포함하여 순회하는 경우에는 계속 실패하여 95이상의 길이에서는 리턴해주는 코드를 작성하였다.

하지만 이는 완벽한 풀이라고 보기에는 무리가 있었다. 긴 문자열 내에서도 타임 리밋 없이 해결하기 위해서는 코드의 변경이 필요했다.

func isUniq(elements map[string]bool, cur string) bool {
    if elements[cur] {
        return false
    }
    return true
}

func max(largest int, length int) int {
  if largest < length {
    return length
  } else {
    return largest
  } 
}

func main(s string) int {
    largest := 0
    nextidx := 0
    for i := nextidx; i < len(s); i++ {
        curElements := make(map[string]bool, len(s));
        
        for j := i; j < len(s); j++ {
            if isUniq(curElements, string(s[j])) { // 유니크한 문자일 경우 map 데이터에 추가
                curElements[string(s[j])] = true
                largest = max(largest, len(curElements))
            } else {
                largest = max(largest, len(curElements)) // 유니크 하지 않을 경우 최대길이인치 확인후
                nextidx = j + 1 // 다음 인덱스 이동
                break
            }
            if len(curElements) >= 95 {
                return 95
            }
        }
    }
    
    return largest
}

이를 해결하기 위해서 슬라이딩 윈도우 알고리즘을 사용할 수 있다.

"a d s e d g"
 i j
"a d s e d g"
 i   j
"a d s e d g"
 i     j
"a d s e d g"
 i       j
"a d s e d g"
     i     j 

이런 식으로 창문이라고 생각하고 한쪽을 확장해 나가면서 문제를 풀어야하는 방식의 문제에서 많이 사용된다.

TCP 네트워크에서 실제로 사용하는 알고리즘이라고 한다. 함께 확인하면 좋을것 같다.

func max(i int, j int) int {
    if i > j {
        return i
    } else {
        return j
    }
}

func main(s string) int {
    var i, largest int
    hashMap := make(map[byte]int, len(s))
    
    for j, _ := range s {
        if hashMap[s[j]] != 0 {
            i = max(hashMap[s[j]], i)
        }
        
        hashMap[s[j]] = j + 1
        largest = max(largest, j + 1 - i)
    }
    return largest
}

이렇게 문제를 풀수 있다.

런타임 자체도 O(N)으로 줄일수 있고

여기서 메모리 사용량을 줄이 기 위해서는

func main(s string) int {
    var i, largest int
    hashMap := make(map[rune]int)
    
    for j, v := range s {
        if count, ok := hashMap[v]; ok && count > i  {
            i = count
        }
        
        hashMap[v] = j + 1
        if cur := j + 1 - i; largest < cur {
            largest = cur
        }
    }
    return largest
}

이렇게 할 수 있다. Runtime: 12 ms, Memory Usage: 3.3 MB