주어진 문제는 위와 같다. n 을 크기로 갖는 문자열 'keysPressed' 와 배열 'releaseTimes' 이 주어지는데 'keysPressed' 는 어떤 순간 어떤 키가 눌렸는 지, 'releaseTimes' 는 각 키가 떼진 순간의 시간을 의미한다.
i 번째로 눌린 키가 눌려진 기간은 releaseTimes[i] - releaseTimes[i - 1] 로 표현된다. (0 번째 키는 releaseTimes[0]) 주어진 정보를 바탕으로 가장 오랫동안 눌려진 키를 찾는 문제이다. 서로 다른 순간에 같은 키가 눌릴 수 있고, 같은 키가 눌린 시간은 각각의 시간으로만 평가하고 누적되지 않는다. 가장 오래 눌려진 키가 여러 개일 경우에는, 사전적으로 더 큰 값을 갖는 키를 정답으로 갖는다.
이 문제는, 단순히 0 번째부터 n - 1 번째까지 (0 - indexed) 각각의 키가 눌린 시간을 계산해 그 중 가장 큰 값을 찾도록 하는 방식으로 문제를 해결했고, 해결을 위해 작성한 소스 코드는 다음과 같다.
class Solution {
public:
char slowestKey(vector<int> &releaseTimes, string keysPressed) {
int len = keysPressed.length();
char ans = keysPressed[0];
int longestDuration = releaseTimes[0];
for (int i = 1; i < len; i++) {
int duration = releaseTimes[i] - releaseTimes[i - 1];
if (duration > longestDuration || (duration == longestDuration && keysPressed[i] > ans)) {
ans = keysPressed[i];
longestDuration = duration;
}
}
return ans;
}
};
주어진 문제는 위와 같다. 트리 노드의 개수인 n 이 주어지면, n 개의 노드를 갖는 BST 들을 찾는 것이다. 이 때, n 개의 노드들은 각각 1 부터 n 까지의 값을 갖는다.
BST (Binary Search Tree) 는 기본적으로 각 서브트리에서 루트 노드보다 작은 값들만 루트 노드의 Left 서브 트리에 저장될 수 있고, 루트 노드보다 큰 값들만 루트 노드의 Right 서브 트리에 저장될 수 있다는 특징을 갖는다.
이러한 특징을 기반으로 재귀를 활용해 문제를 풀이했다. 풀이 방식은 각 재귀 단계마다 BST 를 구성하려는 값의 범위 start ~ end 가 주어지고 그 범위 내의 값들을 루트 노드로 하는 BST 를 찾는 것이다.
간단한 슈도 코드로 이를 표현하자면, 다음과 같다.
recursiveBST(start, end):
for i in (start, end):
leftLists <- recursive_bst(start, i - 1)
rightLists <- recursive_bst(i + 1, end)
for left in leftLists:
for right in rightLists:
root <- new node(i)
root.left <- left
root.right <- right
(start, end) 범위 내에서 각각의 값을 갖는 노드를 루트 노드로 구성하고, 그 값보다 작은 값들을 갖는 서브 트리들과 그 값보다 큰 값들을 갖는 서브 트리들을 각각 루트 노드의 왼쪽 서브 트리, 오른쪽 서브 트리로 구성한다.
이러한 풀이 방식을 바탕으로 작성한 소스 코드는 다음과 같다.
class Solution {
public:
vector<TreeNode*> generateTrees(int start, int end) {
vector<TreeNode*> binarySearchTrees;
if (start > end) {
binarySearchTrees.push_back(NULL);
return binarySearchTrees;
}
if (start == end) {
binarySearchTrees.push_back(new TreeNode(start));
return binarySearchTrees;
}
for (int i = start; i <= end; i++) {
vector<TreeNode*> leftList = generateTrees(start, i - 1);
vector<TreeNode*> rightList = generateTrees(i + 1, end);
for (int l = 0; l < leftList.size(); l++) {
for (int r = 0; r < rightList.size(); r++) {
TreeNode* root = new TreeNode(i);
root->left = leftList[l];
root->right = rightList[r];
binarySearchTrees.push_back(root);
}
}
}
return binarySearchTrees;
}
vector<TreeNode*> generateTrees(int n) {
return generateTrees(1, n);
}
};
주어진 문제는, 어떤 배열이 주어졌을 때 그 배열에서 가장 작은 값을 찾는 문제이다. 이 때, 배열은 정렬된 배열을 rotation 시킨 배열로 주어진다.
예를 들어, [0, 1, 2, 3, 4, 5, 6, 7] 과 같이 정렬된 배열이 주어질 수도 있고 [4, 5, 6, 7, 0, 1, 2, 3] 과 같이 앞의 정렬된 배열에서 [0, 1, 2, 3] 의 위치가 뒤로 이동한 배열이 주어질 수도 있다.
이 문제에서 주어진 조건은, 문제 해결 시 O(log n) 의 시간복잡도를 갖는 알고리즘을 사용해야 한다는 것이다.
문제 해결 전략은 다음과 같다. 기본적으로 이분 탐색을 사용해 배열을 반씩 분할해 각 분할마다 최소값을 찾고, 그 중 가장 최소값을 찾는다.
로테이션이 된 배열이기 때문에, 전체 배열은 정렬이 되지 않은 상태일 수 있지만 부분 배열은 정렬이 된 상태일 수 있다. 위의 [4, 5, 6, 7, 0, 1, 2, 3] 의 배열을 반으로 분할해 보면, [4, 5, 6, 7], [0, 1, 2, 3] 과 같이 표현된다. 이 때 각 부분배열은 모두 정렬된 상태이므로 최소값을 쉽게 찾을 수 있다.
만약, 분할된 부분배열이 정렬되지 않은 배열일지라도, 예를 들어 [4, 5, 0] 이라고 하면 이러한 배열은 다시 또 분할을 해서 정렬된 상태가 될 때까지 분할을 하면 된다. 계속 반으로 분할을 하다보면, 언젠가는 정렬된 부분배열이 될 것이고 (혹은 한 개의 원소만 남은 배열이 되거나) 그 때의 최소값은 바로 탐색할 수 있기 때문에 이 방법은 O(log n) 의 시간복잡도를 갖는 알고리즘이라 할 수 있다.
위와 같은 풀이로 작성한 소스 코드는 다음과 같다.
class Solution {
public:
int binarySearch(vector<int>& nums, int s, int e) {
if (s >= e) {
return nums[s];
}
if (nums[s] < nums[e]) {
return nums[s];
}
int m = (s + e) / 2;
int l = binarySearch(nums, s, m);
int r = binarySearch(nums, m + 1, e);
return l < r ? l : r;
}
int findMin(vector<int> &nums) {
int min = binarySearch(nums, 0, nums.size() - 1);
return min;
}
};
주어진 문제는, 주어진 n, k 에 해당하는 순열을 찾는 것이다. n (1 <= n <= 9) 은 순열에 포함되는 수의 개수이고, k (1 <= k <= n!) 는 순열의 순서이다.
예를 들어, (n, k) 가 (3, 3) 으로 주어졌다면 기대되는 출력값은 "213" 이 된다. 위의 그림에서 보여지듯, "123", "132", "213", ... 의 순서로 순열을 생성할 수 있고, 그 중 k 번째 수열은 "213" 이다. (1-indexed)
이 문제를 해결하기 위한 전략은 다음과 같다. n 이 3일 때 생성되는 순열은 "123", "132" / "213", "231" / "312", "321" 이다. '/' 로 나눠놓은 것을 보면 각각 수열이 갖는 첫번째 수가 같은 것끼리 묶여있음을 알 수 있고, 이를 바탕으로 문제를 해결할 수 있음을 유추할 수 있다.
(n, k) 가 (4, 7) 로 주어진 경우를 생각해 보면, n 이 4이므로 사용 가능한 숫자들의 목록은 [1, 2, 3, 4] 가 된다. 세 개의 숫자로 구성할 수 있는 수열은 6개이므로 "1", "2", "3", "4" 로 시작하는 각각의 수열의 개수는 6개임을 알 수 있다. 이 때, 각 숫자의 순서대로 수열이 순서를 가지므로 k 가 7이라는 것은, "2" 로 시작하는 수열을 찾고자 함을 알 수 있고, 그 중 1번째 수열임을 알 수 있다.
이러한 방식으로, 첫 번째 숫자를 찾고 그 뒤에는 남은 [1, 3, 4] 를 통해 앞으로 어떤 숫자들이 수열에 순서대로 위치할 지를 찾아낼 수 있다. 문제를 풀이한 소스 코드는 다음과 같이 작성했다.
class Solution {
public:
int factorial(int n) {
int result = 1;
while (n > 1) {
result *= n--;
}
return result;
}
string getPermutation(int n, int k) {
vector<int> nums;
for (int i = 1; i <= n; i++) {
nums.push_back(i);
}
string ans = "";
while (n > 1) {
int blockSize = factorial(n - 1);
int block = k / blockSize;
k %= blockSize;
ans += to_string(nums[block]);
nums.erase(nums.begin() + block);
n--;
}
return ans + to_string(nums[0]);
}
};
n 명의 아이들을 의미하는 정수형 배열이 주어졌을 때, 배열에 저장된 값은 해당 위치에 서 있는 아이의 우선순위를 의미한다. 아이들에게 Candy 를 나눠주고자 하는데 모든 아이들은 최소 1개 이상의 Candy 를 받아야 하고 이웃한 아이보다 우선순위가 높은 아이는 이웃 아이보다 Candy 를 더 받아야 한다. 이 때, 아이들에게 최소한의 갯수로 위 규칙을 만족시키며 Candy 를 분배하는 Candy 의 수를 구하는 문제
이 문제는, DP 방식으로 문제를 해결할 수 있었는데 우선 각 아이 별로 왼쪽에 있는 아이보다 많이 받는 경우와 오른쪽에 있는 아이보다 많이 받는 경우를 각각 계산했다. 그 후, 둘 중 더 많은 Candy 를 받는 경우를 계산하면 최소한의 Candy 로 규칙을 만족시키며 분배할 수 있다.
예를 들어, ratings 배열이 [1, 0, 2] 로 주어졌을 때 Candy 를 가져가는 개수는 [2, 1, 2] 로 총 5개가 필요하게 된다. 왼쪽에 있는 아이보다 많이 받는 경우를 계산하면 [1, 1, 2] 가 되는데 ratings[1] 은 0 이므로 ratings[0] 보다 작아 더 많이 받을 필요가 없고, ratings[2] 는 2 이고 ratings[1] 은 1 이므로 3번째 아이는 2번째 아이보다 Candy 를 많이 받아야 한다. 반대로 오른쪽에 있는 아이보다 많이 받는 경우는 [2, 1, 1] 이 되는데 ratings[0] 의 오른쪽에 ratings[1] 이 더 작으므로 첫 번째 아이가 Candy 를 많이 받게 된다. 두 경우에서 각 아이가 받는 Candy 의 개수는 최대가 되어야 왼쪽과 오른쪽의 경우를 모두 만족할 수 있으므로 결과적으로 [2, 1, 2] 로 Candy 를 분배하게 된다.
위와 같은 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
int candy(vector<int>& ratings) {
int sum = 0, n = ratings.size();
vector<int> left(n, 1);
vector<int> right(n, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
for (int i = 0; i < n; i++) {
sum += max(left[i], right[i]);
}
return sum;
}
};
정수형 배열 nums 가 주어졌을 때, 각 인덱스 별로 자기보다 오른쪽에 있는 수 중 자기보다 작은 수들의 개수를 구하는 문제
예를 들어, 배열 nums 가 [5, 2, 6, 1] 과 같이 주어졌을 때 정답은 [2, 1, 1, 0] 이다. 가장 오른쪽에 있는 '1' 은 자기보다 오른쪽에 있는 값이 없기 때문에 무조건 0이 되고, '6' 과 '2' 는 오른쪽에 '1' 이, '5'는 오른쪽에 '2', '1' 이 있어 각각 1 과 2 를 정답으로 갖는다.
이 문제를 풀기 위한 방법으로 두 가지 방법을 사용했다. 첫 번째 방법은 Merge Sort 를 활용한 방법이었고 두 번째는 Binary Index Tree 의 일종인 Fenwick Tree 를 활용한 방법이다.
우선, Merge Sort 를 활용한 방법은 아이디어가 전혀 떠오르지 않아 아래 Reference 를 참고했다. Merge Sort 는 기본적으로 Divide & Conquer 방식으로 정렬을 수행하는데, 이 때 매 단계 별로 시작 위치 ~ 끝 위치 중 가운데 위치를 선정하고, 시작 위치 ~ 가운데 위치 / 가운데 위치 + 1 ~ 끝 위치까지 정렬을 먼저 한 후 시작 위치 ~ 끝 위치의 정렬을 수행한다. 정렬을 할 때, 시작 위치 ~ 가운데 위치 / 가운데 위치 + 1 ~ 끝 위치는 각각 정렬이 된 상태이므로 (아래 단계에서 이미 정렬을 하고 난 상태) 두 배열을 (위치 별로 나눈 것을 두 배열이라 표현) 합치는 과정에서 두 배열 중 작은 값을 먼저 배치하는 방식으로 정렬을 한다. 이를 간단히 코드로 표현하면 다음과 같다.
void merge (int[] arr, int[] tmp, int st, int ed) {
for (int i = st; i <= ed; i++)
tmp[i] = arr[i];
int mid = (st + ed) / 2;
int i = st, j = mid + 1, k = st;
while (i <= mid && j <= ed) {
if (tmp[i] <= tmp[j])
arr[k++] = tmp[i++];
else
arr[k++] = tmp[j++];
}
while (i <= mid)
arr[k++] = tmp[i++];
while (j <= ed)
arr[k++] = tmp[j++];
}
이 문제를 해결하기 위해, Merge Sort 에 추가적으로 도입한 아이디어는 두 배열을 하나로 합치는 과정에서 뒤 배열의 값들이 앞 배열보다 먼저 배치될 경우 앞 배열의 값들은 원래 위치에서 자기보다 오른쪽에 먼저 배치된 값들이 존재한다는 것이다. 즉, 위의 merge 소스 코드에서 앞 배열과 뒤 배열의 값들을 서로 비교해 합치는 과정에서 뒤 배열의 값이 더 크다면 그러한 개수만큼 저장을 하고 앞 배열의 값을 배치할 때 해당 값이 원래 위치했던 인덱스의 결과를 증가시키면 되는 것이다.
이러한 해결 방법으로 작성한 코드는 아래와 같다.
struct node {
int idx, val;
};
class Solution {
public:
void merge(vector<int>& ans, vector<node>& numVector, vector<node>& copyVector, int st, int mid, int ed) {
for (int i = st; i <= ed; i++) {
copyVector[i] = numVector[i];
}
int i = st, j = mid + 1, k = st, cnt = 0;
while (i <= mid && j <= ed) {
if (copyVector[i].val <= copyVector[j].val) {
ans[copyVector[i].idx] += cnt;
numVector[k++] = copyVector[i++];
}
else {
cnt++;
numVector[k++] = copyVector[j++];
}
}
while (i <= mid) {
ans[copyVector[i].idx] += cnt;
numVector[k++] = copyVector[i++];
}
while (j <= ed) {
numVector[k++] = copyVector[j++];
}
}
void mergeSort(vector<int>& ans, vector<node>& numVector, vector<node>& copyVector, int st, int ed) {
if (st >= ed)
return;
int mid = (st + ed) / 2;
mergeSort(ans, numVector, copyVector, st, mid);
mergeSort(ans, numVector, copyVector,mid + 1, ed);
merge(ans, numVector, copyVector, st, mid, ed);
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, 0);
vector<node> numVector(n);
vector<node> copyVector(n);
for (int i = 0; i < n; i++) {
numVector[i].idx = i;
numVector[i].val = nums[i];
}
mergeSort(ans, numVector, copyVector, 0, n - 1);
return ans;
}
};
위 방식으로 문제를 해결할 수는 있었지만, 시간복잡도는 O(NlogN) 으로 (N 은 주어진 nums 배열의 크기, 최대 10만) 수행시간이 생각보다 길어 다른 방식을 고민하게 되었다. 이 문제에서 nums 배열의 크기는 최대 10만이고, 배열에 저장되는 값들은 -1만 ~ 1만 의 값을 가진다. 즉 O(NlogN) 보다는, O(NlogM) 이 된다면 (이 때 M 은 배열에 저장되는 값의 범위, 이 문제에서는 최대 2만) 수행시간을 조금 더 단축할 수 있을 것으로 생각했다.
이 때, logN 을 logM 으로 바꿀 수 있는 방법으로 부분합을 생각했고, 부분합을 업데이트하는 횟수가 많아 세그먼트 트리보다는 펜윅 트리를 생각했다. 펜윅 트리에 대한 자세한 설명은 아래 Reference 를 참고하면 되고, 간단하게 얘기하면 값들의 업데이트가 많을 때 부분합을 구하고 업데이트하는 것의 시간복잡도가 모두 O(logN) 인 자료구조이다.
펜윅 트리는 기본적으로 인덱스를 사용해 인덱스 ? ~ ? 까지의 합을 저장하는 방식으로 사용하는데, 이 문제에서는 인덱스 대신 nums 배열의 값들을 사용했고 값이 -1만 ~ 1만의 범위를 가지기 때문에, Offset 으로 10001 을 더해서 사용했다. 트리에 저장되는 값들은 해당 값이 등장한 횟수이다.
펜윅 트리를 사용해 작성한 코드는 아래와 같다. 수행시간도 생각한 대로 Merge Sort 를 사용한 방식보다 빨랐고, 펜윅 트리의 Update 나 Sum 을 구하는 코드가 모두 간단하기 때문에 코드도 간단하게 작성할 수 있었다.
class Solution {
public:
const int OFFSET = 10001;
const int SIZE = 20010;
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> tree(SIZE, 0);
vector<int> ans(n, 0);
for (int i = n - 1; i >= 0; i--) {
int cnt = 0;
for (int j = nums[i] + OFFSET - 1; j > 0; j -= (j & -j))
ans[i] += tree[j];
for (int j = nums[i] + OFFSET; j < SIZE; j += (j & -j))
tree[j]++;
}
return ans;
}
};
위 코드를 로직에만 집중하도록 간단하게 모듈화를 조금 더 하자면 다음과 같이 작성할 수 있을 것 같다.
class Solution {
public:
const int OFFSET = 10001;
const int SIZE = 20010;
void update(vector<int>& tree, int idx) {
while (idx < SIZE) {
tree[idx]++;
idx += (idx & -idx);
}
}
int sum(vector<int>& tree, int idx) {
int sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> tree(SIZE, 0);
vector<int> ans(n, 0);
for (int i = n - 1; i >= 0; i--) {
int cnt = 0;
ans[i] = sum(tree, nums[i] + OFFSET - 1);
update(tree, nums[i] + OFFSET);
}
return ans;
}
};
m x n 크기의 Grid 와 하나의 Ball 이 Grid 의 [startRow, startCol] 위치에 주어졌을 때, 이 Ball 이 Grid 밖으로 나가게 되는 경우의 수를 구하는 문제. 문제에서 Ball 은 한 번에 가로 / 세로 방향으로만 움직일 수 있고, 최대 움직임 횟수는 제한된다.
처음 문제를 확인하고 Brute Force 방식으로 해결하면 될 것 같다는 생각을 하고 풀이를 시작했는데, 공이 한 번 위치한 장소에 다시 돌아올 수 있기 때문에 완전 탐색 방식은 시간이 너무 오래 걸렸다. 그래서 변경한 풀이 방식은, m x n 행렬에 움직임의 횟수 별로 공이 각 칸에 위치할 수 있는 경우의 수를 저장하고 이를 통해 Grid 밖으로 나갈 수 있는 경우의 수를 구하는 방식이다.
위의 그림을 통해 설명하면, 공의 초기 위치가 (0, 0) 이므로 초기 행렬은 아래와 같이 표현이 가능하다. 이 때, 공이 Grid 밖으로 나갈 수 있는 경우의 수는 (0, 0) 에서 위 방향 / 왼쪽 방향 총 두 경우이다.
1
0
0
0
공이 한 번 움직이고 난 다음의 행렬은 아래와 같다. 이 때, 공이 Grid 밖으로 나가는 경우는 (0, 1) 위치에서 위 / 오른쪽 방향, (1, 0) 위치에서 왼쪽 / 아래 방향, 총 네 가지이다.
0
1
1
0
위 그림에서, 공이 움직일 수 있는 최대 횟수는 2번으로 제한되어 있으므로 두 번 움직이고 난 후의 경우는 구할 필요가 없다. 한 번 움직여서 Grid 를 벗어나는 경우가 2가지, 두 번 움직여서 Grid 를 벗어나는 경우가 4가지 이므로 총 6개가 답이 된다.
이와 같은 풀이로 작성한 코드는 다음과 같다.
const int MOD = (int)1e9 + 7;
int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, -1, 0, 1};
int dp[51][51], tmp[51][51];
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
dp[i][j] = tmp[i][j] = 0;
dp[startRow][startColumn] = 1;
int ans = 0;
for (int move = 1; move <= maxMove; move++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) ans = (ans + dp[i][j]) % MOD;
if (j == 0) ans = (ans + dp[i][j]) % MOD;
if (i == m - 1) ans = (ans + dp[i][j]) % MOD;
if (j == n - 1) ans = (ans + dp[i][j]) % MOD;
tmp[i][j] = 0;
if (i > 0)
tmp[i][j] = (tmp[i][j] + dp[i - 1][j]) % MOD;
if (j > 0)
tmp[i][j] = (tmp[i][j] + dp[i][j - 1]) % MOD;
if (i < m - 1)
tmp[i][j] = (tmp[i][j] + dp[i + 1][j]) % MOD;
if (j < n - 1)
tmp[i][j] = (tmp[i][j] + dp[i][j + 1]) % MOD;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = tmp[i][j];
}
}
}
return ans;
}
};
N-Queens (https://ggop-n.tistory.com/34) 문제와 유사하지만, 앞선 문제에서 N 개의 Queen 을 배치한 체스판을 결과로 return 하는 게 아닌, N 개의 Queen 을 배치한 체스판이 몇 개의 모양으로 존재할 수 있는 지를 구하는 문제
N-Queens 문제 풀이와 풀이 방식은 동일하게 진행했고, 차이가 있었던 점은 결과값으로 몇 개의 경우가 존재하는 지만 저장하도록 했다.
작성한 코드는 다음과 같다.
class Solution {
public:
int ans;
bool check(vector<vector<bool>>& board, int r, int c, int n) {
for (int k = 1; r - k >= 0; k++) {
if (board[r - k][c])
return false;
if (c - k >= 0 && board[r - k][c - k])
return false;
if (c + k < n && board[r - k][c + k])
return false;
}
return true;
}
void solveNQueen(vector<vector<bool>>& board, int row, int n) {
if (row == n) {
ans++;
return;
}
for (int j = 0; j < n; j++) {
if (check(board, row, j, n)) {
board[row][j] = true;
solveNQueen(board, row + 1, n);
board[row][j] = false;
}
}
}
int totalNQueens(int n) {
vector<vector<bool>> board(n, vector<bool>(n, false));
solveNQueen(board, 0, n);
return ans;
}
};
유명한 BackTracking 문제라 DFS 를 활용해 문제를 풀이했다. 문제의 답으로 체스판을 문자열로 표현해야 해서 빈 체스판을 먼저 저장해 놓고, Queen 을 한 개씩 배치하며 해당 위치에 배치 가능한 지 확인했다. 총 N 개 Queen 이 배치된 후 체스판을 결과물 저장하는 Vector 에 추가했다.
이러한 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
vector<vector<string>> ans;
int dr[4] = {-1, -1, 1, 1}, dc[4] = {-1, 1, -1, 1};
bool check(vector<string>& curVec, int i, int j, int n) {
// 가로 세로
for (int k = 0; k<n; k++) {
if (curVec[i][k] == 'Q')
return false;
if (curVec[k][j] == 'Q')
return false;
}
// 대각선
for (int k = 1; ; k++) {
bool flag = false;
for (int l = 0; l < 4; l++) {
int ni = i + dr[l] * k, nj = j + dc[l] * k;
if (ni >= 0 && ni < n && nj >= 0 && nj < n) {
flag = true;
if (curVec[ni][nj] == 'Q')
return false;
}
}
if (!flag)
break;
}
return true;
}
void solveRecursive(vector<string>& curVec, int r, int cnt, int n) {
if (cnt == n) {
ans.push_back(curVec);
return;
}
for (int i = r; i<n; i++) {
for (int j = 0; j<n; j++) {
if (curVec[i][j] == '.' && check(curVec, i, j, n)) {
curVec[i][j] = 'Q';
solveRecursive(curVec, i + 1, cnt + 1, n);
curVec[i][j] = '.';
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
string s;
for (int i = 0; i<n; i++) {
s += ".";
}
vector<string> vec;
for (int i = 0; i<n; i++) {
vec.push_back(s);
}
solveRecursive(vec, 0, 0, n);
return ans;
}
};
위와 같이 코드를 작성했더니 시간이 너무 오래 걸렸다. 불필요한 조건 검사가 많고 생각을 너무 단순하게 해서 그런 것으로 생각이 되었다. 우선, 위에서 가로 검사의 경우는 한 줄에 하나의 Queen 만 배치가 가능하므로 굳이 검사를 할 필요가 없고, 세로 검사의 경우도 현재 위치보다 아래 줄은 검사를 할 필요가 없다. 또한 대각선 검사의 경우도 마찬가지로 현재 위치보다 윗줄만 검사를 하면 되어 이렇게 수정해 코드를 다시 제출했다.
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
vector<string> nQueen(n, string(n, '.'));
solveNQueens(ans, nQueen, 0, n);
return ans;
}
void solveNQueens(vector<vector<string>>& ans, vector<string>& nQueen, int r, int n) {
if (r == n) {
ans.push_back(nQueen);
return;
}
for (int j = 0; j<n; j++) {
if (check(nQueen, r, j)) {
nQueen[r][j] = 'Q';
solveNQueens(ans, nQueen, r + 1, n);
nQueen[r][j] = '.';
}
}
}
bool check(vector<string>& nQueen, int i, int j) {
for (int k = 1; i - k >= 0; k++) {
if (nQueen[i - k][j] == 'Q')
return false;
if (j - k >= 0 && nQueen[i - k][j - k] == 'Q')
return false;
if (j + k < nQueen.size() && nQueen[i - k][j + k] == 'Q')
return false;
}
return true;
}
};
문자열 s 와 패턴 p 의 길이는 각각 0 ~ 2000 으로 제한되고 s 는 영어 소문자로만 이루어진 문자열, p 는 영어 소문자와 '?' '*' 로만 이루어진 문자열 패턴으로 주어진다. '?' 은 어떤 문자든 하나만 매치가 가능하고, '*' 은 어떤 문자열의 연속이든 매치될 수 있다. (빈 문자열도 가능)
문제의 풀이 방식은 다음과 같다. s 와 p 의 인덱스를 각각 저장하고 현재 인덱스의 문자열과 패턴을 비교해 어떤 인덱스를 증가시킬 것인지 선택한다.
우선, s 의 현재 문자를 sc, p 의 현재 문자를 pc 라 하면 sc 와 pc 가 같거나 pc 가 '?' 일 때는 두 인덱스를 모두 증가시킨다.
그렇지 않고, pc 가 '*' 일 경우, '*' 문자가 등장한 패턴의 위치와 문자열의 위치를 저장한다. 이후 문자열과 패턴이 일치하지 않을 때 다시 돌아가서 확인하기 위함이다.
마지막으로, 위의 조건에 부합하지 않은 경우는 기존에 저장된 '*' 문자가 있는 지를 확인한 후, 해당 위치로 돌아가서 문자열 인덱스를 하나 증가시킨다. '*' 문자는 어떤 문자열과도 매칭이 가능하기 때문에 다시 해당 위치부터 매칭 조건을 확인하도록 한다.
문자열 탐색이 완료된 후 패턴의 인덱스가 패턴의 길이와 일치하지 않는 경우는, 남은 패턴의 문자가 모두 '*' 문자인 지 확인한 후 그렇지 않으면 매칭이 되지 않는다 판단한다. 또한 어떤 조건에도 부합하지 않는 경우에도, 매칭이 불가능한 문자열과 패턴으로 판단한다.
이와 같은 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
bool isMatch(string s, string p) {
int si = 0, pi = 0;
int star = -1, stari = 0;
while (si < s.length()) {
if (p[pi] == '?' || s[si] == p[pi]) {
si++;
pi++;
continue;
}
if (p[pi] == '*') {
star = pi++;
stari = si;
continue;
}
if (star != -1) {
pi = star + 1;
si = ++stari;
continue;
}
return false;
}
while (pi < p.length()) {
if (p[pi] != '*')
return false;
pi++;
}
return true;
}
};
