[백준] Round words Python 3

문자열 LCS 문제를 비트마스크로 풀어보기

LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 문자열 문제에서 자주 등장하는 주제입니다. 두 문자열 간에 공통된 부분 수열 중 가장 긴 길이를 구하는 이 문제는 전통적으로 DP(Dynamic Programming)를 사용해 해결합니다. 그러나 오늘은 비트마스크를 활용하여 LCS 문제를 빠르고 효율적으로 푸는 방법과 이를 응용한 문제를 알아보겠습니다.

비트마스크를 이용한 LCS 계산

주어진 코드는 문자열 a와 b의 LCS 길이를 비트마스크로 계산하는 방식입니다. 비트마스크는 메모리를 효율적으로 사용하면서 대규모 연산을 빠르게 처리할 수 있는 강력한 도구입니다.

핵심 로직

1. b 문자열의 비트마스크 준비
   • b에서 각 알파벳의 등장 위치를 기록합니다. 예를 들어, b = "abcac"이라면, 각 알파벳에 대해 비트마스크로 위치를 표현합니다:
     • 'a': 10100 (1, 3번째 자리)
     • 'b': 01000 (2번째 자리)
     • 'c': 00011 (4, 5번째 자리)
2. a 문자열 순회
   • a의 각 문자를 순회하며 현재 비트마스크 상태(B)를 갱신합니다.
   • B는 비트마스크 연산을 통해 가능한 LCS의 상태를 유지합니다. 이때 B와 eng[ch]를 결합하고 적절히 비트를 이동(shift)하여 새로운 상태를 계산합니다.
3. LCS 길이 계산
   • 최종적으로, 비트마스크 B에서 켜져 있는 비트의 개수(bin(B).count('1'))를 반환하면 LCS의 길이가 됩니다.

b 문자열의 모든 회전 및 역회전을 고려한 LCS 계산

문제는 여기서 한 발 더 나아가 b 문자열의 모든 회전(rotation) 및 **역회전(reverse rotation)**에 대해, a와의 LCS 최댓값을 구하는 것입니다.

구현 방법

1. b + b
   • b를 두 번 이어붙여 b + b로 만듭니다. 이렇게 하면 b의 모든 회전을 슬라이싱으로 구할 수 있습니다.
   • 예: b = "abc"일 때, bb = "abcabc"에서 슬라이싱으로 "abc", "bca", "cab"를 추출 가능.
2. reverse(b) + reverse(b)
   • b를 뒤집은 문자열로 같은 과정을 반복합니다.
   • 예: b = "abc"라면, reverse(b) = "cba", rbb = "cbacba"에서 슬라이싱으로 "cba", "bac", "acb"를 추출.
3. LCS 계산
   • 위에서 추출한 모든 경우에 대해 LCS를 계산하고 최댓값을 갱신합니다.

코드 분석

def solve_round_lcs(a, b):
    n = len(b)
    ans = 0

    # (1) b의 모든 회전
    bb = b + b
    for i in range(n):
        sub = bb[i : i+n]
        ans = max(ans, lcs(a, sub))

    # (2) reverse(b)의 모든 회전
    rb = b[::-1]
    rbb = rb + rb
    for i in range(n):
        sub = rbb[i : i+n]
        ans = max(ans, lcs(a, sub))

    return ans

 

위 함수는 b의 모든 회전과 역회전을 순회하며 최댓값을 계산합니다.

이때 lcs(a, sub) 함수는 앞서 설명한 비트마스크 방식을 이용해 최적화된 속도로 동작합니다.

 

시간 복잡도

• solve_round_lcs는 b의 길이 n에 대해 O(n^2)의 시간 복잡도를 가집니다. 이는 각 회전당 O(n)의 lcs 계산이 이루어지기 때문입니다.
• 비트마스크를 이용함으로써 DP 방식(O(n^2))과 유사한 시간 복잡도를 유지하되, 메모리 사용량과 실제 실행 속도에서 효율적입니다.

전체 코드

import sys
input = sys.stdin.readline

def lcs(a, b):
    """
    비트마스크 한 개 (B)만 사용하여 
    문자열 a, b의 LCS 길이를 구한다.
    (길이 최대 2000)
    """
    eng = [0] * 26  # 각 알파벳별로 b에서 등장한 비트를 담을 공간
    B = 0           # LCS 상태를 저장할 비트마스크

    # 1) b의 각 위치에 맞춰 eng[ch] 세팅
    #    b[i] == ch면, eng[ch]에서 i번째 비트를 1로
    for i, ch in enumerate(b):
        eng[ord(ch) - ord('a')] |= (1 << i)

    # 2) a를 순회하며 비트마스크 갱신
    for ch in a:
        cidx = ord(ch) - ord('a')
        # x = B | eng[cidx]
        x = B | eng[cidx]
        # B <<= 1; B |= 1 대신
        # B를 (B << 1) + 1 로 바꿔서 x와 결합
        # 파이썬에서는 2000비트 이하여서 문제 없음
        Bshift = (B << 1) | 1

        # B = x ^ (x & (x - Bshift))
        #  (여러 풀이에서 보이는 공식)
        B = x ^ (x & (x - Bshift))

    # B의 비트가 몇 개 켜져 있는지가 LCS 길이
    return bin(B).count('1')

def solve_round_lcs(a, b):
    """
    a, b (길이 최대 2000) 에 대해, 
    b의 모든 회전/역회전 중 a와의 LCS 최댓값을 구한다.
    """
    n = len(b)
    ans = 0

    # (1) b+b
    bb = b + b
    for i in range(n):
        sub = bb[i : i+n]
        ans = max(ans, lcs(a, sub))

    # (2) reverse(b) + reverse(b)
    rb = b[::-1]
    rbb = rb + rb
    for i in range(n):
        sub = rbb[i : i+n]
        ans = max(ans, lcs(a, sub))

    return ans

def main():
    a = input().strip()
    b = input().strip()
    print(solve_round_lcs(a, b))

if __name__ == "__main__":
    main()