안녕하세요.. 처음으로 에디토리얼을 써봅니다..
 
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)² 가 됩니다
그리고 찾으려고 하는 좌표가 정사각형의 오른쪽선상에 있는지 왼쪽선상에 있는지 위에에 있는지 아래 있는지를
판단해서 적절한 연산을 하면 해당 좌표의 값을 구할 수 있습니다..
~~~ cpp
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의 개수??)
 
 
~~~ cpp
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 어떻게 하는건가요..?
크롬에서 쓰다가 이상해졌어요..;
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/56221">원문보기</a>]</div>