글 읽기 - 1020번 질문입니다.

ikth6001 4년 전 0

안녕하세요 1020번을 푸는데 시간초과가 나서 질문 드립니다(시간초과가 나서 정확한 답을 구하는 알고리즘인지는 파악 못했습니다)

알고리즘을 간략히 설명 드리자면,

입력받은 값의 선분 갯수 n을 구한다.
for(int i=2; i<=n; i++) loop을 돌면서 i를 만들 수 있는 숫자 패턴을 구한다. (숫자 패턴은 0-9 10개의 숫자의 각 선분 갯수와 동일하면 해당숫자를, 그보다 2이상 크면 그 전에 구한 패턴을 더합니다)
구한 숫자 패턴을 Long으로 변환/정렬 합니다.
다음 초를 구합니다.

개선 사항 설명해주시면 감사하겠습니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main 
{
	
	public static void main(String[] args) 
	{
		Scanner scanner= new Scanner(System.in);
		
		String str= scanner.nextLine();
		
		Main m= new Main();
		m.calculate(str);
		
		scanner.close();
	}
	
	public void calculate(String startStr)
	{
		/**
		 * 1. 숫자의 선분 갯수 n을 구한다.
		 * 2. 2부터 n까지 선분 갯수를 만들 수 있는 조합을 구한다(동적 프로그래밍 활용)
		 *    - 0에서 9까지 Loop을 돌며 n과 해당 숫자의 선분을 비교. 같으면 해당 숫자를 조합에 추가. 숫자의 갯수보다 n이 2보다 크거나 같으면 해당 조합 추가
		 * 3. n의 조합을 숫자 크기로 정렬 후 입력받은 숫자와 비교 계산
		 */
		Map<Integer, List<String>> record= new HashMap<>();
		
		int n= getStrCnt(startStr);
		
		for(int i=2; i<=n; i++)
		{
			record.put(i, new ArrayList<>());
			
			for(int j=0; j<10; j++)
			{
				int cnt= cnts[j];
				
				if(cnt == i)
				{
					record.get(i).add(String.valueOf(j));
				}
				else if( (i-cnt) >= 2 )
				{
					if(record.get(i-cnt) == null)
					{
						continue;
					}
					
					for(String str : record.get(i-cnt))
					{
						record.get(i).add(str + String.valueOf(j));
					}
				}
			}
		}
		
		List<String> patterns= record.get(n);
		Collections.sort(patterns, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) 
			{
				Long lng1= Long.parseLong(o1);
				Long lng2= Long.parseLong(o2);
				
				return lng1.compareTo(lng2);
			}
		});
		
		int idx= -1;
		
		for(int i=0; i<patterns.size(); i++)
		{
			if(patterns.get(i).equals(startStr))
			{
				idx= i;
				break;
			}
		}
		
		if(idx == patterns.size()-1)
		{
			System.out.println(1);
		}
		else
		{
			long curr= Long.parseLong(startStr);
			long next= Long.parseLong(patterns.get(idx+1));
			System.out.println(next-curr);
		}
	}
	
	private int[] cnts= new int[]{6, 2, 5, 5, 4, 5, 6, 3, 7, 5};
	
	private int getStrCnt(String str)
	{
		int r= 0;
		
		for(int i=0; i<str.length(); i++)
		{
			int num= Integer.parseInt(Character.toString(str.charAt(i)));
			r= r + cnts[num];
		}
		
		return r;
	}
}

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

문제

문제

출처

ICPC

1020번 질문입니다.

ikth6001 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말