청정알고리즘

문제

Given a 32-bit signed integer, reverse digits of an integer.

풀이

$ans$ 변수를 관리 하면서

ans = 10*ans + x%10;
x /=10;

를 반복하면 된다.

주의해야할 점은, boundary condition을 처리하는 것이다.

첫 줄을 계산할 때 INT_MAX를 넘거나 INT_MIN보다 작아지면 바로 return 해준다.

Time Complexity : $O(log n)$

코드

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while(x)
        {
            int num = x%10;
            x/=10;
            if(ans > INT_MAX/10 ||( ans == INT_MAX/10 && num>7))return 0;
            if(ans < INT_MIN/10 || (ans == INT_MIN/10 && num<-8))return 0;
            ans = ans*10+num;
        }
        return ans;
    }
};

문제

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P      A       H      N

  A  P   L  S   I   I   G

    Y        I        R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

풀이

$jmp=2\times \text{numRows}-2$의 주기로 반복되는 규칙이 생긴다는 것을 캐치하자.

그러면 줄별로 주기가 $jmp$가 되고, 규칙에 맞게 순서대로 출력을 하면 끝난다.

첫줄과 마지막 줄은 $jmp$마다 1개씩, 나머지 줄은 2개씩 포함된다는 것을 캐치한다면 나머지는 구현.

Time Complexity : $O(n)$  

코드

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        
        string ret;
        int l=s.size(), jmp = 2*numRows-2;
        
        for(int i=0;i<numRows;i++)
        {
            for(int j=0;j+i<l; j+=jmp)
            {
                ret += s[j+i];
                if(i!=0 && i!= numRows-1 && j+jmp-i<l) ret+=s[j+jmp-i];
            }
        }
        return ret;
    }
};

개요

Manacher's Algorithm은 주어진 배열에서 배열의 각 entry를 중심으로 하는 가장 큰 회문(palindrome)의 크기를 구하는 알고리즘이다.

Brute Force Approach

이를 단순히 Brute Force로 접근해보자.

총 substring의 개수가 $O(n^2)$이며, 각 substring이 회문인지 아닌지 판별하는데 $O(n)$이 걸린다.

따라서 총 시간복잡도 = $O(n^2) \times O(n) = O(n^3)$ 이다.

중복 제거

$s=\text{bananax}$가 회문인지 아닌지 판단한다고 하자.

우리는 $\text{bananax}$가 회문이 아니라는 걸 알기 위해 다음과 같은 과정을 거친다.

$s[2] = s[4]$   ->   $s[1] = s[5]$   ->   $s[0] \neq s[6]$

우리가 각각의 substring을 모두 회문이 아닌지 체크만 한다면, $\text{bananax}$가 회문이 아니라는 정보만 이용하고, 계산과정에 있었던 $s[2]=s[4], s[1]=s[5], s[0] \neq s[6]$과 같은 정보들을 버리게 되는 것이다. 따라서 이러한 정보를 이용하여 중복 계산을 줄인다면 시간복잡도의 개선을 노릴 수 있을 것이다.

조금 생각을 해본다면 각 entry를 중심으로 하는 가장 큰 회문의 크기를 $O(n)$만에 구할 수 있다는 것을 알 수 있다.

$\text{abanana}$를 예시로 들면 

따라서 각각의 중심을 기준으로 길이를 0부터 하나씩 늘려가면, $O(n)$만에 특정 index를 중심으로 하는 가장 큰 회문을 구할 수 있다.

총 $O(n)$의 index가 있고, 각 index에 대해서 가장 큰 회문을 찾는데 $O(n)$의 시간이 걸린다.

따라서 이 방법의 시간복잡도는 $O(n) \times O(n) = O(n^2)$이다.

아직도 덜 쓴 정보가 있다?

이 정도면 충분히 버려지는 정보없이 잘 만들었다고 보일 수 있다.

$O(n^2)$이면 많은 PS 문제에서 Acceptable한 시간복잡도이기 때문에 더욱 그렇다.

그럼에도 아직도 버려지는 정보가 있다.

우리는 다음과 같은 의문을 가져볼 수 있다.

각 중심을 기준으로 하는 회문을 길이 1짜리 회문부터 찾아야하는 것인가?

여기까지 왔다면 위의 질문에 대한 답이 'No'라는 것을 대략 추측하셨으리라 믿는다.

각 index를 중심으로 하는 최대 회문의 반지름을 $A$라고 하고 $A$배열을 채운다고 해보자.

$s=\text{banana}$의 경우

위와 같은 배열이 채워지게 되는 것이다.

만약 $s=\text{abacababa}$에 대해서 $A$배열을 구하는 과정에서 다음과 같은 상황을 가정해보자.

다음의 올 문자 b는 $s[4]$를 중심으로 하는 길이 $A[4]=3$인 회문 'abacaba'에 포함되어 있다.

우리는 또한 abacaba가 회문임을 알고, $s[6]$과 $s[2]$가 $s[4]$를 기준으로 대칭임을 안다.

따라서 s[0:2]="aba"가 회문이라는 정보를 이용한다면, 추가적인 계산없이 s[5:7]="aba"가 회문이라는 사실을 알 수 있는 것이다.

이 사실을 이용하면, $A[4]$를 0부터 찾을 필요없이 1부터 찾을 수 있게 된다.

좀더 엄밀하게 얘기하자면 $A[i]$를 계산하고자 할 때, 현재까지 가장 멀리 뻗어있는 회문을 관리하는 것이다.

회문의 index인 $ind=arg\max(j+A[j])$ 와 그 회문이 얼마나 뻗어있는지의 정보인 $x=\max(j+A[j])$를 매번 계산한다.

이 회문 안에 들어가는 범위 내에서는 이미 계산한 $i$의 대칭점인 $i' = 2*ind-i$의 정보를 사용하게 된다.

따라서 0부터 보는 것이 아니라 $\min(A[i'], x-i)$부터 하나씩 늘려가면서 $A[i]$를 찾는 것이다.

만약 $i$가 범위에 들어가지 않는다면 $O(n^2)$ 알고리즘과 동일하게 0부터 계산한다.

시간복잡도는?

시간복잡도를 계산하기 위해서 $A[i]$의 초기값이 어디서 부터 시작하는 지를 체크해야한다.

case 1) 초기값이 $A[i']$이고, $A[i']<x-i$일 때,

이미 A[i']를 계산할때, 더 긴 회문이 없다는 계산이 끝났기 때문에, 이 경우에는 바로 $A[i]=A[i']$을 하고 종료한다.

case 2) 초기값이 $x-i$이거나 0일 때

이 경우에는 원래 $O(n^2)$ 알고리즘과 똑같이 하나씩 늘리면서 계산하게 된다.

이 때 $x$의 값이 1 증가하게 되는데, $x$는 초기값 0부터 감소하지 않고 1씩 증가만 해서 최종적으로 $n$이 된다.

따라서 case 2는 총 $n$번 시행되게 된다.

따라서 시간복잡도는 $O(n)$이 된다.

일반적인 회문은 어떻게 구하는가?

이 알고리즘은 홀수 길이의 회문만 구할 수 있다는 단점이 있다.

짝수 길이의 회문을 구하기 위해서는 string의 중간에 사용하지 않는 문자를 추가해주는 것이다.

예를 들어서 $s=\text{banana}$ 라면 $s'=\text{b@a@n@a@n@a}$로 변경한다.

이렇게 하면 @를 기준으로 하는 회문은 짝수길이의 회문을 모두 표현하게 된다.