[LeetCode] 942. DI String Match

- Problem

942. DI String Match

pern은 s의 길이 + 1만큼의 크기를 가진다. 즉, [0, 1, ..., len(s)]의 원소를 갖게 된다.

예를 들어, 주어진 문자열이 s = "DDIIDI"라면 s의 길이는 6으로 perm은 [0,1,2,3,4,5,6]을 갖게 되는 것이다.

이러한 perm의 순열 중 다음 조건을 만족하는 순열을 찾는 문제이다.

• s[i] == 'I' if perm[i] < perm[i + 1]
• s[i] == 'D' if perm[i] > perm[i + 1]

python의 itertools 모듈을 활용한다면 쉽게 풀 수 있겠지만, 문제 조건을 보면 s의 길이는 최대 10^5이다. permutation 메서드를 사용한다면 굉장히 아주 굉장히 느리고 비효율적인 코드가 될 것이다.

다음 코드를 보자.

class Solution:
    def check_match(self, p: list, s: str) -> list:
        for i in range(len(s)):
            if s[i] == "I" and p[i] > p[i+1]:
                return False
            
            if s[i] == "D" and p[i] < p[i+1]:
                return False
        
        return True
    
    def diStringMatch(self, s: str) -> List[int]:
        perm = list(range(0, len(s) + 1))
        
        for p in itertools.permutations(perm):
            if self.check_match(p, s):
                return p

itertools의 permutations 메서드를 활용한 코드이다. 위의 코드로 제출할 경우 다음과 같은 결과를 얻는다.

주어진 문자열의 길이가 10만 되도 시간 초과로 터진다.

- 내 풀이

class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        start, end = 0, len(s)
        answer = []
        
        for i in range(len(s)):
            if s[i] == "I":
                answer.append(start)
                start += 1
            
            else:
                answer.append(end)
                end -= 1
        
        answer.append(start)
        # answer.append(end) # start = end
        
        return answer

- 결과