글 읽기 - 줄세우기 시간초과 도와주세요.

quddnr4096 2년 전 0

자기 바로 다음 번호가 자신의 뒤에 위치해있다면 카운트를 1 증가시키고 그 다음 숫자에 대해 똑같이 반복,

이 때 카운트가 최대인 경우를 구해서 N - 최대를 해주는 형식으로 답을 구하려고 하였는데 시간초과에서 자꾸 막히네요..

나름 줄인다고 앞쪽에서 사용이 되었는 값은 그냥 넘어가는 형식을 취해줘도 안되네요..

고수님들 시간 줄이는 방법좀 알려주십쇼~

import java.util.*;

public class Main {
	static int setCount(int[] child,int i,boolean[] isuse){
		int count=1;
		isuse[i]=true;
		for(int j=i+1; j<child.length; j++)
		{
			if(child[i]+1 == child[j])
			{
				count++;
				i=j;
				isuse[j]=true;
			}
		}
		return count;
	}
	public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int child[]=new int[s.nextInt()];
		boolean isuse[]=new boolean[child.length];
		int count;
		int max=0;
		for(int i=0; i<child.length; i++)
			child[i]=s.nextInt();
		
		for(int i=0; i<child.length; i++)
		{
			if(isuse[i])
				continue;
			else
			{
				count=setCount(child,i,isuse);
				if(max<count)
					max=count;
			}	
		}
		
		System.out.println(child.length-max);
	}
}

methylene 2년 전 1

아이들의 번호 k를 하나씩 받을 때마다

받은 번호의 바로 앞번호가 아직 나오지 않았다면 arr[k] = 1을 저장(arr을 0으로 초기화 했다면 arr[k] = arr[k - 1] + 1;을 해도 무방)

이미 있다면 arr[k] = arr[k - 1] + 1;

이런식으로 하면 시간복잡도가 O(n)이 됩니다.

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

문제

문제

출처

ACM-ICPC

줄세우기 시간초과 도와주세요.

quddnr4096 2년 전 0

methylene 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말