[99클럽 코테 스터디] 19일차 TIL - 문자열, Shuffle String

[19일차 미들러] 문자열

문제: https://leetcode.com/problems/minimum-suffix-flips/description/

* 대충 번역: 길이가 n인 이진수 문자열 target 이 주어진다. 길이가 n이고 전부 0으로 초기화된 또 다른 이진수 문자열 s도 있다. s를 target과 같게 만들고자 한다. 

한 연산에서, 인덱스 i를 골라 [i, n-1] 범위(i포함 ~ 끝까지) 내의 모든 비트들을 뒤집는다. 뒤집는 것은 0을 1로, 1을 0으로 바꾸는 것을 의미한다.

s를 target과 같게 만들기 위한 최소 연산 횟수를 반환하라.

Solution

앞 자리와 다를 경우에 연산이 수행된다. 결국 최소 횟수는 target 문자열이 앞자리와 다른 뒷자리를 몇 개 가지고 있는지를 계산하면 된다.

class Solution(object):
    def minFlips(self, target):
        """
        :type target: str
        :rtype: int
        """
        
        answer = 0
        flag = '0'

        for i in target:
            if i != flag:
                flag = i
                answer += 1 

        return answer

Another Solution

다른 제출자의 정답 중, 한 줄 코딩이 있었다. 활용한 개념은 문자열이 바뀌는 시점의 횟수를 세는 것으로 나와 같았다. 

from itertools import groupby

class Solution:
    def minFlips(self, target: str) -> int:
        return len(list(groupby("0" + target)))-1

groupby 메서드를 사용하여 문자열을 그룹화 하였다는 것이 특징이다. 이 메서드는 같은 정수나 키 값도 아닌 연속되는 동일한 값들을 그룹화하기 때문에 해당 문제에 사용하기 아주 적절하다.

 그러나 groupby는 데이터 분석에서 써 봤던 기억이 있는 함수로.. 코딩테스트에서, 특히 효율성 검사를 하는 경우에는 안 쓰는 것이 권장되는 듯 하다.

 

예를 들어, 결과를 ('key', 'group')인 리스트로 출력한다고 하면

• target이 "110"일 경우, groupby의 결과는 [('1', '11'), ('0', '0')]
• target이 "111001" 일 경우, grooypby의 결과는 [('1', '111'), ('0', '00'), ('1', '1')]
• target이 "010101"일 경우, groupby로  [('0', ['0']), ('1', ['1']), ('0', ['0']), ('1', ['1']), ('0', ['0']), ('1', ['1'])]

키 값은 그룹(연속된 동일한 값)을 대표하는 값으로, 그룹의 첫 번째 원소가 된다. 사전과 달리 키 값이 중복될 수 있다.

 

target의 첫 원소가 0이든 1이든 그룹화가 되어진다. 그러나 문제에서 문자열 s가 전부 0으로 초기화 되어 있기 때문에, 0으로 시작할 경우 뒤집을 필요가 없다. 이를 계산에 적용하기 위해서는 그룹의 갯수에서 1을 빼주어야 하는데,

target의 첫 원소가 1인 경우에는 바로 뒤집기를 해주어야 한다는 점에서 "0"을 맨 앞에 붙여 그룹화를 시행해주는 것이다.

나다어

나는 다음에 어떻게 풀까

• 예제는 이해 참고용, 문제 조건을 보고 해결책을 찾으면 수월하다.
• 문제 자체를 전부 구현해내기 보다 핵심을 파악하자 ~ !