또 30시간이 날아가 버렸다.
플레티넘 상위권은 확실히.. 어지간하면 재대로 손대기 쉽지가 않다..

일단 문제를 풀었지만 정신차려 보니 알고리즘 몇문제에 4일이 지나갔다.....
정신 차리고 프로젝트에 집중하도록 해야겠다.

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

부분 문자열 변환 성공

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 250 22 15 11.719%
문제
두 문자열 S와 T가 주어진다. T는 알파벳 소문자로만 이루어져 있고, S는 알파벳 소문자와 물음표로만 이루어져 있다.

S의 모든 물음표를 알파벳 소문자로 바꾸려고 한다. 이때, S의 부분 문자열로 등장하는 T의 개수를 최대로 만들어보자.

입력
첫째 줄에 S, 둘째 줄에 T가 주어진다. S와 T의 길이는 100,000보다 작거나 같고, 두 길이를 곱한 값은 10,000,000보다 작거나 같다.

출력
S의 물음표를 알파벳 소문자로 바꿨을 때, 부분 문자열로 등장할 수 있는 T의 개수의 최댓값을 출력한다.

문제가 짧다. 간단한 문제라고 생각했었는데
어떻게 풀까? 하고 고민하다보니 코딩 시작까지 10시간이 걸렸다.

브루트 포스로 풀려고 하면 정말 간단하게 물음표에 관한 경우의 수만 새어도 N!이다. N이 5000개만 되어도 현존 컴퓨터로는 연산이 불가능하다.
그래서 LCP , KMP , DP를 사용할 것이다!

과정을 설명하면 다음과 같다.
LCP로 2차원 배열을 만든다. 이때 가로는 l1_len, 세로는 l2_len으로 만들고, ?는 모든 문자열이 가능하도록 만든다.

첫번째 예제를 예시로 들어보자.

winlose???winl???w??
win

부연설명을 해보자면, l1과 l2 가 일치하는 좌표를 마킹한다.
그리고 ?는 모든 문자가 마킹 가능하도록 한다.

이 배열이 의미하는 것은, 첫째줄의 1에서 오른쪽 아래 3까지 이어져 있으면(대각으로 1,2,3이 있으면) 정답으로 가능한 배열이라는 것이다.(l2가 될 수 있다.)

이후 가능한 경우의 수를 1차원 list에 표시한 후,
KMP와 DP를 활용하여 정답을 찾는다.

• 이때 fail 함수를 이용하여 지금 위치에서 몇칸 떨어진 곳이 유효한 값인지 확인하고

• 그 유효한 값들이 무엇을 의미하는지를 생각하면 문제가 풀릴 것이다.

뭐이리 두리뭉실하게 설명하고 넘어가냐? 라고 할 수 있지만
이 문제는 이 개념을 정확하게 짚어야 완벽하게 이해했다고 할 수 있다.

설명이 간단해보이지만

• 특정 배열 중 어떤것이 T가 가능한지 판단하는 방법

• 그 방법의 결과를 가지고 문자열 S에 적용시킬 수 있는지

를 판단하는 과정을 생각해내는것이 장난아니게 어려웠다.
알고있으면 쉽지만 생각하는것이 힘든 문제라 생각한다.

컴프리헨션으로 오버헤드 최적화

list를 새로 만들고 연산할때 오버헤드가 많이 발생한다는걸 어렴풋이 알고 있었다.
하지만 실험해볼 경우가 없었는데, 마침 기회가 생겼다.

위 문제의 예제로 실험해보자.

• l1_len = 8.1만
• l2_len = 100

으로 실험해 보았다.

LCS = [[i + 1 if lst1[j] == lst2[i] or lst1[j] == '?' else 0 for j in range(l1_len)] for i in range(l2_len)]

LCS = []
for i in range(l2_len):
    row = []
    for j in range(l1_len):
        if lst1[j] == lst2[i] or lst1[j] == '?':
            row.append(i + 1)
        else:
            row.append(0)
    LCS.append(row)

컴프리헨션을 사용했을때 시간이 엄청 줄어드는걸 확인할 수 있었다.
새로운 list를 만들고, 그 list를 기존의 list에 합치는 과정은 비효율적이다.
그럼으로 다차원 list를 만들때는 컴프리헨션을 사용하도록 하자!

정신놓고 있다가 1주일가까이 날아갔다.
알고리즘을 푸는 과정이 정말 즐거웠고, 도저히 풀릴것같지 않은 문제들이 결국은 풀렸기에
그에 따른 성취감은 정말 만족스러웠다.

하지만 지금 내가 집중해야 할 것이 무엇인가에 대해 다시한번 생각하게 되었다.
지금 1순위는 개인프로젝트임이 틀림없다.
내일부터는 쉬운 문제 하나, 그리고 꾸준히 잡고 풀 플래티넘~ 문제 하나.
그리고 일정 시간이 지나면 모든걸 다 내려놓고 프로젝트에 몰입해야겠다.

이 점수오르는게 진짜 게임이랑 다를바가 없다.
곧있으면 드디어 승급이다..
플래4를 4월 25일에 달았으니 거의 2달반쯤 됐다.