안녕하세요.. 처음으로 에디토리얼을 써봅니다..
 
Q1, Q2에서 삽질한 덕분에 Q3을 참여하였는데요..
Q3은 난이도도 무난했고 경쟁도 좀 덜 치열했던 것 같네요.. ㅎㅎ

 
 
250 - Bidirectional Queue (링크)
 
bidirectional queue는 세가지 operation이 있는데
1) queue 맨 왼쪽의 원소를 extract
2) 왼쪽으로 한칸 shift (맨 왼쪽에 있는 원소는 오른쪽 끝으로 이동)
3) 오른쪽으로 한칸 shift (맨 오른쪽에 있는 원소는 왼쪽 끝으로..)
 
vector indice[] 의 원소를 차례대로 뽑고 싶을때 최소 몇번 shift해야 하는지 구하기..
 
 
-- 풀이 --
 
이 문제는 greedy로 쉽게 해결할 수 있습니다.
왼쪽으로 shift하든지 오른쪽으로 shift하든지 그 이후의 상태가 같아지므로..
무조건 적은 비용이 드는 방향으로 shift하면 됩니다.
그 다음은 그냥 simulation 합니다 ;;
 
 
 
500 - PrettyPrintASpiral (링크)
 
 
 
그림과 같은 2차원 grid에서 row1, col1, row2, col2 가 주어질 때,
그 사이에 들어있는 수를 차례로 출력하기..
 
 
-- 풀이 --
 
이 문제의 핵심은 input x, y에 대해서 (x, y)에 있는 값을 어떻게 찾아오느냐 입니다..
우선 (0, 0)을 중심으로 하며 (x, y)를 포함하는 최소의 정사각형 찾습니다..
당근 정사각형의 한쪽 끝 x, y좌표는 max(abs(x), abs(y)) 가 됩니다..
그리고 이 정사각형 선상에 있는 수중에 가장 큰 수를 구합니다.. (2*max(abs(x), abs(y))+1)^2 가 됩니다
그리고 찾으려고 하는 좌표가 정사각형의 오른쪽선상에 있는지 왼쪽선상에 있는지 위에에 있는지 아래 있는지를
판단해서 적절한 연산을 하면 해당 좌표의 값을 구할 수 있습니다..

int get_n(int x, int y)
{
    int k, l, m, n;
    m = max(abs(x), abs(y));
    k = (2*m+1)*(2*m+1);
    if (x <= m && y == m) {
        l = m - x;
        n = k-l;
    }
    else if (x == -m && y <= m) {
        l = m - y;
        n = k - (2*m) - l;
    }
    else if (x <= m && y == -m) {
        l = abs(-m - x);
        n = k - (4 * m) - l;
    }
    else {
        l = abs(-m - y);
        n = k - (6*m) - l;
    }
    return n;
}

 
1000 - MatchedStrings (링크)

( 또는 ) 로 이루어진 string 중에서 ( 와 ) 가 짝이 맞는 경우를 well-parenthesized 이라고 합니다
예를들어 다음은 다 well-parenthesized 입니다
 
empty string
()()()
(()())()()
((()))
 
well-parenthesized 가 아닌 string 을 mismatched라고 하는데..
'(' 와 ')' 로 이루어진 길이 N짜리 string 중에서 lexicographically K-th mismatched string을 구하는 문제입니다
 

 
-- 풀이 --
 
기본 아이디어는 우선 empty string에서 시작해서..
'(' 를 붙여보고 앞으로 나올 수 있는 mismatched가 몇개인지 세봅니다
'('를 붙여서 K-th smallest string을 만들 수 없다고 판단되면 대신 ')' 를 붙입니다..
')'를 붙일 경우 '('를 붙였을 때 만들 수 있는 string의 개수 만큼을 건너뛰게 되므로 K 값에서 빼주면서 진행합니다..
 
이 문제를 풀기 위해 먼저 다음과 같은 table을 구해두면 편합니다
 
match[i][j] = 길이 i 이면서 j개의 '(' 가 아직 닫히지 않은 string의 개수
                   (또는 j개의 '('를 닫을 수 있는 string의 개수??)
 
 

long long match[60][60];
int n;
long long get_cnt(string str)
{
    int i, j, len;
    long long cnt;
    len = str.size();
    cnt = 1LL << (n-len);
    j = 0;
    for (i = 0; i < len; i++) {
        if (str[i] == '(')
            j++;
        else
            j--;
        if (j < 0)
            return cnt;
    }
    return cnt - match[n-len][j];
}
class MismatchedStrings {
public:
string getString(int N, long long K)
{
    int i, j;
    long long cnt;
    string res;
    n = N;
    memset(match, 0, sizeof(match));
    match[0][0] = 1;
    for (i = 1; i <= n; i++) {
        for (j = 0 ; j <= n; j++) {
            match[i][j] = match[i-1][j+1];
            if (j-1 >= 0)
                match[i][j] += match[i-1][j-1];
        }
    }
    res = "";
    if (K >= (1LL << N) - match[N][0]) {
        return res;
    }
    for (i = 0; i < N; i++) {
        res += '(';
        cnt = get_cnt(res);
        if (cnt <= K && K) {
            K -= cnt;
            res[res.size()-1] = ')';
        }
    }
    return res;
}
};

이상 tomek의 솔루션 이었습니다..
틀린점이 있으면 알려주세요.. ㅎㅎ;;
code highliting 어떻게 하는건가요..?
크롬에서 쓰다가 이상해졌어요..;