[CF 1215C] Swap Letters - 1500 문제 설명 : a와 b로만 이루어진 길이가 같은 두 문자열이 주어진다. 이 문자열에서 한 가지 연산을 할 수 있는데, 첫 번째 문자열에서 한 인덱스와 두 번째 문자열에서 한 인덱스를 골라서 서로 swap을 할 수가 있다. 이 연산을 최소한으로 사용하여 두 문자열을 같도록 만들어야 한다. 풀이 : 두 문자열이 다를 수 있는 경우는 첫번째 문자열이 'a', 두번째 문자열이 'b'이거나 그 반대의 경우밖에 없다. 따라서 그 두가지 경우에 대해서 따로 저장을 해 놓는다. 문자열이 다르다는 것은 현재 문자와 다른 문자를 서로 swap해야 하므로 한번 swap을 했을 때, 총 다른 횟수는 2가 줄어들 것이다. 따라서 ab의 개수+ba의 개수가 짝수가 아니면 불..
[CF 828C] String Reconstruction - 1700 문제 설명 : n개의 부분문자열(substring)과 이 부분문자열이 전체 문자열에서 등장하는 시작 위치가 주어진다. 이 부분문자열의 정보를 바탕으로 전체 문자열을 구성할 때, 사전순으로 가장 앞서도록 만드는 문제이다. (입력되는 정보는 모순되지 않는다) 풀이 : 입력되는 정보는 모순되지 않으므로 단순하게 substring을 i번째 위치에 넣는다고 생각하면 된다. 하지만 naive하게 생각해서 k_i개의 위치에 대해서 substring의 모든 글자를 다 비교해보면 시간초과가 난다. 예를 들어 substring이 "aaa...aa"로 총 100만 글자이고, k_i=100만개 : {1,2,3,...100만}이라면 시간복잡도는 100만 * ..
[Codeforces 1025C] Plasticine zebra - 1600 문제 설명 : 문자열에서 특정 연산이 하나 정의된다. 그 연산은 문자열 내에서 특정 인덱스 사이를 기준으로 양 옆의 문자열을 reverse하는 연산이다. 이 연산을 0번 이상 사용하여 나온 문자열에서 b,w가 교대로 최대 몇 번 등장할 수 있는지를 구하는 문제이다. 풀이 : 결과적으로 '특정 연산'을 사용하게 되면 그 결과는 원본 문자열에서 몇 번 만큼 shift한 결과와 동일하다. 아직까지는 왜 이것이 가능한지는 밝히지 못했다. 따라서 나는 원본 문자열을 특정 횟수만큼 shift했을 때 최대 몇 번 b,w가 교대로 등장하는지만 세주면 된다. 이에 대한 구현은 원본 문자열 뒤에 똑같이 문자열을 붙여면 O(N)만에 수행할 수 있다..
[Codeforces 1070H] BerOS File Suggestion - 1600 문제 설명 : 처음에 n개의 파일이름(문자열)이 주어진다. 그 다음 q개의 쿼리가 들어오는데, 각 쿼리는 substring을 제시하여 n개의 파일 중에서 해당 substring 포함하는 파일은 총 몇 개인지와 존재한다면 아무 파일이름을 출력하면 된다. 풀이 : 정말 고민을 많이 했던 문제이다. 일단 n이 1만, q가 5만이기 때문에 각 쿼리마다 모든 n을 살펴보는 것은 시간이 초과된다( O(n*q) ). 따라서 반드시 전처리과정을 거친 뒤에야 쿼리를 받을 때 빠르게 답을 출력하는 형태가 될 것이라고 짐작했다. 실제로 솔루션은 한 문자열에서 나올 수 있는 모든 substring의 경우의 수를 map에다 저장해서 카운트 해..
[Codeforces 1138D] Camp Schedule Problem - D - Codeforces codeforces.com 문제 설명 : 0과 1로만 구성된 문자열 s와 t가 주어진다. 목표는 문자열 s에 등장하는 0과 1의 빈도수와 동일하게 문자열을 변형시키는 것인데 그 문자열의 substring으로 문자열t가 최대한 많이 등장하도록 변형시켜야 한다. 풀이 : 조건에서 문자열 t를 최대한 많이 등장하도록 해야 한다. 여기서 substring은 겹치는 것이 가능하다. 예를 들어서 문자열 "aaa"가 있고 패턴이 "aa"라면 총 2개의 substring이 존재하는 것이다. 따라서 나는 우선 문자열 t에서 최장 길이의 공통 prefix와 suffix를 찾아야 한다. 공통부분을 찾으면 현재의 suffi..
1787-문자열의 주기 예측 KMP알고리즘의 실패함수를 활용하는 문제이다. 다만 실패함수를 그대로 사용하는게 아니라 약간의 변형이 필요한데, 이를 위해선 실패함수의 의미에 대해서 정확히 파악해야만 한다.예를 들어 "bbabbab"라는 문자열이 있다고 하자. 이를 실패함수로 표현해보면, 0 1 2 3 4 5 6 b b a b b a b 0 1 0 1 2 3 4 가 된다. 여기서 실패함수의 값이 의미하는 바를 한번 생각해보자. 예를 들어 3번째 인덱스('b')가 의미하는 '1'은 무슨 의미일까? 해당 인덱스에서 txt와 비교를 했는데 만약 일치하지 않았다면 다음으로 비교할 지점은 ptn의 '1'번째 부터 보면 된다는 의미이다. 이것이 실패함수의 표면적인 정의이다. 하지만 이것 말고도 숨겨진 의미가 있다. 그..
4354-문자열 제곱 정말 오랫동안 고민하다가 생각이 안 나서 결국 풀이를 흘깃 쳐다본 문제이다. 정답은 허탈하리만큼 간단했다. 그냥 실패함수를 구한 다음에, 특정한 공식에 대입만 하면 그게 답이다. 그 공식이라는 것도 복잡하지 않다. 이렇게 생겼다. len은 문자열의 길이이고 fail[len-1]은 마지막 글자의 실패함수 값이다. 위의 분수 값이 정수여야만(분자가 분모로 나누어 떨어져야만) 정답으로 유효하고, 그렇지 않다면 답은 1이다. 다만 아직은 직감적으로 와닿지는 않는다. 이런 문제일수록 처음에 풀었을 때 이해를 제대로 하고 넘어가야지 다음에 비슷한 유형의 문제를 만났을 때 풀 수 있다. 현재까지 분석한 지점은 은 ptn의 길이를 의미한다(답으로서 유효한 경우에만). 이 문제는 ptn이 총 몇 번..