LeetCode, Longest Substring Without Repeating Characters (Golang)

Longest Substring Without Repeating Characters

첫번째 풀이 O(n2)

처음 접근

처음 접근법은 abcabcbb, 이중 반복문을 통해서 첫번째 문자열과 일치하는지를 확인하고, 일치하면, 거기서 break를 걸어서 문자열 대치를 진행했다. 문제점은 첫번째 문자열만 일치한다는 점이였고, 2, 3 ... 이어지는 문자열이 존재하는지는 확인하지 못했다.

 

확인 불가

 

 

따라서 수정한 접근, Hash Map을 활용한 Brute Force - O(n2)

 

그래서 HashMap을 따로 생성하여, 반복적으로 확인하는 문자열마다 HashMap에 존재여부를 판단하여, 진행한다.

    a := "abcabcbb"
    var ans, tmp int = 0, 0
    var hMap = make(map[rune]int)

    for j, i := range a {
        hMap[i] = 1
        tmp = 1

        for _, k := range a[j+1:] {
            _, exists := hMap[k]
            if !exists {
                tmp++
                hMap[k] = 1
            } else {
                break
            }
        }

        if ans < tmp {
            ans = tmp
        }
    }

    return ans

 

Details

Runtime: 334 ms, faster than 14.81% of Go online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 10.2 MB, less than 5.65% of Go online submissions for Longest Substring Without Repeating Characters.

 

LeetCode 풀이법 투 포인터 이용 알고리즘 O(n)

 

투포인터 알고리즘은 두 개의 포인터, 즉 left, right 나누어서 윈도우 내에 있는 데이터를 이용해서 left, right 포인터를 바꿔가며, 풀이하는 알고리즘을 말합니다. 이렇게 하면, 이중 반복문을 쓰지 않는 결과가 나옵니다. 

    a := "abcabcbb"

    var left, right, res int
    ch := make(map[byte]int)

    for right < len(a) {

        // 존재하는지 확인!
        index, exist := ch[a[right]]
        fmt.Println(index, exist)

        // 존재하면, 존재하는 index 인덱스에서 right 다시 증명 시작
        // left가 존재하는 다음 자리에서 다시 증명을 시작하는 이유는
        // 이미 right까지 중복한 숫자가 없다는 것을 증명했기 떄문
        if exist && index >= left {
            left = index + 1
        }

        if res < right-left+1 {
            res = right - left + 1
        }

        ch[a[right]] = right

        right += 1
    }

투포인터를 이용해서, 알고리즘을 수정하면 O(n)이라는 결과값이 나옵니다.

 

Details

Runtime: 8 ms, faster than 74.88% of Go online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 2.9 MB, less than 76.09% of Go online submissions for Longest Substring Without Repeating Characters.