softeer : 비밀메뉴2

https://softeer.ai/class/devcrew/study/resource/detail/description/6259?id=280&resourceId=328

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

오늘도 열심히 삽질끝에 3일만에 해결했다!!!ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

비밀메뉴1을 string의 find(contain)을 이용해서 풀었던 기억을 바탕으로 해결하려 했지만... 못했다!!

일단 k의 범위가 늘어나서 냅다 수열을 string으로 보고 풀면 안되었고

    (10 22 33 이랑 10 2 2 3 3 이랑... string으로 만들면 똑같음)

뭔가,,, 이유가 있지 않을까?? 길이면에서 그런가?

n하고 m의 범위가 작지만 k의 범위가 늘어나서 이걸 연결해서 string하나로 보면 엄청엄청 길어질것같긴하다!

 

아무튼 그래서 이게뭔가,,, 했는데 LCS로 해결하는 문제였다

https://usowelcome.tistory.com/116

LCS : Longest common subsequence / substring

작년에 알고리즘 수업 dp파트에서 배웠던 기억이 있는데,,,

완전 까먹고 있었다!!ㅋㅋㅋㅋ

아무튼 이번기회에 복습할 수 있었으니 오히려조아~~~ 럭키취준생이잔앙

 

그냥 LCS를 그대로 구현하면 되는 문제였다ㅎㅎㅎㅎ

다만 sequence가 아니라 string으로 봐야했을뿐!! (연속되어야 하니까)

 

#include<iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;


int n, m, k;

int main(int argc, char** argv)
{
    cin >> n >> m >> k;
    vector<int> str1;
    vector<int> str2;
    for(int i = 0; i<n; i++){
        int temp;
        cin >> temp;
        str1.push_back(temp);
    }
    for(int i = 0; i<m; i++){
        int temp;
        cin >> temp;
        str2.push_back(temp);
    }

    vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); //[i][j]     index 1부터 시작하도록
                  // i : str1
                   // j : str2

    int answer = 0;

    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=m; j++){
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }else{
                dp[i][j] = 0;
            }
            answer = max(answer, dp[i][j]);
        }
    }


    cout << answer;
    
   return 0;
}

 

answer같은 경우는 dp를 완성하고 마지막에 구할 수 있었지만

난 그냥 저렇게 같이 구하고싶었당ㅎ

 

그리고 이렇게 길이숫자만 필요하다면...

dp배열을 저렇게 n*m 전체를 할게 아니라, 2*m으로 해서 당장 필요한 두줄만 써서 공간절약을 할 수도 있을것이다!

 

아무튼... 해결했으니까 다행이야~~