[알고리즘] 백준_문자열 뽑기 Python (boj 8913)

문제

a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 연결해서 새 문자열을 만들 수 있다. 이러한 과정은 문자열이 빈 문자열이 되거나, 길이가 2 이상인 그룹이 없을 때 까지 계속한다.

예를 들어, s = babbbaaabb일 때, s에는 그룹이 다섯 개 있다. s는 다음과 같은 단계를 거쳐서 빈 문자열로 바꿀 수 있다. (밑 줄이 그어져 있는 그룹이 뽑히는 그룹)

babbbaaabb → baaaabb → bbb → 빈 문자열

하지만, 아래와 같은 단계를 거친다면, 빈 문자열로 바꿀 수 없다.

babbbaaabb → babbbaaa → baaaa → b

문자열이 주어졌을 때, 적절한 과정을 거쳐 빈 문자로 바꿀 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 a와 b로 이루어진 문자열로 이루어져 있다. 문자열의 길이는 1보다 크거나 같고, 25보다 작거나 같다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 문자열을 빈 문자열로 바꿀 수 있으면 1을, 없으면 0을 출력한다. 

 

 

https://www.acmicpc.net/problem/8913

 

1. DFS 브루스트포스

1. 문자열을 분리와 - 연결을 통해서 공통되는 문자열을 뽑아줍니다. (aabbaa -> (aa, bb, aa), abba -> (a, bb, a)

2-1 공통되는 문자열을 제거하고, 지워진 문자열에 대해서 DFS를 실행합니다. (visited를 통해 과거에 방문한 문자열일 경우에는 dfs를 실행하지 않습니다.)

2-2. 문자열 분리를 했을 때 문자열의 list의 갯수가 1개 이고, 그 1개의 문자열 Length가 1개 이상이라면 1을 return 하고 아닐경우에는 0을 리턴합니다. 

 

 

def sol2() :
    curInput = input().strip()
    def spiltInput(curInput: str)  :
        curStr = curInput[0]
        res = []
        for ele in curInput[1:] :
            if curStr[0] == ele :
                curStr += ele
            else :
                res.append(curStr)
                curStr = ele
        res.append(curStr)
        return res
    visited = collections.defaultdict(lambda: False)

    def dfs(strList: list) :
        strList = spiltInput("".join(strList))
        # 분리한 문자열의 갯수가 한개이면서, 그 한개의 문자열의 Length가 1 이상이라면 1을 리턴합니다.
        if len(strList) == 1 :
            return 0 if len(strList[0]) == 1 else 1
        # 아닐경우 분리한 문자열에서 특정 부분을 제거한 문자열을 dfs를 실행합니다. 
        for ind in range(len(strList)) :
            if len(strList[ind]) >= 2 :
                newList = strList[:]
                newList.pop(ind)
                if visited[tuple(newList)] == False :
                    visited[tuple(newList)] = True
                    curRes = dfs(newList)
                    if curRes == 1 :
                        return 1
        return 0
    return dfs([curInput])

 

2. BFS 부르스트포스

1. 일단 q에 비교할 문자열을 넣어놓습니다.

2. 문자열을 넣어놓은 이후에, 겹치는 문자열에 관한 index를 구합니다(문자열에 겹치는 단어에 따라 startIndex, endIndex가 존재할 것이며 이는 여러개 존재하므로 배열이 될 것입니다.).

3. 그리고 겹치는 [(startIndex, endIndex)]에 대한 배열을 순회하면서 startIndex와 endIndex에 해당하는 문자열을 빈 문자열로 초기화 해주고 이를 str로 초기화 해줍니다. visited를 확인하고 초기화 된 값을(str) 값을 다시 q에 넣습니다. 

4. 1-3을 반복합니다. 

 

def sol() :
    curInput = input().strip()
    q = collections.deque()
    q.append(curInput)
    
    flag = False
    visited = collections.defaultdict(lambda: False)
    while not flag and q :
        curInput = q.popleft()
        temp = list(map(str, curInput[:]))
        tempInd = 1
        curList = []
        while tempInd < len(temp) :
            prev = temp[tempInd - 1]
            cur = temp[tempInd]
	        # Ind를 비교하면서 겹치는 부분의 startInd, endInd를 확인합니다.
            if prev == cur :
                prevStartInd = tempInd - 1
                while tempInd < len(temp) and prev == temp[tempInd] :
                    tempInd += 1
                # CurList에 startInd, endInd를 기록해 줍니다. 
                curList.append((prevStartInd, tempInd - 1))
            else :
            	# 만약 과거 앖과 현재 값이 같지 않다면 tempInd에 값을 더해줍니다.
                tempInd += 1
        for startInd, endInd in curList :
            nextCur = list(map(str, curInput[:]))
            # startInd, endInd까지 값을 ""로 만들어 줍니다. 
            for ind in range(startInd, endInd + 1) :
                nextCur[ind] = ""
            nextCur = "".join(nextCur)
            if nextCur == "" :
                flag = True
                break
            # visited를 확인하고, visited가 False일 경우에만 Q에 값을 추가해 줍니다. 
            if not visited[nextCur] :
                visited[nextCur] = True
                q.append(nextCur)
    return 1 if flag else 0