[LeetCode] LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters - python3

간만에 재밌는 문제를 만났다. 

 

1576. Replace All ?'s to Avoid Consecutive Repeating Characters 문제인데 문제 자체도 재밌고 풀이 방식을 보던 중 꽤나 기발한 접근법을 보게 되어서 인상깊어서 기록해둔다. 

 

우선 문제 링크는 아래와 같다. 

 

https://leetcode.com/problems/replace-all-s-to-avoid-consecutive-repeating-characters/

Replace All ?'s to Avoid Consecutive Repeating Characters - LeetCode

 

자 이제 내가 풀이한 솔루션을 보도록 하겠다. 

 

'''
Runtime: 62 ms, faster than 31.15% of Python3 online submissions for Replace All ?'s to Avoid Consecutive Repeating Characters.
Memory Usage: 14 MB, less than 27.40% of Python3 online submissions for Replace All ?'s to Avoid Consecutive Repeating Characters.

코멘트:
꽤나 재밌었던 문제다. 조금 까다롭기도 했고 조건을 세세하게 주는게 꽤나 신경쓰이던 문제였다. 
분명 이것보다 쉽게 푸는 방법이 있을거라는 생각이 드는데... 어떻게 하면 더 쉽게 풀 수 있을까? 
'''
class Solution:
    def modifyString(self, s: str) -> str:
        # 1003 ~ 1020 
        alpha = 'abcdefghijklmnopqrstuvwxyz'
        result = list(s)
        for i in range(len(s)):
            print(result)
            if result[i] == '?':
                if i == 0: # 0번째 인덱스라면 
                    for c in alpha:
                        if i + 1 < len(s) and c != result[i + 1]:
                            result[i] = c
                            break     
                        if i + 1 >= len(s):
                            result[i] = c
                            break 
                elif i == len(s) - 1: # 마지막 인덱스라면 
                    for c in alpha:
                        if i - 1 >= 0 and c != result[i - 1]:
                            result[i] = c
                            break 
                        if i - 1 < 0:
                            result[i] = c
                            break 
                else:    
                    for c in alpha:
                        if c != result[i - 1] and c != result[i + 1]:
                            result[i] = c
                            break 
            
        return ''.join(result)

 

자 언뜻보더라도 코드가 너무 길다.

 

첫번째 인덱스일 경우와 마지막 인덱스일 경우에 대해서 한칸 옆 인접한 인덱스를 체크하고 중복되지 않는 요소로 문자를 바꾸어준다. 이후 양옆이 존재하는 중간 인덱스라면 양옆 즉 오른쪽, 왼쪽의 요소들을 확인하면서 중복되지 않는 요소로 문자를 바꾸어준다. 

 

잠깐 봐도 조건이 너무 많이 나열되어있는데 이렇게 조건문을 써주면서도 너무 길게 써내려지는 걸 보고 분명 다른 접근법이 필요하겠다고 생각되었다. 

 

한참을 생각했는데 답이 나오질 않아서 다른 분의 풀이를 참고하게 되었다. 

 

그런데 상당히 기발한 풀이를 찾게 되어서 흥미롭다고 생각되었다. 

 

아래 그 풀이가 있다. 

'''
https://www.youtube.com/watch?v=SJBDLYqrIsM

개선된 솔루션: 
왼쪽, 오른쪽만 중복되는지 확인하면 된다면? a, b, c 이 세개의 알파벳으로 끝낼 수 있지 않을까? 
굳이 모든 알파벳을 다 돌면서 체크해야 하는가? 
이렇게 생각하면 좀더 깔끔하게 풀 수 있음. 

코멘트: 
아래 개선 솔루션은 답안지를 봐서 풀었는데 꽤나 기발하다... 문제에 대해 곰곰히 생각해보면 알 수 있는 접근법이랄까...
항상 보면 간단하면서도 빠르고 명쾌한 답안은 문제를 단순화시킨 방식임을 알 수 있다. 
'''

'''
Runtime: 71 ms, faster than 13.35% of Python3 online submissions for Replace All ?'s to Avoid Consecutive Repeating Characters.
Memory Usage: 13.9 MB, less than 77.28% of Python3 online submissions for Replace All ?'s to Avoid Consecutive Repeating Characters.
'''
class Solution:
    def modifyString(self, s: str) -> str:
        s_li = list(s)
        for i in range(len(s_li)):
            if s_li[i] == '?':
                for j in range(3):
                    if (i > 0 and s_li[i - 1] == chr(ord('a') + j)) or (i + 1 < len(s_li) and s_li[i + 1] == chr(ord('a') + j)):
                        continue
                    else:
                        s_li[i] = chr(ord('a') + j)
        
        return ''.join(s_li)

 

딱 봐도 상당히 간단하다. 

 

이 풀이를 보면 이제서야 내가 어떤 부분을 놓쳤는지 알 수 있다. 

 

일단 왼쪽과 오른쪽의 중복을 체크해야하는데 굳이 모든 알파벳 리스트를 돌면서 다 체크해야 하는가에 대한 의문이 들었다. 왼쪽, 오른쪽과 현재 포지션을 체크한다면 3개의 알파벳만 가지고 체크해도 되지 않을까? 예를 들면 a, b, c? 

그렇게 해서 문자 'a' 에 대해서 3 length의 range 를 돌면서 'a' + j 를 통해서 중복을 체크해주는게 낫지 않을까? 

 

이런 생각을 하지 못해서 첫번째 솔루션이 나왔다.  

 

그리고 그런 부분들을 적용했기 때문에 두번째 솔루션이 나오게 되었다. 

 

문자가 '?' 일 경우 딱 3번만 loop를 도는데 와중에도 0보다 크고 s_li의 length 보다 작은 범위내에 있는데 'a' + j 가 중복될 경우 그냥 continue 해버리는 것도 상당히 인상깊다.

 

두번째 풀이의 핵심은 else 구문이다. if 문은 그냥 filter 역할을 하는거고 결국에는 else 부에서 최종적으로 들어가야할 문자가 결정될 거다. 

---

자 근데 여기서 한가지 의문이 생긴다.

 

else 구문이 꼭 한번만 실행될까? 두세번 실행될 수도 있으려나?

 

한 요소에 대해서 계속 update 될 수 있을까? 그럴것같기도 한데 만약 그렇다면 한 요소에 대해서 여러번 update 를 한다면 이게 overhead일까? 아니면 3번의 범위 안에서 일어나는 아주 작은 동작이니 overhead라고 말할 수 없을까? 답은 직접 찍어보면 알겠죠. 

 

결론은 직접 해보면 안다. 

 

한번만 실행된다. (정확히 말하자면 한번만 실행되도 상관없다.)

 

어떻게 한번만 실행되는지 확실할 수 있을까? else 부에 print 문을 하나 박아서 출력문 개수를 하나씩 세서 비교해볼까? 아니면 더 쉬운 방법은 없을까? 있다. 한번만 실행되도 제대로 동작하는지를 보면 된다. 그럴려면 else 부에서 요소를 update 하자마자 break 하는 구문을 넣으면 된다.

else 부가 딱 한번만 실행되자마자 바로 밖으로 break 해버렸는데도 결과가 올바르게 나온다면 문제없다는 의미다. 

 

아래처럼 바꿔도 제대로 동작한다. 

else:
    s_li[i] = chr(ord('a') + j)
    break

---

 

항상 느끼는거지만 속도도 빠르고 간단하고 코드도 짧게 나오는 기발한 솔루션들을 거창한 아이디어에서 나오는게 아니다. 엄청 복잡하게 생각하거나 번뜩이는 아이디어를 떠올려야만 나오는 솔루션이 아니다.

 

대부분의 기발한 솔루션들은 오히려 문제를 아주 단순화시켰을때 나오게 된다. 

 

인상깊은 솔루션들을 볼때마다 이런 생각이 든다. (물론 나의 부족함도 여실히 느낀다.)

 

아침먹고나서 심심할때마다 오전 뇌마사지용으로 풀면서 EASY만 거의 280문제는 푼것같은데 이제 슬슬 MEDIUM 문제를 풀어볼까나. 근데 MEDIUM이 백준 골드 수준인것같은 느낌은 나만 느끼는건가.