algorithm/problem solving

leetcode 974(prefix sum), 1375(구현;), 93(백트래킹), 616(merge interval)

qkqhxla1 2022. 1. 3. 21:14

974 https://leetcode.com/problems/subarray-sums-divisible-by-k/
subarray의 합이 k로 나눠지는 subarray를 구해야하는데 인덱스와 상관없이 구하는게 아니라 근처의 값들로만 구성해야 해서 백트래킹같은게 아니다. 앞에서부터 prefix sum을 계산해주며 prefix sum이 k로 나눠지면 그 값이 존재하는만큼 더해준다. 그리고 뒤에서도 사용하기 위해 그 값이 나온만큼 증가시켜준다.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        ret = 0
        d = {0: 1}
        prefix_sum = 0
        for i in range(len(nums)):
            prefix_sum += nums[i]
            key = prefix_sum % k
            if key not in d:
                d[key] = 1
            else:
                ret += d[key]
                d[key] += 1
        return ret


1375 https://leetcode.com/problems/number-of-times-binary-string-is-prefix-aligned/
별생각없이 비트 연산자로 하나하나 구현을 했고 답은 나왔는데 좀 느렸다. 그래서 뭐가 잘못된거지 하고 다른사람들의 답을 봤는데.. 대박 좀 읽어보면 원 지문은 현재 지문과 좀 달랐던것 같다. 그래도 유추해서 요지는 이해할수 있다.

1-indexed기준으로 i번째의 비트를 1로 전환했을때 그 i번째가 가장 오른쪽에 있는 경우와 같으면 그게 prefix-aligned이다.
그러니까.. 예로 5개를 채웠는데 가장 오른쪽의 비트가 5라고 하면 5개가 전부 왼쪽에 전부 들어갔을것이므로 자동으로 prefix-aligned가 된다. 5개를 채웠는데 가장 오른쪽의 비트가 7이다? 그러면 중간 어디가 비어있다는 뜻이므로 아니다.
결국 n개를 채웠는데 가장 오른쪽의 비트가 n이다? 그럼 prefix-aligned이다. 와 진짜 알고리즘 문제 보고 구현할 생각만 했지 이렇게 방법을 떠올릴 생각은 못했네

class Solution:
    def numTimesAllBlue(self, flips: List[int]) -> int:
        rst = 0
        cur_max = 0
        for i, l in enumerate(flips):
            cur_max = max(cur_max, l)
            # everytime meet max, increase rst
            if i + 1 == cur_max:
                rst += 1
        return rst


93 https://leetcode.com/problems/restore-ip-addresses/
s의 길이가 20 이하이니 dp가 아니라 백트래킹으로 구현만 해도 된다. 재귀적으로 구현한다.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        ret = []
        def get_ip(s, made_ip):
            if len(made_ip) > 4:  # ip주소가 4자리 이상이면 무시
                return
            if s == '':  # 더 만들만한 거리가 없는데
                if len(made_ip) == 4:  # 4자리이면 .으로 조인
                    ret.append('.'.join(made_ip))
                return

            if s[0] == '0':  # 0으로 시작하면 무조건 앞자리는 0임.
                get_ip(s[1:], made_ip + ['0'])
            else:
                if len(s) >= 3 and int(s[:3]) < 256:  # 3자리 이상이고 앞 3자리가 256보다 작아야함.
                    get_ip(s[3:], made_ip + [s[:3]])  # 3자리 끊어탐색
                if len(s) >= 2:  # 남은 길이가 2이상이면 2자리 탐색
                    get_ip(s[2:], made_ip + [s[:2]])
                get_ip(s[1:], made_ip + [s[0]])  # 1자리 탐색.
                
        get_ip(s, [])
        return ret


616 https://leetcode.com/problems/add-bold-tag-in-string/
하나하나 다 검사하면 당연히 시간초과가 나니까 미리 가지치지로 갯수를 줄여놔야 한다.
1. 단어 리스트중 실제로 존재하는 단어들을 검색해봐서 위치값을 저장해놓는다.
2. 존재하는 단어들의 위치값 리스트를 머지해준다. https://leetcode.com/problems/merge-intervals/ 를 참고하자.
3. 머지된 단어 리스트로 일일히 <b>태그를 붙여준다. 

class Solution:
    def addBoldTag(self, s: str, words: List[str]) -> str:
        word_range = []
        words = set(words)
        for w in words:
            len_w = len(w)
            for i in range(len(s)-len_w+1):
                if s[i:i+len_w] == w:
                    word_range.append([i, i+len_w])
        word_range.sort()
        
        new_word_range = []
        for i in range(len(word_range)):
            if not new_word_range:
                new_word_range.append(word_range[i])
            elif new_word_range[-1][1] >= word_range[i][0]:
                new_word_range[-1][1] = max(new_word_range[-1][1], word_range[i][1])
            else:
                new_word_range.append(word_range[i])

        for new_word in new_word_range[::-1]:
            s = s[:new_word[0]] + '' + s[new_word[0]:new_word[1]] + '' + s[new_word[1]:]
        return s