23.07.29. 풀었던 문제들 복기
백준 14906 스러피 : 50분
사실상 regular expression을 구현하는 문제인데, regular expression만으로는 구현할 수 없기 때문에 무조건 string parse를 해야 하는 문제이다.
일단 slump와 slimp를 판별하는 것은 간단한데, 문제에서 주어진 조건을 그대로 풀면 된다. 그리고 slump의 경우에는 내부에 slump가 있고, slimp의 경우에는 내부에 slimp나 slump가 있다. 때문에 각 조건을 판별할 때 재귀로 slump인지 slimp인지 판별하기는 쉽다! 귀찮을 뿐이지.
이후, 전체 string은 slimp + slump로 구성되기 때문에 slump의 시작 지점을 잘 잡아야 한다. 그러나 어느 지점에서 시작하기 잡기 까다롭다. slimp 내부에 slump가 있을 수 있기 때문이다. 그래서 입력 string의 D나 E인 부분을 기점으로 좌/우로 쪼개고 (slump의 시작 char), 단 하나라도 slimp + slump 형태인 경우 true를 리턴하게 했다.
*** 실수했던 점은, return으로 YES or NO를 리턴해야 하는데 1 0을 리턴한 것이다. ㅠㅠ
bool isSlump(string s){
if(!(s[0] == 'D' || s[0] == 'E')) return false;
if(s[1] != 'F') return false;
for(int i = 2; i<s.length(); i++){
if(s[i] == 'F') continue; // 연속된 F
if(s[i] == 'D' || s[i] == 'E'){ // 새 slump
return isSlump(s.substr(i));
}
else if(s[i] == 'G'){ // 종료
if(i == s.length()-1) return true;
else return false;
}
else return false;
}
return false;
}
bool isSlimp(string s){
if(s.length() < 2) return false;
if(s[0] != 'A') return false; // 첫 문자
if(s.length() == 2){ // length 2면 AH
if(s[1] == 'H') return true;
else return false;
}
else{
if(s[1] == 'B' && s[s.length()-1] == 'C' && isSlimp(s.substr(2, s.length()-3))) return true;
if(s[s.length()-1] == 'C' && isSlump(s.substr(1, s.length()-2))) return true;
else return false;
}
}
void solve(){
string s; cin>>s;
string result = "NO";
for(int i = 0; i<s.length(); i++){
if(s[i] == 'D' || s[i] == 'E'){
string left = s.substr(0, i), right = s.substr(i);
if(isSlimp(left) && isSlump(right)){
result = "YES";
break;
}
}
}
cout<<result<<'\n';
}
//////////////////////
int main(void) {
cin.tie(0);
cout.tie(0);
std::ios_base::sync_with_stdio(0);
// number of test cases
int t; cin>>t;
cout<<"SLURPYS OUTPUT"<<'\n';
while(t--){
solve();
}
cout<<"END OF OUTPUT"<<'\n';
return 0;
}
시간복잡도
isSlimp(), isSlump()는 O(n)이다. recursion이 들어간다고 해도, T(n) = T(n-2) + c이기 때문이다.
그리고 solve() 함수는 string s의 모든 char를 보고, 좌우로 판별한다. 모든 char를 보는 데 O(n), 각각을 판별하는 데 O(n)이 걸리니 O(n$^2$)이다.
입력에서 N은 60보다 작으므로 충분히 풀 수 있다.
공간복잡도
추가 공간을 사용하지 않는다. 다만 function call stack을 O(n)만큼 사용하므로 O(n)이다.
후기
문제를 잘 읽자. + 실수로 인해 시간이 좀 늦어졌는데, (10분) 최대한 원큐에 풀자.
백준 5702 Jollo : 40분
입력이 작기 때문에 brute force로 풀면 되는 문제.
- 모든 사용 가능한 card에 대해
- 왕자에게 card를 줘 보고,
- princess의 모든 경우와 prince의 모든 경우 (6 * 6)을 대응해 봤을 때
- prince가 이긴다면 왕자는 어떤 경우에도 이긴다.
- 한 번이라도 지면 질 수 있으므로 다음 card를 줘 본다.
이런 로직으로 풀면 된다.
*** 실수했던 점은 6 * 6으로 해야 하는데 조합을 6개만 비교해 버린 것. 마찬가지로 단순 구현 문제이다.
bool canPrinceWin(vector<int> princess, vector<int> prince){
int winCount = 0;
for(int i = 0; i<3; i++){
if(prince[i] > princess[i]) winCount++;
}
if(winCount >= 2) return true;
else return false;
}
void solve(int a, int b, int c, int d, int e){
set<int> deck;
for(int i = 1; i<=52; i++) deck.insert(i);
vector<int> princess(3), prince(3, 0);
princess[0] = a; princess[1] = b; princess[2] = c;
prince[0] = d; prince[1] = e;
for(int c : princess) deck.erase(c);
for(int c : prince) deck.erase(c);
// princess permutation
sort(princess.begin(), princess.end(), less<int>());
vector<vector<int>> princessDecks;
do{
princessDecks.push_back(princess);
}while(next_permutation(princess.begin(), princess.end()));
int allCount = princessDecks.size();
// 제일 낮은 카드 할당할 것임. 이후 모든 경우의 수에서 왕자가 승리하면 그 카드 주면 됨.
for(int card : deck){
prince[0] = d; prince[1] = e; prince[2] = card;
// prince permutation
sort(prince.begin(), prince.end(), less<int>());
vector<vector<int>> princeDecks;
do{
princeDecks.push_back(prince);
}while(next_permutation(prince.begin(), prince.end()));
// 모든 경우 판정에서, 단 하나라도 질 수 있다면 다음 카드로 감.
// 실수 : 6개를 1:1 대응이 아니라 6*6으로 2중for문 돌렸어야 했음.
bool canLose = false;
for(vector<int> princessDeck : princessDecks){
for(vector<int> princeDeck : princeDecks){
if(canPrinceWin(princessDeck, princeDeck) == false){
canLose = true;
break;
}
}
if(canLose == true) break;
}
if(canLose == true) continue;
else{
cout<<card<<'\n';
return;
}
}
// 승리 불가
cout<<"-1\n";
return;
}
//////////////////////
int main(void) {
cin.tie(0);
cout.tie(0);
std::ios_base::sync_with_stdio(0);
int a, b, c, d, e;
while(1){
cin>>a>>b>>c>>d>>e;
if(a + b + c + d + e == 0) break;
solve(a, b, c, d, e);
}
return 0;
}
시간복잡도
card는 52개이므로 대략 O(50)으로 잡고, prince와 princess의 모든 경우의 수는 O(6)이므로 둘의 곱은 O(36)으로 계산할 수 있다. prince와 princess 카드 조합을 비교할 때는 O(3)이다. 그러면 O(50 * 36 * 3) = 대략 O(50000)이다.
공간복잡도
prince, princess card 저장을 위한 공간, local variable만 사용하므로 O(1)
백준 25180 썸 팰린드롬 : 15분
처음에는 brue force로 푸는 문제인지 알았는데, 문제 조건의 N이 10$^9$이기 때문에 절대 그렇게 풀 수 없다. 따라서 규칙을 찾아야만 했다.
- 일단 최소 자리수를 만들기 위해 가능한 모든 자리를 9로 만들고, 이 수의 자리수를 Q라고 하자. - N + 9 > 9Q >= N이다.
- N과 9Q가 같은 경우, 그대로 palindrome (모든 수가 9로 설정할 수 있다.)
- Q가 N보다 큰 경우, 나머지를 R이라고 하자. (9Q - N)
- R을 palindrome 형식으로 배분하면 최소 자리수로 palindrome을 만들 수 있다.
- Q가 짝수면 2개의 숫자에서 하나씩 빼야 palindrome을 만들 수 있다. 따라서 R이 홀수면 Q+1이 답, R이 짝수면 Q가 답.
- Q가 홀수면 가운데 숫자에서 R을 빼면 palindrome을 만들 수 있다. 따라서 Q가 답.
int solve(){
int N; cin>>N;
int Q = N/9 + (N%9 > 0), R = 9*Q - N;
if(Q & 1) return Q;
return Q + (R & 1);
}
시간복잡도
별도 계산이 없다. O(1).