24-06-12 알고리즘 문제 풀이

오늘부터는 어제부터 시작된 프로젝트의 코드 작성을 시작했다. 이전에 경험해보지 못한 협업 방식들을 이용했기 때문에 살짝 걱정했는데 적응하고 나니 아주 편하다는 것을 알게되었다. Git, GitHub이나 여러 협업 도구들에 대해서도 따로 공부를 해보아도 괜찮겠다는 생각이 들었다.

 

여기에는 프로젝트 이후 시간에 풀어본 알고리즘 문제 풀이를 정리해보았다.

 

1. 알고리즘 문제 풀이

오늘은 leetcode에 있는 '3. Longest Substring Without Repeating Characters' 문제를 풀어보았다.

1-1. 풀어본 문제

[문제]

문자열 s가 주어졌을 때, 반복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구하세요

 

- 예시 1

입력: s = "abcabcbb"

출력: 3

설명: 답은 "abc"이고, 문자열의 길이는 3 입니다.

 

- 예시 2

입력: s = "bbbb"

출력: 1

설명: 답은 "b"이고, 문자열의 길이는 1입니다.

 

-예시 3

 

입력: s = "pwwkew"

출력: 3

설명: 답은 "wke"이고, 문자열의 길이는 3입니다. 답이 반드시 부분 문자열이어야함을 참고하세요. "pwke"는 부분 문자열이 아니라 부분 문자들의 나열입니다.

 

- 제한 사항

• $ 0 {\;}{\leq}{\;} s.length {\;}{\leq}{\;} 5 × 10^{4} $
• s는 영문자와 숫자, 기호, 공백으로 이루어져 있습니다.

 

1-2. 문제 풀이

문제 풀이에 앞서 슬라이딩 윈도우라는 알고리즘에 대해 공부하게되었다. 개념 자체는 쉽게 이해가 되었는데 실제로 코드로 구현하려니 머리가 아픈 부분이 있었다. 그래서 문제를 푸는데 생각보다 오래 걸리게 되었다.

 

어찌 되었든 가장 간단하게 설명하자면 left, right라는 두 포인터를 두고 right의 경우는 계속 1씩 증가하게 되고, left의 경우는 특정 조건 하에서만 움직이도록 코드를 작성하면 된다.

 

먼저 문자와 문자가 마지막으로 등장한 인덱스를 저장할 수 있는 맵을 선언해준다. 그리고 최대 길이라고 할 수 있는 answer를 하나 선언해주었다. 그리고 두 개의 포인터가 있다. 그런 다음 문자열의 하나의 문자에 대해 작업을 반복하면 된다.

 

map에는 기본적으로 문자 하나와 그 문자가 마지막으로 등장한 인덱스가 저장되게 된다.

 

그리고 문자열에 있는 하나의 문자에 대해 다음과 같은 작업이 반복된다.

 

해당 문자가 이전에 등장한 적이 없거나(map에 key 값으로 저장되어있지 않음), 마지막으로 등장했던 곳이 left 포인터보다 앞에 있다면(이미 left 포인터가 그 곳을 지나쳤기 때문에 무시해야 한다) left 포인터를 해당 문자가 등장했던 곳 바로 앞으로 이동시키면 된다.

 

해당 문자가 등장한 적이 없거나, 마지막으로 등장했던 곳이 left 포인터보다 더 뒤에 있다면 left 포인터는 이동하지 않고 현재 상태에서 두 포인터의 길이를 구해 answer 보다 클 경우 값을 업데이트 해주기만 하면 된다.

 

그런 다음 현재 문자를 right 포인터의 인덱스 값을 값으로 하여 맵에 저장한뒤, right 포인터를 한 칸 앞으로 옮기기만 하면된다.

 

위와 같이 말로 잘 풀어 설명해도 바로 로직이 이해가 쉽지는 않은데, 실제 코드를 작성하는 것도 쉽지만은 않았다.

 

설명대로 작성한 코드는 아래와 같다.

 

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val map: MutableMap<Char, Int> = mutableMapOf()
        var answer = 0
        var left = 0
        var right = 0

        for (char in s) {
            // 해당 문자가 등장한 적이 없거나,
            // 마지막으로 등장했던 곳이 left 포인터보다 앞에 있을때
            if (left <= map.getOrDefault(char, -1)) {
                left = map[char]!! + 1
            // 해당 문자가 등장한 적이 있거나,
            // 마지막으로 등장했던 곳이 left 포인터보다 뒤에 있을 때
            } else {
                answer = answer.coerceAtLeast(right - left + 1)
            }
            
            map[char] = right

            right++
        }

        return answer   
    }
}

위와 같이 작성하면 답안으로 잘 통과된다. 

 

몇 줄 안되는 간단한 코드로 위와 같이 구현할 수 있었지만 생각해내고 적용하는 과정은 쉽지 않았다. 알고리즘 문제 풀이에 익숙해지려면 오랜 시간이 필요할 것 같다. 하루에 하나씩이라도 꾸준히 하는 것이 중요한 것 같다.

 

2. 오늘 배운 것

- 팀 프로젝트를 진행하면서 협업하는 법에 대해서 계속 배우게되는 것 같다. 앞으로 진행될 프로젝트에도 잘 적용해 보아야겠다.

- QueryDsl에 대해 익숙해지려고 연습을 하는 중이다. 잘 사용한다면 좋은 도구가 될 것 같다.