[백준 21762] 2021 정올 공통 부분 수열 확장

문제 출처 : https://www.acmicpc.net/problem/21762

21762번: 공통 부분 수열 확장

이 문제는 2021년 정보올림피아드 1차 고등부 문제 입니다.

 

두 개의 수열 X, Y의 부분수열 W를 확장 가능한지, 불가능한지 확인 하는 프로그램을 작성하는 것입니다. 예제 입력에 있는 X, Y, W를 살펴 보겠습니다.

X = ababca

Y = cbabba

W = baa

X, Y에 W는 공통부분수열이기 때문에 무조건 존재합니다. 이 부분수열이 확장 가능한지 확인을 해야 합니다. 잘 보면 X와 Y의 4번째 자리에 있는 b가 확장이 가능합니다.

X = ababca

Y = cbabba

W = baba

위와 같이 확장이 가능하면 1을, 불가능하면 0을 출력하는 문제입니다. 지금은 X, Y에 W가 하나밖에 없지만 W가 여러개 존재할 수도 있고, 얼마든지 복잡해 질 수 있습니다. 그래서 먼저 서브테스크를 하나하나 해결해 나가면서 문제를 풀어보도록 하겠습니다.

서브테스크1

서브테스크1은 W의 길이가 1 입니다. 따라서 W의 앞과 뒤쪽에 공통되는 문자가 있는지만 확인하면 됩니다.

X = abcde

Y = acf

W = c

W가 c라면 앞과 뒤쪽을 a부터 z까지 확인하면서 공통된 문자가 있으면 1을 출력하고, 그렇지 않으면 0을 출력하면 됩니다. 이렇게 보면 어렵지 않지만 W가 여러개일 경우 문제가 생깁니다.

X = abcdc

Y = dc

W = c

X에서 W를 확인해보면 3번째 자리에 c가 있습니다. c의 앞에만 비교한다면 확장이 불가능해 보이지만 X에는 c가 뒤쪽에도 있습니다. 공통 부분 수열 c는 dc로 확장 가능하기 때문에 1을 출력하는 것이 맞습니다. 즉 우리는 W가 여러개 있을 것을 예상하고 앞, 뒤로 W가 있는지 확인해야 합니다.

X = ****W***W***

Y = W***W***W

이해하기 쉽게 위와 같이 표현하였습니다. *는 어떤 문자인지 모르는 문자입니다. W는 공통부분수열 입니다. 이와 같이 X, Y가 있을 때 앞에 공통 부분수열이 있는지 확인할 때에는 마지막 노란색의 W를 기준으로 합니다.

X = ****W***W**

Y = W***W***W

앞 부분의 빨간색으로 표현된 모든 문자를 확인해야 합니다. 반대로 뒤쪽에 확장 가능한지 확인할 때에는 맨 앞에 있는 W 기준으로 확인해야 합니다. 앞의 노란색 W를 기준으로 뒤에 있는 모든 문자를 확인 합니다.

X = ****W***W***

Y = W***W***W

이렇게 맨 앞의 W 기준으로 뒤쪽의 문자를 확인해야만 확장 가능한지 알 수 있습니다. 여기서는 여러개의 W가 있기 때문에 *의 문자가 무엇인지 상관 없이 확장 가능합니다.

우리가 해야할 일은 X, Y의 첫 번째와 마지막 W의 위치를 알아내어 앞쪽과 뒤쪽의 문자들을 a부터 z까지 확장 가능한지 확인하면 됩니다. 그럼 문제를 풀어보도록 하겠습니다.

입력 받기

def solve():
    X = '0' + input()
    Y = '0' + input()
    W = '0' + input()

    lenX, lenY, lenW = map(len, (X, Y, W))

T = int(input())

for _ in range(T):
    solve()

여러 케이스를 해결해야 하기 때문에 T를 입력 받고, T번 만큼 반복합니다. 그리고 solve라는 함수를 통해 문제를 해결합니다.

solve 함수에서는 각각 X, Y, W를 입력 받습니다. 이 때 맨 앞에 ‘0’을 추가하여 줍니다. 이유는 자릿수 계산할 때 헷갈리지 않기 위해서 입니다. 그냥 입력 받으면 첫 번째 자리의 인덱스는 0번 입니다. 이것을 매번 계산하기 힘들기 때문에 앞에 한자리를 추가하여 첫 번째 자리의 인덱스를 1번으로 만들어 준 것입니다.

W는 어짜피 자릿수가 1이지만 우리는 서브테스크1만 해결하고 끝낼것이 아니기 때문에 자릿수를 계산해 준 것입니다. 서브테스크1만 해결하려면 W길이를 굳이 구하지 않아도 됩니다. 그리고 X, Y, W의 길이를 구합니다. map을 통해 세 개의 길이를 구해 주었습니다.

W 위치 찾기

다음으로 W가 X, Y에서 어디에 있는지 첫 번째 위치와 마지막 위치를 찾아 줍니다. 아래 내용은 solve 함수에 이어져서 작성하면 됩니다.

def solve():
    # 앞의 내용은 같습니다.
		
    sx, sy, ex, ey = -1, -1, -1, -1
    for i in range(1, lenX):
        if X[i] == W[1]:
            if sx == -1:
                sx = i
            ex = i

    for i in range(1, lenY):        
        if Y[i] == W[1]:
            if sy == -1:
                sy = i
            ey = i

X와 Y의 값들을 하나하나 확인해서 W값과 같을 경우 위치를 저장합니다. sx, sy의 경우는 시작 위치를 찾는 것으로 초기값인 -1일때만 업데이트 합니다. ex, ey는 마지막 위치를 찾는 것으로 W와 같을 경우 계속 업데이트를 해주면 마지막 위치의 값이 최종적으로 기록될 것입니다.

W 앞부분 확인하기

def solve():
    # 앞의 내용은 같습니다.

    atoz = map(chr, range(ord('a'), ord('z') + 1))
    for c in atoz:
        check = 0
        for x in X[:ex]:
            if c == x:
                check += 1
                break
        
        for y in Y[:ey]:
            if c == y:
                check += 1
                break

        if check == 2:
            print(1)
            return                

a부터 z까지 c라는 변수로 반복을 합니다. X와 Y의 앞 뒤를 확인합니다. 처음부터 마지막 W가 있는 위치인 ex, ey의 앞까지 확인해서 같은 문자가 있는지 체크합니다. 체크한 값이 있다면 check에 1을 더해줍니다. 그리고 더 이상의 반복을 중지하고 다음으로 넘어갑니다. check값이 2라면 X, Y 에 둘 다 해당 문자가 있는 것입니다. 그럼 확장이 가능한 것이기 때문에 1을 출력하고 종료합니다.

W 뒷 부분 확인하기

def solve():
    # 앞의 내용은 같습니다.

    check = 0
    for x in X[sx + 1:]:
        if c == x:
            check += 1
            break

    for y in Y[sy + 1:]:
        if c == y:
            check += 1
            break

    if check == 2:
        print(1)
        return
        
    print(0)    
    return

뒷 부분 확인은 앞부분 확인한 코드 밑에 이어서 작성합니다. 첫 번째로 찾은 W의 위치인 sx, sy로 탐색을 시작합니다. sx, sy는 탐색 범위가 아니기 때문에 sx + 1, sy + 1을 시작 위치로 하였습니다. 그리고 로직은 앞 부분 확인한 것과 같습니다. check 값이 2가 된다면 둘 다 있기 때문에 1을 출력하고 끝내는 것입니다. 하지만 W값이 존재하지 않는다면 atoz를 체크하는 for문을 빠져나오게 될 것 입니다. 이 때는 확장이 불가능 한 것이기 때문에 0을 출력하고 끝내줍니다.

서브테스크2

서브테스크2는 W의 범위가 존재하지 않습니다. W의 길이가 길어진 것입니다.

W = abc

W가 위와 같다면 확장 가능한 부분은 총 4군데 입니다.

?가 들어간 위치에 확장이 가능한지 확인해야 합니다. W가 길어질 수록 체크할 부분이 많아지고 반복의 횟수가 늘어나게 됩니다. 또한 a, b, c가 중복될 경우가 있기 때문에 첫 번째와 마지막 위치를 파악할 때 조심해야 합니다. 가령 X가 아래와 같이 주어졌습니다.

X = ****c****a****b****b****c

이 때 c의 첫 번째 c의 위치는 맨 앞에 있는 c의 위치가 아닙니다. abc 형태로 W가 주어져 있기 때문에 c의 위치는 a, b가 출현한 다음에 있는 c가 첫 번째 위치가 됩니다.

Y = ****a****b****a****c****b****c

위의 Y와 같이 a, b, c가 중복되어 나타나는 경우도 있습니다. 이 때도 어디가 첫 번째인지, 어디가 마지막인지 위치 파악을 잘 해야합니다. 입력부분은 서브테스크1과 똑같기 때문에 입력 부분은 넘어가고, 첫 번째와 마지막 위치를 잡는 부분을 작성해 보겠습니다.

def solve():
    X = '0' + input()
    Y = '0' + input()
    W = '0' + input()

    lenX, lenY, lenW = map(len, (X, Y, W))

    rngX = [[-1, lenX] for _ in range(lenW)]
    rngY = [[-1, lenY] for _ in range(lenW)]
    
    k = 1
    for i in range(1, lenX):
        if k < lenW and X[i] == W[k]:
            rngX[k][0] = i
            k += 1

    k = lenW - 1
    for i in range(lenX - 1, 0, -1):
        if 0 <= k and X[i] == W[k]:
            k -= 1
            rngX[k][1] = i
            
    k = 1
    for i in range(1, lenY):        
        if k < lenW and Y[i] == W[k]:
            rngY[k][0] = i
            k += 1
    
    k = lenW - 1
    for i in range(lenY - 1, 0, -1):
        if 0 <= k and Y[i] == W[k]:
            k -= 1
            rngY[k][1] = i

sx, sy, ex, ey가 아닌 rngX, rngY로 변경하였습니다. 이제 단일값이 아닌 범위를 나타내야 하기 때문에 이렇게 변경한 것입니다. 초기값은 -1, lenX로 하였습니다. 우리가 구해주는 W의 위치값은 범위에 포함되지 않습니다. 따라서 범위의 시작 값 + 1을 해주어야 합니다. 이 때 시작값이 -1로 되어 있어야 1을 더해 0이 되어야 0번째 인덱스부터 파악이 가능합니다.

서브테스크1에서는 첫 번째 위치와 마지막 위치를 하나의 for문에서 해결하였지만 여기서는 첫 번째 값과 마지막 값을 따로 찾아줍니다. 위에서 언급했던 것처럼 서브테스크1의 W처럼 하나만 있는 것이 아니기 때문에 각 문자들의 관계를 따져봐야 합니다. 이것을 매번 체크하는 것이 힘들기 때문에 첫 번째 위치를 구했던 것처럼 끝에서부터 계산해서 입력합니다. 뒤에서부터 첫 번째 W의 값을 구하면 이것이 앞에서 보았을 때는 마지막 값을 구하는 것이 되는 것입니다.

이해하기 어려울 수 있으니 예를 만들어 확인해 보면서 값이 잘 들어가 있는지 확인해 보겠습니다.

X = ababcaac

W = baa

X와 W의 값이 이와 같을 때 rngX의 값을 구해보면 다음과 같이 나옵니다.

[[-1, 4], [2, 6], [3, 7], [6, 9]]

W의 baa값이 여러개 들어가 있습니다. 정확하게 확인해보면 아래와 같이 3개의 baa가 들어가 있습니다.

X = ababcaac

X = ababcaac

X = ababcaac

W의 첫 번째인 b는 b가 될 수 있는 마지막 위치를 가져야 합니다. 따라서 범위가 처음부터 4번째 자리인 -1, 4가 되었습니다.

X = ababcaac

W 두 번째 자리인 a는 첫 번째 b의 위치부터 두 번째 a가 될 수 있는 마지막 a까지를 구해야 합니다.

X = ababcaac

위와 같은 범위인 2, 6 사이가 범위가 됩니다. W 세 번째 자리 a역시 위에서 구한 첫 번째 bba의 두 번째 a부터 마지막 bba의 마지막 a가 범위가 됩니다.

X = ababcaac

따라서 이 값은 3, 7이 됩니다. 그리고 마지막 범위는 첫 번째 bba의 마지막 a부터 끝까지 됩니다.

X = ababcaac

이 값이 6, 9가 됩니다. X의 길이가 8인데 9가 된 이유는 리스트의 범위 슬라이싱은 마지막을 포함하지 않습니다. 그렇기에 마지막 값이 9가 되어야 8까지 확인하게 되는 것입니다.

W 범위 확인하기

def solve():
    # 앞 부분은 같습니다.

    atoz = map(chr, range(ord('a'), ord('z') + 1))
    for c in atoz:
        for i in range(lenW):
            sx, ex = rngX[i]
            sy, ey = rngY[i]
            
            check = 0
            for x in X[sx + 1:ex]:
                if c == x:
                    check += 1
                    break
            
            for y in Y[sy + 1:ey]:
                if c == y:
                    check += 1
                    break

            if check == 2:
                print(1)
                return           
            
    print(0)    
    return

범위 확인 하는 코드는 다음과 같습니다. 시작과 끝 부분을 확인했던 것과는 달리 범위로 바뀌었습니다. 시작값인 s와 끝 값인 e를 찾습니다. s는 포함되지 않기 때문에 범위를 구할 때 + 1을 해주었습니다. e역시 범위에 포함되지 않지만 슬라이싱 자체에서 마지막 값은 포함이 안되기 때문에 그대로 써줍니다.

범위 안에 a부터 z까지의 값들을 계산해서 check 값이 2가 되면 1을 출력해 줍니다. 끝까지 아무것도 없다면 0을 출력하고 프로그램을 종료합니다.

이렇게 하면 서브테스크2까지 해결할 수 있습니다. 아직 최적화가 안되어 있기 때문에 좀 더 최적화 할 수 있는 방법을 찾아야 합니다.

서브테스크3

다음으로 생각해볼 문제는 a부터 z까지 존재하는지 매번 찾는 부분입니다. 이것을 a부터 z까지 찾는 것이 아니라 X, Y에 포함된 문자만 반복한다면 속도를 조금이라도 올릴 수 있을것 같습니다. 따라서 atoz를 구하는 부분을 바꿔보겠습니다.

atoz = map(chr, range(ord('a'), ord('z') + 1))

기존에 atoz를 구하는 것은 위와 같았습니다. a부터 z를 모두 확인하기 위해 구한 것입니다. 이것을 다음과 같이 바꿔줍니다.

    atoz = X[1:] + Y[1:] 
    atoz = set(atoz)

X와 Y에 있는 문자만으로 만들기 위해서 두 리스트를 더해줍니다. 앞에 추가했었던 0값을 없애기 위해서 1번 인덱스부터 더해줍니다. 더해준 atoz에는 중복된 값이 많이 있기 때문에 중복을 없애주기 위해서 set으로 변환 합니다. set으로 바꿔주면 중복된 값이 모두 사라집니다. 이렇게 바꿔주는 것만으로도 서브테스크3을 해결할 수 있습니다.

서브테스크4

서브테스크4에서는 모든 제약 조건이 없습니다. 따라서 좀 더 빠른 알고리즘을 생각해내야 합니다. 우리가 찾아야 할 것은 각 범위 안에 문자가 있는지 없는지 입니다. 이럴 때 가장 사용하기 좋은 알고리즘이 누적합입니다. 각 문자들의 누적합을 구해서 X, Y의 각 범위 안에 같은 문자가 존재하면 1, 범위 안에 같은 문자가 존재하지 않으면 0을 출력합니다.

누적합 만들기

그럼 누적합을 만드는 방법에 대해 알아보겠습니다.

X = ababca

X가 위와 같이 있을 때 누적합은 다음과 같습니다.

a의 갯수를 확인하면 첫 번째 인덱스는 1개 입니다. 그리고 3번째 인덱스가 되었을 때 누적으로 2가 됩니다. 마지막으로 6번째가 되었을 때 누적 3이 됩니다. 이런 방식으로 각 문자에 대한 누적합을 만들어 줍니다.

def solve():
    # 앞 부분은 같습니다.

    cntX = [[0] * lenX for _ in range(26)]
    cntY = [[0] * lenY for _ in range(26)]

    k = 1
    ascii_a = ord('a')
    for i in range(1, lenX):
        for j in range(26):
            cntX[j][i] = cntX[j][i - 1]
        idx = ord(X[i]) - ascii_a
        cntX[idx][i] += 1

        if k < lenW and X[i] == W[k]:
            rngX[k][0] = i
            k += 1

    k = 1
    for i in range(1, lenY):
        for j in range(26):
            cntY[j][i] = cntY[j][i - 1]
        idx = ord(Y[i]) - ascii_a
        cntY[idx][i] += 1

        if k < lenW and Y[i] == W[k]:
            rngY[k][0] = i
            k += 1

    # 뒷 부분은 같습니다.

누적합을 구할 cntX, cntY 리스트를 만들어 줍니다. 누적합을 만드는 방법은 리스트를 만들면서 이전 값을 계속 누적해서 더해주는 것입니다.

    for i in range(1, lenX):		
        for j in range(26):
            cntX[j][i] = cntX[j][i - 1]

i값은 1부터 시작합니다. 따라서 i - 1값의 최소값은 0이 되어 i값이 음수가 나오는 경우는 고려하지 않아도 됩니다. 앞의 값을 계속 복사하기 때문에 누적이 됩니다.

다음으로 현재 위치에 있는 문자를 찾습니다. ord를 통해 해당 문자의 아스키코드값을 얻습니다. a의 아스키코드값은 97 입니다. b는 98, c는 99가 되고 마지막 z값은 122가 됩니다. 하지만 cntX의 범위를 0부터 25까지로 했기 때문에 여기에 맞게 변경시켜야 합니다. 결과로 얻는 값에다가 97을 빼는 것입니다. 그럼 원래 a값인 97에서 97을 빼면 0이 됩니다. 마지막 z는 122에서 97를 빼기 때문에 25가 됩니다.

하지만 우리가 a의 아스키코드값을 매번 외우고 있는 것은 아닙니다. 그리고 지금은 소문자이기 때문에 97이지만 대문자 A일 경우는 65가 됩니다. 이 두 값이 헷갈릴수 있기 때문에 아스키코드값을 외어서 사용하는 것은 좋은 방법이 아닙니다. 그래서 ord(’a’)값을 빼주는 것으로 대신 하였습니다. ord(’a’)값은 ascii_a로 미리 구해놓고 ord(X[i])에서 빼주는 이유가 바로 이 범위를 만들어 주기 위해서 입니다.

범위안에 값이 있는지 확인하기

서브테스크3에서 찾아야할 범위를 구했고, 방금 누적합을 구해주었습니다. 이제 이 범위로 문자가 있는지 계산하면 문자가 있는지 없는지 알 수 있습니다.

X = ababca

X가 위와 같을 때 처음부터 3번 인덱스 사이에 b가 있는지 확인 할 때 cntX[2][3 - 1] - cntX[2][0]을 계산해서 1 이상이 나오면 그 사이에 b가 있다는 뜻입니다. 이런식으로 범위안에 어떤 문자가 있는지 없는지 알 수 있습니다.

    for c in atoz:
        idx = ord(c) - ascii_a
        for i in range(lenW):
            sx, ex = rngX[i]
            sy, ey = rngY[i]

            calx = cntX[idx][ex - 1] - cntX[idx][sx]
            caly = cntY[idx][ey - 1] - cntY[idx][sy]

            if calx and caly:
                print(1)
                return

먼저 문자 c의 인덱스를 구합니다. 그리고 해당 인덱스를 가지고 범위안에 x, y의 값이 있는지 확인 합니다. x, y를 계산한 calx, caly가 둘 다 있으면 1을 출력하면 됩니다.

전체코드

전체 코드를 확인해 보겠습니다.

def solve():
    X = '0' + input()
    Y = '0' + input()
    W = '0' + input()

    lenX, lenY, lenW = map(len, (X, Y, W))

    rngX = [[0, lenX] for _ in range(lenW)]
    rngY = [[0, lenY] for _ in range(lenW)]

    cntX = [[0] * lenX for _ in range(26)]
    cntY = [[0] * lenY for _ in range(26)]

    k = 1
    ascii_a = ord('a')
    for i in range(1, lenX):
        for j in range(26):
            cntX[j][i] = cntX[j][i - 1]
        idx = ord(X[i]) - ascii_a
        cntX[idx][i] += 1

        if k < lenW and X[i] == W[k]:
            rngX[k][0] = i
            k += 1

    k = lenW - 1
    for i in range(lenX - 1, 0, -1):
        if 0 <= k and X[i] == W[k]:
            k -= 1
            rngX[k][1] = i

    k = 1
    for i in range(1, lenY):
        for j in range(26):
            cntY[j][i] = cntY[j][i - 1]
        idx = ord(Y[i]) - ascii_a
        cntY[idx][i] += 1
        if k < lenW and Y[i] == W[k]:
            rngY[k][0] = i
            k += 1
    
    k = lenW - 1
    for i in range(lenY - 1, 0, -1):
        if 0 <= k and Y[i] == W[k]:
            k -= 1
            rngY[k][1] = i

    atoz = X[1:] + Y [1:]
    atoz = set(atoz)

    for c in atoz:
        idx = ord(c) - ascii_a
        for i in range(lenW):
            sx, ex = rngX[i]
            sy, ey = rngY[i]

            calx = cntX[idx][ex - 1] - cntX[idx][sx]
            caly = cntY[idx][ey - 1] - cntY[idx][sy]

            if calx and caly:
                print(1)
                return           
            
    print(0)    
    return 

T = int(input())

for _ in range(T):
    solve()