글 읽기 - 자바 Arrays.asList().indexOf() ?? 시간초과

qkrehdwns032 1년 전 0

index = Arrays.asList(origin).indexOf(ptr[i]);

이부분에서 시간초과가 나는건가요??

출력은 잘 나오는데 풀이방식이 잘못된걸까요?

import java.util.Scanner;
import java.util.Arrays;

public class Main 
{
	public static void main(String[] args) 
	{

		Scanner sc = new Scanner(System.in);
		
		int n,m;
		int index= 0; 
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		String[] ptr = new String[m];
		
		String[] arr = new String[n];
		String[] origin = new String[n];
		String[] newOrigin = new String[n];
				
		for(int i=0;i<n;i++)
		{
			arr[i] = sc.next();
			origin[i] = arr[i];
			newOrigin[i] = arr[i];
			arr[i] = arr[i].toLowerCase();
			origin[i] = origin[i].toLowerCase();
			newOrigin[i] = newOrigin[i].toLowerCase();
		}
		
		Arrays.sort(arr);
		Arrays.sort(newOrigin);
		
		for(int i=0;i<m;i++)
		{
			ptr[i] = sc.next();
			ptr[i] = ptr[i].toLowerCase();
			
			if(ptr[i].charAt(0) == '0' ||ptr[i].charAt(0) == '1' || ptr[i].charAt(0) == '2'|| 
			   ptr[i].charAt(0) == '3' ||ptr[i].charAt(0) == '4' || ptr[i].charAt(0) == '5'|| 
			   ptr[i].charAt(0) == '6' ||ptr[i].charAt(0) == '7' || ptr[i].charAt(0) == '8'|| 
			   ptr[i].charAt(0) == '9')
			{
				System.out.println(origin[Integer.parseInt(ptr[i])-1]);
			}
			else
			{			
				index = Arrays.asList(origin).indexOf(ptr[i]);
				
				System.out.println(index+1);
				
			}
		}
		sc.close();
	}
}

문제를 풀 때에는 단순히 답이 잘 나오는지만이 아니라 항상 시간이 얼마나 걸릴지를 고려해야 합니다. indexOf를 쓰면 라이브러리가 다 해주니 너무나 편리하죠. 하지만 편리함에는 댓가가 따르기 마련입니다. indexOf라는 건 굉장히 무거운 연산입니다. 리스트의 입장에서는 ptr[i]라는 게 리스트의 어디에 숨어있을지 모르니, 처음부터 하나씩 일일이 비교해가면서 일치하는 것을 찾는 수밖에 없습니다. 결국 평균적으로 리스트의 길이에 비례하는 시간이 걸립니다. 이 부분을 라이브러리 대신 직접 루프를 돌려서 찾는다고 생각하고 직접 구현해보시면, 그게 얼마나 비효율적인지 시간 복잡도도 계산해보실 수 있습니다.

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

문제

문제

출처

ICPC

자바 Arrays.asList().indexOf() ?? 시간초과

qkrehdwns032 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말