[Leetcode / Python] 2375. Construct Smallest Number From DI String

난이도 : medium

 

길이가 n인 문자열 pattern에서 I는 증가하는 것, D는 감소하는 것을 의미

길이가 n+1인 숫자 num은, 1부터 9까지의 숫자에서 하나씩만 사용하며, num[i]와 num[i+1] 사이에 다음과 같은 규칙을 만족할 때, num의 최소값을 구하는 문제

 

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        n = len(pattern)
        result = []
        a = list(range(1, 10)) 
    
        for i in range(n + 1):
            if i == n or pattern[i] == 'I':
                result.append(min(a))
                a.remove(min(a))
            else:
                count = 1
                while i + count < n and pattern[i + count] == 'D':
                    count += 1
                result.append(a[count])
                a.remove(a[count])
        
        return ''.join(map(str, result))

1. 1부터 9까지의 리스트 a를 만듬
2. i가 n이거나 pattern이 I면, result에서 리스트 a의 min값을 더하고, 동일 값을 a에서 제거
3. pattern이 D면, D가 연속으로 있는 갯수를 확인하고, D의 개수에 해당하는 index의 숫자를 결과에 result에 추가 및 a에서 제거

Runtime : 3ms (25.88%)

Memory : 17.97MB (17.18%)

 

이 code를 더 효율적으로 만드는 방법을 확인하기 위해 perplexity에 도움을 요청!

class Solution:
    def smallestNumber(self, pattern: str) -> str:
        result = []
        stack = []
        
        for i, char in enumerate(pattern + 'I'):
            stack.append(str(i + 1))
            if char == 'I':
                result.extend(stack[::-1])
                stack = []
        
        return ''.join(result)

1. pattern + 'I'를 enumerate하여, stack에 i+1을 문자열로 추가
2. 'I'일 때, stack을 뒤집어서 result에 추가하고 리스트 stack 초기화
3. 'D'일 때에는, stack이 초기화되지 않고 쌓이다가, 마지막 char는 'I'이기 때문에 리스트 stack을 뒤집어서 result에 추가

Runtime : 0ms

Memory : 17.79MB (54.04%)