Softeer 대회 예선 1번문제, 비밀메뉴 cpp 문제풀이

 

 

안녕하세요. 오늘은 Softeer 최근 대회 예선문제인 1번문제, 비밀메뉴의 cpp문제풀이를 기록해보겠습니다.

해당 문제는 예선 1번문제로 쉬운편에 속하는 문제였는데요. O(N)의 시간복잡도로 풀 수 있는 문제일것 같은데, 제가 제출한 O(N) 시간복잡도 코드가 테스트케이스 1개가 계속 틀려서... 이번 포스팅에서는 O(N*M) 복잡도의 풀이를 공유해보겠습니다.

 

 

---

Softeer 대회 예선문제, 비밀메뉴 문제 개요

Softeer

비밀메뉴 문제의 세부 내용은 위 링크를 참고하세요. 최근 열었던 Softeer 대회 예선 1번 문제였다고 합니다.

 

 

 

 

문제 내용을 요약하자면, 비밀 메뉴에 대한 조작법, 자판기를 조작한 과정이 입력으로 들어왔을때 자판기 조작 간에 비밀 메뉴 조작법이 들어있으면 "secret", 비밀 메뉴 조작법이 없었다면, "normal"을 출력하면 되는 문제입니다.

 

 

 

 

K는 입력받는 번호 숫자의 범위, M은 비밀메뉴의 길이, N은 자판기 조작 횟수입니다. 이후 두번째 줄에는 비밀메뉴를 얻기 위한 조작 번호, 세번째 줄에는 자판기 조작 번호가 차례대로 주어지고, 자판기 조작 간에 입력한 번호가 비밀메뉴 조작법과 매칭이 되는 경우가 있다면 "secret"을 출력하면 됩니다. 

이어서 O(N*M) 시간복잡도 풀이를 해설해보겠습니다.

 

 

 

---

Softeer 대회 예선문제, 비밀메뉴 cpp 문제풀이

cpp 표출입출력을 받기 위해, vector자료구조를 사용하기 위해 헤더를 추가하고, M, N, K를 차례로 입력받습니다. 
secret에는 비밀메뉴를 얻기 위한 번호 순서를 저장합니다. G에는 자판기 번호를 누른 순서를 저장하는데, 길이는 N이 됩니다. now는 현재까지 비밀메뉴와 메칭된 번호가 들어가며 비밀메뉴 매칭 여부 체크에 사용합니다. 

이후 secret, G에 M, N만큼의 숫자를 차례로 입력받습니다. good에는 비밀메뉴 포함여부를 기록합니다.

 

 

 

 

자판기를 눌렀던 시점이 0 ~ N-1일때 까지를 순회하면서 i번째 부터 M번 눌렀을때 비밀메뉴를 눌렀는지를 체크합니다. 만약 비밀메뉴와 맞지 않는 번호가 들어간다면, test에 false를 저장하며, i를 증가시켜 다음 경우의 수를 체크합니다. 만약 비밀메뉴와 동일한 순서의 번호가 입력되면, test는 true값을 유지한 채로, 아래 if(test) 조건문을 타게 됩니다. 비밀메뉴 조작법이 들어있었으므로 이 경우에는 good을 true로 저장하고 for문을 바로 탈출합니다.

 

 

 

 

결과적으로 good이 true면 "secret"을, false면 "normal"을 출력하게 됩니다. 이렇게 O(N*M)의 시간복잡도로 문제를 풀 수 있었고,

 

 

 

---

Softeer에서 제출을 할때에도 통과가 되었지만, 더 효율적으로 풀 수 있었던것 같은 문제라 아쉽네요. O(N)의 시간복잡도 풀어보신분 계시면 언제든 댓글 달아주세요. 저는 O(N) 문제풀이로 테스트케이스 1개가 틀렸는데 반례를 못찾은 상태네요.(짜증...) 

다시한번 의견이나 지적 환영합니다. 즐거운 코딩 되시길 바라며, 다음 포스팅에서 뵙겠습니다. ㅂㅇ~ 
+ 아래에 전체 소스코드 공유합니다.

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

int main(int argc, char** argv)
{
    int M, N, K; cin>>M>>N>>K;
    vector<int> secret(M, 0);
    vector<int> G(N, 0);
    vector<int> now;
    for(int i=0; i<M; i++) cin>>secret[i];
    for(int i=0; i<N; i++) cin>>G[i];
    bool good = false;

    for(int i=0; i<N; i++) {
        if(G.size() <= i+M-1) break;
        bool test = true;
        int k=0;
        for(int j=i; j<i+M; j++) {
            if(secret[k] != G[j]) {
                test = false;
                break;
            }
            k++;
        }
        if(test) {
            good = true;
            break;
        }
    }

    printf("%s", good ? "secret" : "normal");

    return 0;
}