Ex) Level0 - 소인수분해 [X]
두 개의 풀이를 진행해보았으나, 둘다 100점이 아님.
문제점을 못 찾겠어서 일단 스킵.
<hide/>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
// 1번 풀이
for (int i = 2; i <= n; ++i)
{
if (n % i == 0)
{
answer.push_back(i);
n /= i;
}
}
return answer;
}<hide/>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(int n) {
vector<int> answer;
// 2번 풀이
vector<int> vDivisors;
for (int i = 1; i * i <= n; ++i)
{
if (n % i == 0)
{
vDivisors.push_back(i);
vDivisors.push_back(n / i);
}
}
size_t uSizeOfDivisors = vDivisors.size();
for (size_t i = 0; i < uSizeOfDivisors; ++i)
{
bool IsPrime = true;
for (int j = 2; j < vDivisors[i]; ++j)
{
if (vDivisors[i] % j == 0)
{
IsPrime = false;
}
}
if (true == IsPrime && 1 != vDivisors[i])
{
answer.push_back(vDivisors[i]);
}
}
sort(answer.begin(), answer.end());
return answer;
}
Ex) Level0 - 영어가 싫어요
map 초기화 방법을 자꾸 까먹음.
<hide/>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define COMMON_OFFSET (3)
long long solution(string numbers) {
long long answer = 0;
map<string, int> mStrToInt = { {"zer", 0}, {"one", 1}, {"two", 2},{"thr", 3},{"fou", 4},{"fiv", 5},{"six", 6},{"sev", 7},{"eig", 8},{"nin", 9}};
map<string, int> mStrToOffset = { {"zer", 1}, {"one", 0}, {"two", 0},{"thr", 2},{"fou", 1},{"fiv", 1},{"six", 0},{"sev", 2},{"eig", 2},{"nin", 1}};
size_t uSizeOfNumbers = numbers.size();
for (size_t i = 0; i < uSizeOfNumbers;)
{
string strNumber = "";
for (size_t j = i; j < i + COMMON_OFFSET; ++j)
{
strNumber += numbers[j];
}
answer = answer * 10 + mStrToInt[strNumber];
i += COMMON_OFFSET + mStrToOffset[strNumber];
}
return answer;
}
Ex) Level0 - 잘라서 배열로 저장하기
<hide/>
#include <string>
#include <vector>
using namespace std;
vector<string> solution(string my_str, int n) {
vector<string> answer;
int iSizeOfMyStr = static_cast<int>(my_str.size());
int iLine = iSizeOfMyStr / n;
for (int i = 0; i < iLine; ++i)
{
answer.push_back(my_str.substr(i * n, n));
}
int iRemain = iSizeOfMyStr % n;
if (0 != iRemain)
{
answer.push_back(my_str.substr(iLine * n));
}
return answer;
}
Ex) Level0 - 문자열 계산하기
<hide/>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
int solution(string my_string) {
int answer = 0;
stringstream ss;
ss.str(my_string);
int iOperand;
char chOperator;
ss >> answer;
while (false == ss.eof())
{
ss >> chOperator;
ss >> iOperand;
switch (chOperator)
{
case '+':
answer += iOperand;
break;
case '-':
answer -= iOperand;
break;
default:
break;
}
}
return answer;
}
Ex) Level0 - 구슬을 나누는 경우의 수
구슬은 모두 다르게 생겼습니다. -> 중복이 없다. -> 순열 or 조합
구슬을 고르는 순서는 고려하지 않습니다 -> 조합
<hide/>
#include <string>
#include <vector>
using namespace std;
void Combination(int _iCurrentN, int _iN, int _iCurrentR, int _iR, int& _iAnswer, vector<bool>& _vbVisit)
{
if (_iCurrentR == _iR)
{
++_iAnswer;
return;
}
else
{
for (int i = _iCurrentN; i < _iN; ++i)
{
if (true == _vbVisit[i])
{
continue;
}
_vbVisit[i] = true;
Combination(i, _iN, _iCurrentR + 1, _iR, _iAnswer, _vbVisit);
_vbVisit[i] = false;
}
}
}
int solution(int balls, int share) {
int answer = 0;
vector<bool> vbVisit;
vbVisit.resize(balls + 1, false);
Combination(0, balls, 0, share, answer, vbVisit);
return answer;
}
Ex) Level0 - 컨트롤 제트
스택을 이용해서 Z가 나오면 Pop을 함. 다 끝난후엔 empty까지 총합.
<hide/>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
enum { STACK_SIZE = 201, INVALID = -1};
class Stack
{
public:
Stack()
: m_arriData{ 0, }
, m_uTop(0u)
{
}
void Push(int _iData)
{
if (STACK_SIZE - 1 <= m_uTop)
{
// Stack overflow.
}
else
{
m_arriData[++m_uTop] = _iData;
}
}
bool Empty()
{
return 0u == m_uTop;
}
int Pop()
{
if (true == Empty())
{
// Stack underflow.
return INVALID;
}
else
{
return m_arriData[m_uTop--];
}
}
public:
int m_arriData[STACK_SIZE];
size_t m_uTop;
};
int solution(string s) {
int answer = 0;
Stack st;
stringstream ss;
ss.str(s);
while (false == ss.eof())
{
string strInput;
ss >> strInput;
if ("Z" != strInput)
{
st.Push(stoi(strInput));
}
else
{
st.Pop();
}
}
while (false == st.Empty())
{
answer += st.Pop();
}
return answer;
}
Ex) Level0 - 외계어 사전
spell에 담긴 알파벳을 한 번씩만 모두 사용한 단어 -> 중복 없음 -> 순열 or 조합
순서가 중요함. -> 순열
크래프톤에서 비슷한 문제가 마지막문제로 나왔었는데..... 인생...
<hide/>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void Permutation(int _iN, int _iCurrentR, int _iR, vector<string>& _vstrSpell, vector<string>& _vstrDic, string& _strResult, int& _iAnswer, vector<bool>& _vbVisit)
{
if (_iCurrentR == _iR)
{
if (_vstrDic.end() != find(_vstrDic.begin(), _vstrDic.end(), _strResult))
{
_iAnswer = 1;
}
return;
}
else
{
for (int i = 0; i < _iN; ++i)
{
if (true == _vbVisit[i])
{
continue;
}
_vbVisit[i] = true;
_strResult.replace(_iCurrentR, 1, _vstrSpell[i]);
Permutation(_iN, _iCurrentR + 1, _iR, _vstrSpell, _vstrDic, _strResult, _iAnswer, _vbVisit);
_vbVisit[i] = false;
}
}
}
int solution(vector<string> spell, vector<string> dic) {
int answer = 2;
int iN = static_cast<int>(spell.size());
int iR = iN;
string strResult = "";
vector<bool> vbVisit;
vbVisit.resize(iN + 1, false);
Permutation(iN, 0, iR, spell, dic, strResult, answer, vbVisit);
return answer;
}
Ex) Level0 - 종이 자르기 [X]
재귀함수. 트리형태로 뻗어나가면 될듯.
그러나, N과 M의 크기가 예사롭지 않음. 메모이제이션 필요.
30분 넘게 걸려서 포기하고 다음에 풀기로. 배열 참조와 memset()을 활용해봄.
<hide/>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
enum { MEMOIZATION_SIZE = 101, INVALID = -1 };
int Recursive(int _iM, int _iN, int (&Memo)[MEMOIZATION_SIZE][MEMOIZATION_SIZE])
{
if (INVALID != Memo[_iM][_iN])
{
return Memo[_iM][_iN];
}
if (0 == _iM || 0 == _iN)
{
return Memo[_iM][_iN] = 0;
}
if (1 == _iM && 1 == _iN)
{
return Memo[_iM][_iN] = 0;
}
else if ((2 == _iM && 1 == _iN) || (1 == _iM && 2 == _iN))
{
return Memo[_iM][_iN] = 1;
}
else if ((2 == _iM && 2 == _iN))
{
return Memo[_iM][_iN] = 3;
}
return Memo[_iM][_iN] = (Recursive(_iM - 1, _iN, Memo) + Recursive(_iM, _iN - 1, Memo));
}
int solution(int M, int N) {
int Memoization[MEMOIZATION_SIZE][MEMOIZATION_SIZE];
memset(Memoization, INVALID, sizeof(Memoization));
int answer = Recursive(M, N, Memoization);
return answer;
}
댓글