수식이 여러 개 주어지면 어려울 수 있겠지만, 지문에서는 최대 [ *, +, - ]만 주어졌기 때문에 충분히 next_permutation을 활용할 수 있을 것이라 판단했습니다. 이를 위해 처음 받는 expression을 파싱해줍니다.
1. Numbers : 파싱된 숫자들
2. Formulas : 파싱된 연산자들
3. FormulaSet : 연산자가 어떤 것들이 있는지
3번을 따로 사용한 이유는 중복을 제거하여 expression 내에 무슨 종류의 연산자가 존재하는지 판단하기 위함입니다. 이제 이 3종류의 컨테이너에 파싱된 값들을 넣어주고, next_permutation을 실행합니다.
순회 도중 중간에 요소를 삭제하기 위하여 for문보다는 while문을 활용했으며, 순회를 실시하여 현재 지정된 Operator와 Fomula가 동일하다면, Formula에 해당하는 index와 index+1의 값을 서로 연산해주고 erase를 실시하여 컨테이너를 갱신하는 작업을 실시했습니다. 이렇게 계속 수를 줄여나가다보면 최종적으로 현재 순열에 의해 조합된 연산자 순서대로 값을 알아낼 수 있게 됩니다.
#include <string>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <iostream>
using namespace std;
long long solution(string expression)
{
long long answer = 0;
vector<long long> Numbers;
vector<char> Formulas;
unordered_set<char> FormulaSet;
string CurNumber;
for (size_t i = 0; i < expression.size(); ++i)
{
char c = expression[i];
if ('0' <= c && c <= '9')
{
CurNumber += c;
}
else
{
Numbers.push_back(stoll(CurNumber));
CurNumber.clear();
Formulas.push_back(c);
FormulaSet.insert(c);
}
}
// 마지막 숫자
if (!CurNumber.empty())
{
Numbers.push_back(stoll(CurNumber));
}
vector<char> Arr;
Arr.reserve(FormulaSet.size());
for (char Operator : FormulaSet)
{
Arr.push_back(Operator);
}
sort(Arr.begin(), Arr.end());
// 3) 모든 우선순위 순열 시도
do
{
vector<long long> NTemp = Numbers;
vector<char> FTemp = Formulas;
for (char Operator : Arr)
{
size_t j = 0;
while (j < FTemp.size())
{
if (FTemp[j] == Operator)
{
long long L = NTemp[j];
long long R = NTemp[j + 1];
long long Result = 0;
if (Operator == '*') Result = L * R;
else if (Operator == '+') Result = L + R;
else Result = L - R;
NTemp[j] = Result;
NTemp.erase(NTemp.begin() + (j + 1));
FTemp.erase(FTemp.begin() + j);
}
else
{
++j;
}
}
}
long long value = llabs(NTemp[0]);
if (value > answer) answer = value;
} while (next_permutation(Arr.begin(), Arr.end()));
return answer;
}
딱히 어떤 알고리즘이 필요한 문제는 아닌 것 같아 algorithm의 rotate() 함수를 활용하여 풀었습니다. 구역을 총 네 개로 나눈 뒤, 각 구역의 값을 vector로 받아와 rotate()를 실시합니다. 저의 풀이에서는 1, 2 단계의 rotate()의 경우 오른쪽으로 회전, 3, 4 단계의 rotate()의 경우 왼쪽으로 회전시키고 값을 저장(CashMap)해둔 뒤, 최종적으로 원본 데이터에 적용(Map)하는 방식으로 진행했습니다. 추가로 각 요소를 Temp vector에 담을 때마다 min()을 활용하여 보다 낮은 값을 각 단계마다 실시하여 저장해두고 마지막에 answer에 담아주면 됩니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// 주어진 쿼리로 회전시키고(y, x, y, x), 회전시킨 수중에 가장 낮은 수를 answer에 입력해둔 뒤 리턴
vector<int> solution(int rows, int columns, vector<vector<int>> queries)
{
vector<int> answer;
vector<vector<int>> Map(rows);
int Count = 1;
for (int y = 0; y < rows; y++)
{
for (int x = 0; x < columns; x++)
{
Map[y].push_back(Count++);
}
}
vector<vector<int>> CashMap = Map;
int Size = queries.size();
int QueryIndex = 0;
while (Size--)
{
int Y1 = queries[QueryIndex][0] - 1;
int X1 = queries[QueryIndex][1] - 1;
int Y2 = queries[QueryIndex][2] - 1;
int X2 = queries[QueryIndex][3] - 1;
++QueryIndex;
int Min = INT32_MAX;
// [1]
vector<int> Temp1;
int Index = 1;
{
// Map[Y1][X1]; ~ Map[Y1][X2];
// 맨 처음 버림
for (int i = X1; i <= X2; ++i)
{
Min = min(Min, Map[Y1][i]);
Temp1.push_back(Map[Y1][i]);
}
rotate(Temp1.begin(), Temp1.end() - 1, Temp1.end());
for (int i = X1 + 1; i <= X2; ++i)
{
CashMap[Y1][i] = Temp1[Index++];
}
}
// [2]
vector<int> Temp2;
Index = 1;
{
// Map[Y1][X2]; ~ Map[Y2][X2];
// 맨 처음 버림
for (int i = Y1; i <= Y2; ++i)
{
Min = min(Min, Map[i][X2]);
Temp2.push_back(Map[i][X2]);
}
rotate(Temp2.begin(), Temp2.end() - 1, Temp2.end());
for (int i = Y1 + 1; i <= Y2; ++i)
{
CashMap[i][X2] = Temp2[Index++];
}
}
// [3]
vector<int> Temp3;
Index = 0;
{
// Map[Y2][X2]; ~ Map[Y2][X1];
// 맨 마지막 버림
for (int i = X1; i <= X2; ++i)
{
Min = min(Min, Map[Y2][i]);
Temp3.push_back(Map[Y2][i]);
}
rotate(Temp3.begin(), Temp3.begin() + 1, Temp3.end());
for (int i = X1; i <= X2 - 1; ++i)
{
CashMap[Y2][i] = Temp3[Index++];
}
}
// [4]
vector<int> Temp4;
Index = 0;
{
// Map[Y2][X1]; ~ Map[Y1][X1];
// 맨 마지막 버림
for (int i = Y1; i <= Y2; ++i)
{
Min = min(Min, Map[i][X1]);
Temp4.push_back(Map[i][X1]);
}
rotate(Temp4.begin(), Temp4.begin() + 1, Temp4.end());
for (int i = Y1; i <= Y2 - 1; ++i)
{
CashMap[i][X1] = Temp4[Index++];
}
}
answer.push_back(Min);
Map = CashMap;
//for (size_t i = 0; i < Map.size(); i++)
//{
// for (size_t j = 0; j < Map[i].size(); j++)
// {
// cout << Map[i][j] << ' ';
// }
// cout << endl;
//}
}
return answer;
}
결국 이 방식으로 파고 들어가면, k번째에 생성되는 조합은 어떤 경우를 갖는지 알아낼 수 있습니다. { 1, 2, 3 } 수열에서 5번째로 오는 값을 찾는 과정을 아래의 함수로 살펴보겠습니다.
long long factorial(int _Num)
{
long long Result = 1;
for (int i = 1; i <= _Num; ++i)
{
Result = Result * i;
}
return Result;
}
// ...
--k;
for (int i = 0; i < n; ++i)
{
long long Value = factorial(n - 1 - i);
long long Index = k / Value;
k %= Value;
if (Index >= Numbers.size())
{
Index = Numbers.size() - 1;
}
answer.push_back(Numbers[Index]);
Numbers.erase(Numbers.begin() + Index);
}
1. --k : 인덱스는 0부터 계산하기 때문에, 1을 빼서 활용
2. n = 3일 때, 가능한 순열 수는 3! = 6 입니다.
3. i = 0 일 경우
- Value는 (3-1-0)! = 2! = 2
- Index는 4 / 2 = 2
- k %= Value는 0
- 이로써 3이 선택되고, 1. 2가 남습니다.
4. i = 1 일 경우
- Value는 (3-1-1)! = 1! = 1
- Index는 0 / 1 = 0
- k %= Value는 0
- 이로써 1이 선택되고, 2가 남습니다.
4. i = 2 일 경우
- Value는 (3-1-2)! = 0! = 1
- Index는 0 / 1 = 0
- k %= Value는 0
- 이로써 2가 선택되고, 종료됩니다.
결론은 전체 경우의 수 중 5번째의 경우로 3을 선택하고, 그 안에서 다시 첫 번째로 와야하는 경우로 1을 선택하고, 이 과정을 반복하는 것입니다.
#include <string>
#include <vector>
using namespace std;
long long factorial(int _Num)
{
long long Result = 1;
for (int i = 1; i <= _Num; ++i)
{
Result = Result * i;
}
return Result;
}
vector<int> solution(int n, long long k)
{
vector<int> answer;
vector<long long> Numbers;
for (int i = 1; i <= n; ++i)
{
Numbers.push_back(i);
}
--k;
for (int i = 0; i < n; ++i)
{
long long Value = factorial(n - 1 - i);
long long Index = k / Value;
k %= Value;
if (Index >= Numbers.size())
{
Index = Numbers.size() - 1;
}
answer.push_back(Numbers[Index]);
Numbers.erase(Numbers.begin() + Index);
}
return answer;
}
크게 특별한 조건이 없는 그래프 탐색 문제입니다. 우선 방문 설정을 위한 Visited 배열을 하나 만들어주고, 방문했거나 X인 부분은 N, 방문 가능한 곳은 Y로 기록해둡니다.
이후 배열을 순회하면서 Y인 부분이 있다면 해당 지점을 기준으로 BFS()를 실시합니다. BFS를 모두 돌면 연결된 노드들에 대해 Add 값이 산출됩니다. 물론 방문한 노드들은 N으로 기록해주기 때문에 이후 배열 순회에서 해당 지점을 기준으로 BFS()가 실시되지 않을 것입니다.
이 과정을 배열의 모든 요소에 대해 실시하면 무인도(연결된 노드들) 갯수 만큼 답이 나옵니다. 마지막에 오름차순으로 sort()후 리턴해줍니다. 물론 아무것도 방문할 수 없는 상태라면 answer가 empty() 상태일 것입니다. 이 때만 -1을 push_back() 하여 리턴해줍니다.
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
int SearchY[4] = { -1, 0, 1, 0 };
int SearchX[4] = { 0, 1, 0, -1 };
using namespace std;
vector<string> Visited;
void BFS(vector<string>& maps, int _StartY, int _StartX, int& _Add)
{
queue<pair<int, int>> Que;
Que.push(make_pair(_StartY, _StartX));
while (!Que.empty())
{
int CurY = Que.front().first;
int CurX = Que.front().second;
Que.pop();
for (int i = 0; i < 4; i++)
{
int TempY = CurY + SearchY[i];
int TempX = CurX + SearchX[i];
if (TempY < 0 || TempY >= maps.size() || TempX < 0 || TempX >= maps[0].size())
{
continue;
}
if (maps[TempY][TempX] == 'X')
{
continue;
}
if (Visited[TempY][TempX] == 'N')
{
continue;
}
Visited[TempY][TempX] = 'N';
_Add += maps[TempY][TempX] - '0';
Que.push(make_pair(TempY, TempX));
}
}
}
// X = 바다
// 숫자 = 무인도
// 연결된 무인도들의 숫자 합은 최대 무인도에서 머무를 수있는 날
// 연결된 섬들에서 각각 몇일 씩 머물 수 있는지 return, 아무것도 없으면 -1 리턴, 오름차순 정렬
vector<int> solution(vector<string> maps)
{
vector<int> answer;
Visited.resize(maps.size(), "");
for (size_t i = 0; i < maps.size(); i++)
{
for (size_t j = 0; j < maps[i].size(); j++)
{
char Temp = maps[i][j];
if (Temp == 'X')
{
Visited[i] += 'N';
}
else
{
Visited[i] += 'Y';
}
}
}
for (size_t i = 0; i < maps.size(); i++)
{
for (size_t j = 0; j < maps[i].size(); j++)
{
if (Visited[i][j] == 'Y')
{
int Add = maps[i][j] - '0';
Visited[i][j] = 'N';
BFS(maps, i, j, Add);
answer.push_back(Add);
}
}
}
if (!answer.empty())
{
sort(answer.begin(), answer.end());
}
else
{
answer.push_back(-1);
}
return answer;
}
카카오 문제는 언제나 지문이 길지만, 막상 까보면 그냥 구현 문제이다. 지금까지 풀어왔던 카카오 문제와 유사한데, 정보가 긴 문자열(로그)로 주어지고, 그 로그의 정보를 해석하여 문제를 푸는 형식이다. 제한은 넉넉하다.
본인은 그냥 악보의 #을 따로 처리하기 번거로워서, 그냥 악보를 받고 먼저 보기 편한 방식으로 바꿔줬다(SheetMusic() 이후 ConvertSheetMusic()). 이후 반복문을 돌면서, 총 재생 시간은 몇 분인지, 노래 제목은 뭔지, 악보 구성은 어떻게 되어있는지 확인하고 검사 전 재생시간만큼 악보로 연주(?)를 해준다. 그러면 최종 검사 악보가 나오는데, 여기서 그냥 Find를 해주면 된다. -1 검사를 해도 되고 npos 검사를 실시해도 된다. 마지막으로 재생 시간이 더 길거나, 동일한 경우에는 앞서 재생된 노래를 return하기 위해 MaxPlayTime으로 조건을 판별해준다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<string, string> SheetMusicTable;
void SheetMusic()
{
SheetMusicTable["C"] = "A";
SheetMusicTable["C#"] = "B";
SheetMusicTable["D"] = "C";
SheetMusicTable["D#"] = "D";
SheetMusicTable["E"] = "E";
SheetMusicTable["F"] = "F";
SheetMusicTable["F#"] = "G";
SheetMusicTable["G"] = "H";
SheetMusicTable["G#"] = "I";
SheetMusicTable["A"] = "J";
SheetMusicTable["A#"] = "K";
SheetMusicTable["B"] = "L";
}
string ConvertSheetMusic(const string& _Input)
{
string Result;
for (size_t i = 0; i < _Input.length();)
{
string Note;
if (i + 1 < _Input.length() && _Input[i + 1] == '#')
{
Note = _Input.substr(i, 2); // e.g., C#
i += 2;
}
else
{
Note = _Input.substr(i, 1); // e.g., C
i += 1;
}
auto it = SheetMusicTable.find(Note);
if (it != SheetMusicTable.end())
{
Result += it->second;
}
else
{
Result += "?"; // Unknown note
}
}
return Result;
}
string CreateSheetMusic(int _Miin, const string& _Score)
{
string SheetMusic = "";
int MaxIndex = _Score.size() - 1;
int CurIndex = 0;
while (_Miin--)
{
if (CurIndex > MaxIndex)
{
CurIndex = 0;
}
SheetMusic += _Score[CurIndex++];
}
return SheetMusic;
}
int MinuteCalculation(const string& _Start, const string& _End)
{
string Start = _Start;
string End = _End;
int StartMin = (stoi(Start.substr(0, 2)) * 60) + stoi(Start.substr(3, 2));
int EndMin = (stoi(End.substr(0, 2)) * 60) + stoi(End.substr(3, 2));
return EndMin - StartMin;
}
// [1] 음악 제목 [2] 재생이 시작되고 끝난 시각 [3] 악보
// C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개
string solution(string m, vector<string> musicinfos)
{
string answer = "(None)";
SheetMusic();
string Newm = ConvertSheetMusic(m);
int MaxPlayTime = -1; // 현재까지의 최장 재생 시간
for (size_t i = 0; i < musicinfos.size(); i++)
{
string CurStr = musicinfos[i];
int Min = MinuteCalculation(CurStr.substr(0, 5), CurStr.substr(6, 5));
string Title = "";
string Score = "";
bool IsFirst = false;
for (size_t j = 12; j < CurStr.size(); j++)
{
char temp = CurStr[j];
if (temp != ',' && IsFirst == false)
{
Title += temp;
}
else if (temp == ',')
{
IsFirst = true;
continue;
}
else
{
Score += temp;
}
}
string NewScore = ConvertSheetMusic(Score);
string Music = CreateSheetMusic(Min, NewScore);
if (Music.find(Newm) != -1)
{
if (Min > MaxPlayTime)
{
MaxPlayTime = Min;
answer = Title;
}
}
}
return answer;
}
기본적인 구조는 DFS와 비슷하지만, 한 칸씩 이동하는 방식과 다르게 정해진 방향으로 쭉 이동해야합니다(인덱스 범위 내 or 다음 구역이 D가 아닌 경우). 이후 이동한 구역에 대해서는 현재까지의 이동 횟수(Count)를 기록합니다. 나중에 다시 돌아왔을 때 현재 Count보다 기록된 Count가 낮다면 해당 구역에서는 DFS를 다시 할 필요가 없기 때문입니다(이미 다른 구역을 모두 탐색한 곳이기 때문). 이런 식으로 이동하면서, 도달 가능한 방식을 찾고 그 중 가장 낮은 값을 리턴해줍니다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> Visited;
int LimitY = 0;
int LimitX = 0;
int CheckY[4] = {-1, 0, 1, 0};
int CheckX[4] = {0, 1, 0, -1};
int answer = INT32_MAX;
bool bIsFound = false;
void DFS(vector<string>& _board, int _StartY, int _StartX, int _Count)
{
Visited[_StartY][_StartX] = _Count;
// 위, 오른쪽, 아래, 왼쪽으로 진행 가능한지 체크
// 진행이 불가능한 경우(이동 후 위치가 나와 동일한 경우)에는 실패 체크
// 위에 반복
for (size_t i = 0; i < 4; i++)
{
int TempY = _StartY;
int TempX = _StartX;
while (true)
{
TempY += CheckY[i];
TempX += CheckX[i];
if (TempY >= LimitY || TempY < 0 || TempX >= LimitX || TempX < 0) // 상하좌우가 이동 불가능한지 체크
{
TempY -= CheckY[i];
TempX -= CheckX[i];
break;
}
if (_board[TempY][TempX] == 'D')
{
TempY -= CheckY[i];
TempX -= CheckX[i];
break;
}
}
if (Visited[TempY][TempX] <= _Count)
{
continue;
}
else if (_board[TempY][TempX] == 'G')
{
// 찾음
bIsFound = true;
answer = min(_Count, answer);
}
else
{
DFS(_board, TempY, TempX, _Count + 1);
}
}
}
int solution(vector<string> board)
{
int StartY = 0, StartX = 0;
LimitY = board.size(); // 인덱스는 얘보다 -1 // 5
LimitX = board[0].size(); // 인덱스는 얘보다 -1 // 7
Visited.resize(board.size(), vector<int>(board[0].size(), INT32_MAX));
// 원래 위치로 돌아오는 경우에는 폐기
for (size_t y = 0; y < board.size(); y++)
{
for (size_t x = 0; x < board[y].size(); x++)
{
char CurDot = board[y][x];
if ('R' == CurDot)
{
StartY = static_cast<int>(y);
StartX = static_cast<int>(x);
}
}
}
int Count = 1;
DFS(board, StartY, StartX, Count);
if (bIsFound == false)
{
answer = -1;
}
return answer;
}
가끔 보면 문제를 보자마자 힌트가 보이는 것들이 있습니다. 해당 문제가 그런데, orders의 크기(갯수)와 각 요소마다의 문자열 길이를 보면 이런 문제는 그냥 완전 탐색을 진행해도 됩니다.
근데 문제가 course를 선택해서 가장 많은 조합을 도출하라고 했으니, 아예 다 돌 필요는 없습니다. 일단 모든 orders를 취합해서 문자열들(메뉴들)이 뭐가 있는지를 파악합니다. 이후 이 문자열들에서 course 갯수만큼 추출해서 모든 요소들을 검사하고, 이 조합을 선택하는 orders가 몇개인지 파악합니다. 예를 들어 AB를 탐색하기로 했으면 ABCFG에서 AB가 있는지 없는지, AC에서 AB가 있는지 없는지를 파악하는 것입니다.
이렇게 2개 조합일 때, 3개 조합일 때, 4개 조합일 때 모두 파악한 뒤 가장 많은 선택을 받았던 조합을 answer에 담고 오름차순 정렬해준 뒤 return 해줍니다.
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
using namespace std;
// 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성
// 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함
// orders.size() : 2 이상 20 이하
// orders[i] : 2 이상 10 이하인 문자열, 대문자로만, 같은 알파벳이 중복해서 들어있지 않습니다
// course.size() : 1 이상 10 이하
// course[i] : 2 이상 10 이하인 자연수가 오름차순으로 정렬
// 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return
// 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return
vector<string> solution(vector<string> orders, vector<int> course)
{
vector<string> answer;
map<char, int> Map;
vector<char> Menus;
for (size_t i = 0; i < orders.size(); i++)
{
for (size_t j = 0; j < orders[i].size(); j++)
{
char CurMenu = orders[i][j];
if (Map.find(CurMenu) == Map.end())
{
Map.insert(make_pair(CurMenu, 1));
Menus.push_back(CurMenu);
}
}
}
sort(Menus.begin(), Menus.end());
// 원하는 조합 개수에 대해 순회
for (int c : course)
{
unordered_map<string, int> CombCount;
int MaxCount = 0;
for (const string& order : orders)
{
if (order.size() < c) continue;
string SortedOrder = order;
sort(SortedOrder.begin(), SortedOrder.end());
vector<bool> Select(SortedOrder.size(), false);
fill(Select.end() - c, Select.end(), true);
do
{
string Comb;
for (int i = 0; i < SortedOrder.size(); ++i)
{
if (Select[i])
Comb += SortedOrder[i];
}
CombCount[Comb]++;
MaxCount = max(MaxCount, CombCount[Comb]);
} while (next_permutation(Select.begin(), Select.end()));
}
// 가장 많이 등장한 조합만 answer에 추가
for (const auto& it : CombCount)
{
const string& comb = it.first;
int count = it.second;
if (count >= 2 && count == MaxCount)
{
answer.push_back(comb);
}
}
}
sort(answer.begin(), answer.end());
return answer;
}
스카이박스에서 큐브맵을 로드하여 활용해봤습니다. 큐브맵을 여기서만 쓰는게 아니고, 리플렉션 프로브를 위해 사용할 수도 있습니다. 리플렉션 프로브는 3D 실시간 렌더링에서 간접 반사를 구현하기 위한 기술로, 오브젝트 표면에 환경이 반사되는 것처럼 보이게 만드는 데 사용됩니다.
실시간 반사는 성능 부담이 크기 때문에, 리플렉션 프로브를 활용하여 특정 위치의 반사 환경을 미리 저장해두고, 주변 오브젝트에 이 큐브맵을 적용하여 효율적으로 간접 반사를 구현할 수 있습니다.
기존의 RTV, SRV를 만들던 것과 차이가 있다면, MiscFlags 값을 D3D11_RESOURCE_MISC_TEXTURECUBE로 지정해주는 것과 아래와 같이 D3D11_SUBRESOURCE_DATA에 값을 6번 넣어주고, 그걸로 Textrue2D를 Create()하는 것 정도 아닐까 싶습니다.
SkyBox는 기존에 렌더러들을 출력해주는 RenderTarget에 그리지 않고, 따로 RenderTarget을 만들어 거기에 먼저 그려둔 뒤, 나중에 최종 RenderTarget(CameraRenderTarget)에 Blending 했습니다. 먼저 Material Setting입니다.
