글 읽기 - 시간초과가 나와요... 여기서 더 단축시킬방법이 있을까요 ?

woojin121 7년 전 1

1초가 넘어가네요.

이정도면 충분히 짧게 한것 같은데... 알려주시면 감사하겠습니다.

간단히 설명하면

2차원 boolean 배열에 별 모양이 들어갈 부분을 true로 만들고

마지막에 true를 별로 찍는 방법입니다.

import java.util.Scanner;



public class BJ2448 {
	static boolean[][] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		
			Scanner sc = new Scanner(System.in);
			
			int a = sc.nextInt();
			int row = a/3;
			
			arr = new boolean[row*3][row*6];
			//System.out.println();
			recur(a, 0,a-1);
			
			for (int i = 0; i < row*3; i++) {
				for (int j = 0; j < row*6; j++) {
					if (arr[i][j] == true) {
						System.out.print("*");
					
					}else{
						System.out.print(" ");
					}
					
					
				}
				System.out.println("");
			}
			
		
			
	}
	
	
	public static void recur(int n, int x, int y){
		if(n == 3){
			arr[x][y] = true;	
			arr[x+1][y+1] = true;	
			arr[x+1][y-1] = true;	
			arr[x+2][y-2] = true;	
			arr[x+2][y-1] = true;	
			arr[x+2][y] = true;	
			arr[x+2][y+1] = true;	
			arr[x+2][y+2] = true;	
			return;
		}
		int temp = n/2;
	//	System.out.println(n + " : "+ x + " : " + y);
		recur(temp,x,y);
		recur(temp,x+temp,y-temp);
		recur(temp,x+temp,y+temp);
		
	}

}

bupjae 7년 전 0

나중에 true를 '*', false를 ' '로 바꿔서 출력하느니, 아예 처음부터 '*', ' '를 저장해 두는 건 어떨까요? StringBuilder 같은 걸로요.

woojin121 7년 전 0

스트링 빌더로 어떤방식으로 하라고 하시는지 잘 모르겠어요 ㅜ

지금은 char배열로 각 자리에 * 를 미리 저장하고 있는데도 느리네요 .

bupjae 7년 전 0

char 배열을 사용하고 계신다면 출력할 때 한 글자씩 출력하지 말고 한 줄씩 String로 바꾼 뒤에 출력해 보세요

woojin121 7년 전 0

bupjae 님 말씀대로 출력형식을 바꿔봤는데 시간초과가 아닌 틀렸다고 나오네요 . 이클립스에서는 잘돌아가는데 ㅜ

import java.util.Scanner;

public class Main {
	static char[][] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		 
	        
			Scanner sc = new Scanner(System.in);
			
			int a = sc.nextInt();
			int row = a/3;
			
			arr = new char[a][a*2];
			//System.out.println();
			recur(a, 0,a-1);
			
			for (int i = 0; i < a; i++) {
				
					System.out.println(arr[i]);
                
                // 또는 System.out.println(new String(arr[i],0,arr[i].length ));
					
			}
			
			
			
	}
	
	
	public static void recur(int n, int x, int y){
		if(n == 3){
			arr[x][y] = '*';	
			arr[x+1][y+1] = '*';	
			arr[x+1][y-1] = '*';	
			arr[x+2][y-2] = '*';	
			arr[x+2][y-1] = '*';	
			arr[x+2][y] = '*';	
			arr[x+2][y+1] = '*';	
			arr[x+2][y+2] = '*';	
			return;
		}
		int temp = n/2;
	//	System.out.println(n + " : "+ x + " : " + y);
		recur(temp,x,y);
		recur(temp,x+temp,y-temp);
		recur(temp,x+temp,y+temp);
		
	}

}

bupjae 7년 전 0

처음에 char 배열을 빈 칸 (' ')으로 직접 초기화 해 주세요

배열 만든 직후에는 U+0000 이 들어가 있기 때문에 화면에서는 빈칸으로 보여도 문제에서 요구하는 공백과는 다른 글자입니다

woojin121 7년 전 0

배열만든 직후에 U+0000 이 들어간다는 사실을 몰랐어요 감사합니다.

그런데 bupjae 님 말씀대로 했더니 되긴 했는데 왜 됐는지 모르겠네요 ...

아래 코드처럼 결국 초기화를 하는데 배열의 n^2 만큼 시간이 소요되는데

이렇게 되면 기존 boolean배열과 2번째로 시도한 char 배열과 다르지 않을거같은데..

속도가 어디서 개선된지 알수 있을까요 ?

arr = new char[row*3][row*6];
			for (int i = 0; i < a; i++) {
				
				Arrays.fill(arr[i], ' ');
			}

bupjae 7년 전 0

속도가 개선된 부분은 출력문입니다.

시간복잡도 표기로는 동일하지만, 출력을 한 번 할 때 마다 syscall 이 발생하는데, 출력 크기와 독립적인 부분에서 생각하는 것 보다 많은 시간을 소비합니다.

예를들어 for 루프에서 print("#") 5만번 하는 것과 for 루프 없이 print(길이_5만_문자열) 하는 건 상당한 시간 차이가 납니다.

woojin121 7년 전 0

아 감사합니다.

계속 생각했었는데 bupjae 님이 말씀하신 이유랑 비슷하게 생각했어요 ㅎㅎ

정확한 답변주셔서 감사합니다.

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

문제

문제

출처

ICPC

시간초과가 나와요... 여기서 더 단축시킬방법이 있을까요 ?

woojin121 7년 전 1

bupjae 7년 전 0

woojin121 7년 전 0

bupjae 7년 전 0

woojin121 7년 전 0

bupjae 님 말씀대로 출력형식을 바꿔봤는데 시간초과가 아닌 틀렸다고 나오네요 . 이클립스에서는 잘돌아가는데 ㅜ

bupjae 7년 전 0

woojin121 7년 전 0

bupjae 7년 전 0

woojin121 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말