22.05.12. 풀었던 문제들

1. 스티커 모으기(2)

DP문제이다. dp[i]는 i번째 스티커까지 봤을 때 최댓값이라고 두면 점화식은 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])이다. max 함수에서 전자는 i번째 스티커를 떼지 않는 경우이고 후자는 i번째 스티커를 떼는 경우이다. 그리고 이 문제의 경우 0번째 스티커를 떼면 마지막 것을 떼지 못하므로 이에 대한 예외처리도 해 주어야 한다.

​

​

2. 기지국 설치

그냥 풀면 되는 문제.

​

​

3. 스타 수열

꽤 빡셌다. 일단 모든 숫자들이 나온 횟수를 저장하고, 모든 숫자로 brute-force하게 탐색해야 하는 건 맞다. 그러나 조금 최적화가 빡셌다. 마음같아서는 a배열 한번만 탐색하면서 찾는 방법을 찾고 싶은데....

// 스타 수열

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>

using namespace std;

typedef pair<int, int> pii;

bool cmp(pii &a, pii &b){
    return a.second > b.second;
}

int solution(std::vector<int> a) {
    map<int, int> m;
    int size = a.size();
    for(int i : a) m[i]++;
    
    int answer = 0;
    for(pii p : m){
        int value = p.first;
        if(2 * p.second <= answer) continue;
        int max_len = 0;
        for(int j= 0; j<size-1; j++){
            if(a[j] == a[j+1]) continue; // 수가 같은 경우 - 어차피 스타수열이 될 수 없음
            if(a[j] != value && a[j+1] != value) continue; // 두 수 다 스타수열이 아닌 경우 - 스타수열이 될 수 없음
            j++; max_len += 2;
        }
        answer = max(max_len, answer);
    }
    
    return answer;
}

 

4. 가장 긴 팰린드롬

처음 작성했던 코드. 그냥 무작정 때려박았다

 

// 가장 긴 팰린드롬

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPalin(string s){
    int len = s.length(), mid = len / 2; // 4면 2, 5면 2
    string back;
    if(len & 1){
        back = s.substr(mid+1, mid);
    } else{
        back = s.substr(mid, mid);
    }
    reverse(back.begin(), back.end());
    if(s.substr(0, mid) == back) return true;
    else return false;
}

int solution(string s)
{
    int answer = 0;
    int len = s.length();
    // 초기화
    for(int i = 0; i<len; i++){
        for(int j = len-1; j>=0; j--){
            if(j - i + 1 > answer && isPalin(s.substr(i, j - i + 1)))
                answer = max(answer, j-i+1);
        }
    }
    
    

    return answer;
}

// DP였던 것 같은데...
// dp[i][j] : i부터 j까지 max 팰린드롬
// 처음에는 i, i 접근
// 다음에는 i, i+1 접근
// 그 다음에는 i, i+2 접근. i는 row

 

그러나 이렇게 풀면, 팰린드롬을 검사하는 과정에서 s.length()만큼의 시간이 든다. 그러면 2500^3이라 시간 초과가 되는 것 같다. 음... 고민해 보자.