SRM151 DIV2
허프만 트리에 대한 개념을 알고 있어서 그런지 문제이해가 빨랐던 문제..
#define pb push_back
using namespace std;
class PrefixCode
{
public:
string isOne(vector <string> words)
{
string ret;
string w;
int find_index = -1;
for(int i=0; i< words.size() && find_index == -1; i++)
{
w = words[i];
for(int j=0; j< words.size() && find_index == -1; j++)
{
if(i == j) continue;
for(int length=1; length <= words[j].size() && find_index == -1; length++)
{
if(words[j].compare(0, length, w) == 0 )
{
find_index = i;
break;
}
}
}
}
stringstream buf;
buf << find_index;
if(find_index == -1)
ret = "Yes";
else
ret = "No, "+ buf.str();
return ret;
}
};
SRM152 DIV2
: 지문이 꽤 길어서 문제파악이 어려웠던 문제;;
#define pb push_back
using namespace std;
class FixedPointTheorem
{
public:
double cycleRange(double R)
{
double maxVal = 0;
double minVal = INT_MAX;
double X=.25;
for(int i=0; i<200000; i++)
{
X = R * X * (1-X);
}
for(int i=0; i< 1000; i++)
{
X = R * X * (1-X);
maxVal = max(maxVal, X);
minVal = min(minVal, X);
}
double ret = maxVal - minVal;
return ret;
}
};
SRM153 DIV2
: 문제 내용도 쉽고..풀이도 간단했던 문제..
typedef long long LL;
#define pb push_back
using namespace std;
class MostProfitable
{
public:
string bestItem(vector <int> costs, vector <int> prices, vector <int> sales, vector <string> items)
{
int profit = 0;
int max_profit = 0;
string ret;
for(int i=0; i<costs.size(); i++)
{
profit = (prices[i] - costs[i]) * sales[i];
if(profit < 0) continue;
if(profit > max_profit)
{
max_profit = profit;
ret = items[i];
}
}
return ret;
}
};
SRM154 DIV2
: substring으로 double형 데이터를 만들수 있으면 막힐게 없는 문제.
일부 유저들을 보니 string각 자리수에 10*n을 곱해서 double을 만들기도 했다.
미리만들어놓은 toInt함수를 조금 변형해서 적용해서 빨리 푼 문제..
class ProfitCalculator
{
public:
double toDouble(string s)
{
stringstream s1(s);
double t;
s1 >> t;
return t;
}
int percent(vector <string> items)
{
int ret = 0;
double price = 0;
double cost = 0;
double margin = 0;
for(int i=0; i<items.size(); i++)
{
price += toDouble(items[i].substr(0, 6));
cost += toDouble(items[i].substr(7, 6));
}
margin = (price - cost) / price * 100;
ret = (int)margin;
return ret;
}
};
SRM155 DIV2
: 나름 평이한 문제.
미리 만들어놓은 toInt, toStr을 꽤나 유용하게 사용한 문제다.
이게 없었다면, 10자리마다 10을 곱해서 주는 등 Readablity가 떨어지는 알고리즘을 고안해야 했을 문제..
성능측면으로 봤을때는 물론, 이렇게 string으로 갔다가 int로 변환보다는 로직으로 답을 구하는게 나을듯.
class Quipu
{
public:
int toInt(string s)
{
stringstream s1(s);
int t;
s1 >> t;
return t;
}
string toStr(int num)
{
stringstream s;
s << num;
return s.str();
}
int readKnots(string k)
{
int ret = 0;
string result;
int cnt = 0;
for(int i=1; i< k.size(); i++)
{
cnt = 0;
if(k[i] == '-')
{
result += '0';
continue;
}
while(k[i] == 'X')
{
cnt++;
i++;
}
result += toStr(cnt);
}
ret = toInt(result);
return ret;
}
};
SRM156 DIV2
: DIV2 에 전형적으로 나오는 유형같다. 총 cost를 구한후 몇개에 담을 수 있는지 묻는 문제
sort순서를 큰것부터 소트하는 방법을 몰라서, for문을 큰 수부터 돌렸는데..
다른사람들 짠거 보니 sort할때 greater<int>() 를 세번째 인자로 줘서 sort하더라.
그걸 모르면 sort한 후에 reverse를 한번 호출해 준다던가.
0 등 바운드값에 대한 고려가 안되면, 다 풀고도 틀릴 수 있는 문제.
class DiskSpace
{
public:
int minDrives(vector <int> used, vector <int> total)
{
int ret = 0;
int total_use = 0;
for(int i=0; i< used.size(); i++)
total_use += used[i];
sort(total.begin(), total.end());
for(int i=total.size()-1; i >= 0; i--)
{
total_use -= total[i];
ret++;
if(total_use <= 0 ) break;
}
return ret;
}
};
SRM157 DIV2
: 난이도가 낮은 평이한 문제..
class GuessTheNumber
{
public:
int noGuesses(int u, int answer)
{
int ret = 1;
int lower = 1;
int upper = u;
int middle = (lower + upper) / 2;
while(middle != answer)
{
if(middle < answer)
{
lower = middle + 1;
}
else
{
upper = middle - 1;
}
middle = (lower + upper) / 2;
ret++;
if(ret > 10) break;
}
return ret;
}
};
SRM158 DIV2
: 난이도는 평이한 문제.
C를 하던 습관때문인지, 나는 여전히 sprintf류의 함수를 자주 쓰는거 같다.
아래와 같이 동일 크기 string을 하나 만들어서, 비교하는 방식으로 푸는게 나을듯함..
string s = initial;
s[0] = initial[3];s[1] = initial[2];s[2] = initial[0];s[3] = initial[1];
class TireRotation
{
public:
int getCycle(string initial, string current)
{
char t1 = initial[0];
char t2 = initial[1];
char t3 = initial[2];
char t4 = initial[3];
if(initial == current) return 1;
char buf[5];
sprintf(buf, "%c%c%c%c", t4, t3, t1, t2);
if(string(buf) == current) return 2;
sprintf(buf, "%c%c%c%c", t2, t1, t4, t3);
if(string(buf) == current) return 3;
sprintf(buf, "%c%c%c%c", t3, t4, t2, t1);
if(string(buf) == current) return 4;
return -1;
}
};