글 읽기 - 문제 의도가 이렇게 푸는게 아닌거같아서 질문이요...

dubaihuadeweixiao 1년 전 0

문제를 보고 (탐색 worstcase 1억*문자열 비교시간) 하면 시간초과 나겠구나 해서 일단 시간초과 나는지 보자 해서 내본 코드입니다.

코드를 보면 그냥 단순하게 링크드 리스트로 만들어서 무식하게 linear search하는 방법으로 내본건데 AC떠서 이게 문제 의도에 맞나? 생각이 들어서 질문드려요

왜 이코드는 시간초과가 안뜰까요?

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

public class Main {

    static LinkedList<String> strList;
    //N=10000 M=10000 > 1억 O(n^2)가능
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String rd = br.readLine();
        String[] str = rd.split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        strList = new LinkedList<>();
        int cnt=0;

        for(int i=0; i<N; i++) {
            strList.add(br.readLine());
        }

        for(int i=0; i<M; i++) {
            if(isIncluded(br.readLine()))
                cnt++;
        }

        System.out.println(cnt);
    }

    //리스트에 들어있는지 체크
    private static boolean isIncluded(String findstr) {
        for(String str:strList) {
            if(str.equals(findstr))
                return true;
        }
        return false;
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 의도가 이렇게 푸는게 아닌거같아서 질문이요...

dubaihuadeweixiao 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말