22.05.14. 풀었던 문제들

1. 가장 긴 팰린드롬

내가 작성한 코드의 문제점을 찾았다. 나는 index i부터 index j까지 palindrome인지 검사하는 식으로 잡았는데, 이러면 2중 for문 + palindrome 검사문의 시간이 O(s.length())이므로 총 합해서 O(n^3)으로 풀고 있었던 것이다.

그래서 좀 더 효율적인 방법을 생각했다. 첫 번째 for문은 검색 index의 중간점을 두고, i에 따라 좌우로 검색할 수 있는 string max 길이를 계산한다. 그리고 짝수/홀수인 경우에 따라 string length를 1칸씩 늘려가면서 검사한다. string length가 1일 때는 무조건 팰린드롬, 2 이상일 때는 문자가 같은지 검색해 나가야 하는데, 기존 검색되어 있는 내용을 이용하는 것이다.

// 가장 긴 팰린드롬

int solution(string s)
{
    int answer = 1, len = s.length();
    
    // i : string 중간점
    for(int i = 1; i<len-1; i++){
        // palin이 홀수
        int maxlen = min(i, len-i-1);
        for(int ilen = 1; ilen<=maxlen; ilen++){
            if(s[i - ilen] != s[i + ilen]){
                break;
            }
            answer = max(answer, 2*ilen + 1);
        }
        // palin이 짝수
        for(int ilen = 0; ilen <= maxlen+1; ilen++){
            if(s[i-ilen] != s[i + ilen-1]){ // ilen이 0이면 i랑 그 앞에것 비교
                break;
            }
            answer = max(answer, 2*ilen);
        }
    }
   
    
    return answer;
}

 

 

2. 공 이동 시뮬레이션

머리 깨지는 줄 알았다. 일단 처음 접근을 - 'target으로부터 역추적'은 잘 잡았는데 이게 좀 많이 헷갈렸다.

단순히 생각해서 x축으로만 움직인다고 생각하자.

그러면 query가 오른쪽으로 움직인다고 했으면 - target으로부터 왼쪽으로 움직이면 되고, query가 왼쪽으로 움직인다고 했으면 - target으로부터 오른쪽으로 움직이면 된다. 그러나 신경 쓸 것은

1) 제일 가에 있어서 해당 query가 씹히는 경우

예를 들어 0, 4인 수직선에서 target이 4에 있는 상태. 여기서는 오른쪽으로 가 봤자 위치는 계속 4이며, 그쪽으로 갈 수 있는 경우의 범위가 늘어난다. 예를 들어 현 추적 위치가 4인데 query가 오른쪽으로 2칸이면 2, 3, 4인 위치에서 오른쪽으로 2칸 옮기면 이 모든 경우, 옮긴 위치가 4가 되기 때문이다. 따라서 추적 위치는 2, 3, 4로 늘어난다.

2) 예외처리 - 해당 위치로 갈 수 없는 경우

예를 들어 0, 4인 수직선에서 target이 4에 있는 상태에서 query가 왼쪽으로 간다고 생각하자. 수직선 사이즈가 1이 아닌 이상 왼쪽으로 1칸 옮겨서 4로 갈 수 없다. 이 경우 예외처리를 해 주어야 한다.

3) start와 end 지점

수직과 수평으로만 움직이고, 경우의 수가 늘어나며, 각각의 경우의 수에 대해 경우의 수가 늘어난다. 따라서 start와 end 지점을 잡아야 할 필요가 있다.

// 공 이동 시뮬레이션

#include <string>
#include <vector>
#include <iostream>

using namespace std;

// 원래 direction
int dr[4] = {0, 0, -1, 1};
int dc[4] = {-1, 1, 0, 0};

typedef pair<int, int> pii;
typedef long long ll;

int handle(int value, int max){
    if(value < 0) return 0;
    if(value >= max) return max-1;
    return value;
}

long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
    int size = queries.size();
    ll rs = x, re = x, cs = y, ce = y;
    for(int i = size-1; i>=0; i--){
        int dir = queries[i][0], space = queries[i][1];
        if(dir == 2){ // up
            if(rs == 0){ // 끝점이면 탐색 지점 늘려줌
                re += space;  
            } else{ // 끝점 아니면 line을 옮김
                rs += space;
                re += space;
            }
            re = handle(re, n); // rs가 n을 넘어가면 해당 칸으로 갈 수 없다
        } else if(dir == 3){ // down
            if(re == n-1){
                rs -= space;
            } else{
                rs -= space;
                re -= space;
            }
            rs = handle(rs, n);
        } else if(dir == 0){ // left
            if(cs == 0){
                ce += space;
            } else{
                cs += space;
                ce += space;
            }
            ce = handle(ce, m);
        }else{ // right
            if(ce == m-1){
                cs -= space;
            } else{
                cs -= space;
                ce -= space;
            }
            cs = handle(cs, m);
        }
        if(rs > n-1 || re < 0 || cs > m-1 || ce < 0) return 0;
        // 이런 반례 : 2 by 2에서 target이 (0, 1)이고 query가 left로만 가는 경우 -> 역추적하면 cs가 오른쪽으로 넘어감
    }

    return (ce - cs + 1) * (re - rs + 1);
}