[Softeer] [21년 재직자 대회 예선] 비밀 메뉴

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 비밀메뉴 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        String[] secret = br.readLine().split(" ");
        String[] input = br.readLine().split(" ");
        int index = 0;
        int cnt = 0;

        for(int i = 0; i <= input.length - secret.length; i++) {
            for(int j = 0; j < secret.length; j++) {
                if(!input[i + j].equals(secret[j])) {
                    break;
                }
                cnt++;
            }
            if(cnt == secret.length) {
                System.out.println("secret");
                return;
            }
            cnt = 0;
        }
        System.out.println("normal");
    }
}

• 단순 문자열 비교 문제인 거 같아서 시간 복잡도를 고려해보니 최악의 경우의 수가 M*N인 10000이 나왔다.
• 주어진 1초는 충분한 시간이라고 판단되어 N^2의 시간복잡도를 가지는 for문 2개를 돌려 단순 비교하여 문제를 풀이하였다.