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;
}
};
정수형 배열이 주어지고, 이 배열이 저장하고 있는 값이 해당 위치의 벽의 높이라고 했을 때, 빗물을 받을 수 있는 총량을 구하는 문제
이 문제는 Two Pointer 방식으로 문제를 해결할 수 있었는데, Left 와 Right 에 각각 인덱스 포인터를 두고 이를 이동하면서 문제를 풀이하는 방식이다. 인덱스 포인터를 이동하면서 Left 에서의 최대값과 Right 에서의 최대값을 각각 저장해 두고 현재 인덱스 위치가 이보다 값이 작을 경우 빗물을 받을 수 있게 된다.
예를 들어, 위의 그림에서 left 는 0부터 right 는 11부터 시작한다. left, right 인덱스 위치를 보고 높이가 낮은 쪽을 우선한다.
현재 left 인덱스가 1인 경우, left max (0) 보다 현재 높이가 높으므로 left max 를 갱신한다. 그 다음 left 가 2가 되었을 때, 현재 높이보다 left max 가 크므로 left max 와 현재 높이의 차이만큼 물을 받을 수 있게 된다.
이러한 방식으로 left 와 right 포인터를 각각 이동하며 빗물을 받는 양을 구할 수 있다. 이러한 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0, left_max = 0, right_max = 0;
int left, right;
for (left = 0, right = height.size() - 1; left < right; ) {
if (height[left] < height[right]) {
if (height[left] >= left_max) {
left_max = height[left];
}
else {
ans += left_max - height[left];
}
left++;
}
else {
if (height[right] >= right_max) {
right_max = height[right];
}
else {
ans += right_max - height[right];
}
right--;
}
}
return ans;
}
};
정렬되지 않은 정수형 배열 nums 가 주어졌을 때, 배열에서 등장하지 않은 양의 정수 중 가장 작은 수를 찾는 문제
문제 조건으로 시간 복잡도는 O(n), 공간 복잡도는 O(1) 로 주어졌다.
문제에서 주어진 시간 복잡도 조건이 O(n) 이기 때문에 정렬을 하거나 하는 등의 방법은 사용이 불가능했고, 단순히 순차 탐색을 통해서만 문제를 해결해야 했다. 이 문제의 경우 풀이 방법을 고민하다가 다른 사람들의 풀이를 보고 아이디어를 얻어 문제를 풀었는데 그 아이디어는 다음과 같다.
문제에서 찾고자 하는 수는 nums 의 길이가 n 이라고 할 때, 1 ~ n+1 사이에 존재한다.
이 아이디어를 통해 생각한 풀이는, 숫자들을 순서대로 나열하면 그 중 빈 자리가 존재할 것이고, 그 위치에 있어야 하는 수가 정답이 되는 것이다. 그래서 순차적으로 배열을 탐색하고 탐색 과정에서 저장된 수들이 각자 맞는 위치에 들어가 있는 지를 확인하고 그렇지 않다면 자리를 서로 바꿔준다.
예를 들어 [1, 2, 3, 4, 5] 는 순서대로 숫자들이 들어가 있기 때문에 자리를 바꿔줄 필요가 없지만 [1, 2, 5, 4, 3] 은 [5, 4, 3] 의 자리가 순서에 어긋나므로 [3, 4, 5] 로 변경해 [1, 2, 3, 4, 5] 의 모양을 갖도록 한다. 이렇게 1 부터 n 까지의 수가 차례대로 저장된 경우는 그 다음으로 큰 수인 n + 1 이 문제의 답이 된다. 그렇지 않고 [1, 2, 4, 5, 6] 과 같은 모양을 하게 된다면 이를 원래 자리로 숫자들을 옮기면 [1, 2, 6, 4, 5] 가 될 것이다. 왜냐하면, 6 은 이 배열의 길이 5 보다 큰 수이기 때문에 적절한 위치가 없다. 그러므로 배열 탐색 중 중간에 3이 들어가야 할 위치에 6이 들어가 있고 문제의 답은 3이 된다.
이러한 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
// 일단 숫자가 1 ~ n 사이인 지 확인하고
// 자기 자리 찾아주기
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
문자열 s 와, 각각이 동일한 길이를 갖는 단어들 words 가 주어졌을 때 words 를 모두 연결해서 나올 수 있는 substring 을 찾는 문제
예를 들어, s 가 "barfoothefoobarman" 이고 words 가 ["foo","bar"] 이면 words 를 모두 연결했을 때 나올 수 있는 문자열은 "foobar" 와 "barfoo" 두 가지이다. 문자열 s에서 위 문자열은 다음과 같이 나타난다. "barfoothefoobarman". 이 때 반환값은 문자열 s에서 찾고자 하는 문자열 words 의 결합이 나타나는 곳의 시작 위치이다.
이 문제에서 중요한 것은, words 의 결합된 문자열의 시작 위치가 어떤 순서로 반환되는 지는 상관이 없다는 점이다. 문제를 해결하기 위해 생각한 방법은 주어진 words 에서 각각의 word 의 등장 횟수를 저장하고, s 를 순차적으로 탐색하면서 해당 위치에서 부분 문자열이 words 에 주어진 word 중 하나인지, 맞다면 count 값을 증가시켜 각 word 별로 등장 횟수가 words 에서 얻은 정보와 일치하는 지를 확인한다.
이와 같은 풀이로 작성한 코드는 다음과 같다.
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> indexes;
unordered_map<string, int> counts;
for (auto word : words) {
counts[word]++;
}
int len = s.length(), n = words.size(), wordLen = words[0].length();
for (int i = 0; i < len - n * wordLen + 1; i++){
unordered_map<string, int> seen;
int j;
for (j = 0; j < n; j++){
string word = s.substr(i + j * wordLen, wordLen);
if (counts.find(word) != counts.end()) {
seen[word]++;
if (seen[word] > counts[word])
break;
}
else
break;
}
if (j == n)
indexes.push_back(i);
}
return indexes;
}
};
위의 코드는 매 탐색 별로 이전 탐색의 정보를 이용하지 않지만, 보완할 수 있다면 위의 코드를 Sliding Window 기법을 활용해 이전 탐색에 이어서 탐색을 이어갈 수 있도록 하면 성능 면에서 더 효율적으로 동작할 수 있을 것 같다.
