글 읽기 - 문제는 어찌어찌 풀었는데 너무 느립니다 조언 부탁드려요 JAVA

kisi1023 6년 전 0

제가 4학년인데 학교에서 알고리즘을 재대로 배우지 못해서 다시 처음부터 공부한지 일주일이 안됬는데요.

단계별 문제로 앞에부터 천천히 풀다가 대회문제를 하나 풀어봤습니다.

그런데 상위 다섯 분은 1000 MS를 넘지않는데, 제 코드는 수행속도가 4076 MS 로 나와서요.

제 코드에서 시간낭비가 되서 고칠만한 부분 조언 부탁드릴께요.

제가 문제를 잘못읽어서 무조건 1,2,3,4~...n 이런식으로 나가는줄알고 오름차순,내림차순을 이용해서 프로그램을 짰다가

문제 다시읽고, 작성한 코드에서 정답이 나오게 고쳤습니다. 조언 부탁드려요.

p.s. 기존에는 1 2 3 4 5 1 2 3 4 5 이 수열 중에 연속 5개가 나오는지 혹은

5 4 3 2 1 5 4 3 2 1 이수열중에 5개가 연속으로 나오는지를 생각하면서 알고리즘을 짯어요.

convert 함수는 나중에 추가했는데, 위에 기능이 되는 상황에서 1:1 맵핑하면 문제해결이 될거같아서 시도하면서 추가된 함수에요.

import java.io.*;
import java.util.*;
	
	public class Main {
		
		public static void main(String[] args) throws IOException {
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
			
			int a = Integer.parseInt(input.readLine());
			if(a<4) { // n= 1,2,3일때 모든 경우에 가능
				System.out.println("good puzzle");
				return;
			}
			int[] arr1= new int[a];
			int[] arr2= new int[a];
			int[] arr3= new int[a];
			String str1,str2;
			str1=input.readLine();
			str2=input.readLine();
			String[] strarr1= str1.split(" ");
			String[] strarr2= str2.split(" ");
			for(int i =0 ; i< a;i++) {
				arr1[i]=i+1;
				arr2[i]=Integer.parseInt(strarr2[i]);
				arr3[i]=Integer.parseInt(strarr1[i]);
				
				//	System.out.println("\n"+strarr1[i]+" "+ strarr2[i]);
			}
		
			arr2=convert(arr3,arr2,a); // 나중에 추가된 함수
			if (checkorder(arr2,a)) { //오름차순인지 내림차순인지 좌측에서 확인
				
			}else {
				arr2=Reverse(arr2,a); // 내림차순일때 오름차순으로 돌림.
			}
			int Location= findone(arr2,a); // 1의 위치를 찾음
			
			arr2=shiftn(arr2,a,Location); // 1의 위치에 따라서 쉬프팅
			boolean check = true;
            //오름차순이고, 1의 위치를 맞췄을때 일치하는지 확인. 
			for (int i =0; i<a;i++) {
				if(arr1[i]!=arr2[i])//하나라도 다르면 false
					check=false;  
			}
			if(check) {
				System.out.println("good puzzle");
			}
			else {
				System.out.println("bad puzzle");
			}
		}
        
        // 차후에추가된 맵핑용함수
		private static int[] convert(int[] arr,int[] arr2,int length) {
			int[] temp= new int[length];
			int value,i;
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			for( i =0; i< length;i++)
			map.put(arr[i], i+1);
			
			for( i =0;i<length;i++) {
				value= map.get(arr2[i]);
				temp[i]=value;
			}
			
			
			return temp;
		}
		
        //오름차순인지 확인
		public static boolean checkorder(int[] arr,int length) {
			if(arr[0]<arr[1]) {
				return true;
			}
			else if(arr[0]==length&&arr[1]==1) {
				return true;
			}
			else
			return false;
		}
        //내림차순을 오름차순으로 변경
		public static int[] Reverse(int[] arr,int length) {
			int[] temp= new int[length];
			for (int i =0; i< length;i++) {
				temp[i]=arr[length-1-i];
			}
			return temp;
		}
        // 1의 위치를 찾음
		public static int findone(int[] arr, int length) {
			for(int i=0; i<length;i++) {
				if (arr[i]==1)return i;
			}
			return -1;
		}
        //1의 위치에 따라서 쉬프트
		public static int[] shiftn(int[] arr, int length, int loc) {
			int[] temp=new int[length];
			int a=0,lastidx=length-1;
			
			for(int i =0 ; i < length ; i++) {
				if(i+loc<=length-1) {
					temp[i]=arr[i+loc];
				}
				else {
				temp[i]=arr[i+loc-length];
				}
			}

			return temp;
		} //shift
		
	}//main

일단 대회의 공식 솔루션은 https://github.com/jwvg0425/So... 여기서 확인하실 수 있습니다.

C++을 기준으로 작성되어 있어서 Java기준으로 작성하신 코드에서 비효율적인 부분을 보자면, 처음에 오름차순 / 내림차순만 된다고 생각하고 작성하신 다음에 그 로직이 동작하게 수정하시면서 로직에 필요없는 비효율적인 과정이 들어간 것 같아보입니다.

작성하신 코드는 (배열 입력) -> 입력 받은 값에 따라 Convert -> 오름차순/내림차순 확인 -> 1의 위치 찾음 -> 1위치 기반으로 회전 -> 일치하는 것 확인

이렇게 동작하는데요, 여기서 (1의 위치 찾음 -> 일치하는 것 확인) 로직만 있어도 답을 확인할 수 있습니다.

이건 작성하신 로직을 보면 이해하고 계신 것 같긴 한데, 설명하자면 문제에서 주어진 연산은 절대 배열의 순서 관계를 바꾸지 않습니다. 주어진 연산으로는 전체 배열이 전부 뒤집히거나 / 안 뒤집히거나 한 상태에서 앞뒤로 k칸 만큼 쉬프트가 일어나게만 만들 수 있죠. 즉 1 2 3 4 -> 1 3 2 4 와 같이 중간에서 순서 관계가 바뀐게 있으면 이건 잘못된 결과(bad puzzle)이라는 뜻이 됩니다.

이걸 판단하기 위해서, 처음 배열에서 특정 숫자의 위치가 결과 배열에서는 어느 위치에서 등장하는지를 찾습니다. 이건 굳이 1일 필요는 없고, 계산하기 편한건 처음 배열에서 맨 첫번째 숫자가 결과 배열에서 몇 번째 위치에 오는지를 따지는게 계산하기 좀 편하겠죠.

이제 이걸 알고 있는 상태에서는, 그 결과 배열에서 찾은 위치로부터 앞, 혹은 뒤로 n개의 원소를 순회하면서 모든 원소가 일치하는가, 아닌가를 확인해보면 됩니다. 이 과정 하나만으로도 의도하신 것과 동일한 결과가 나오고, 전체 원소를 순회하는 횟수가 훨씬 적기 때문에 더 빠르게 동작하게 됩니다. 이런 방식으로 수정한 코드를 아래에 첨부했어요.

* 아래 수정한 코드로 채점시 608ms가 나오는데, String Tokenizer로 바꿔서 인풋이 빨라진 것을 제외하고 기존에 작성하신 input 방식(readline후 split -> parseInt)으로 돌릴경우 1970ms 정도가 나오네요. 어쨌든 아래 로직 정도면 많이 최적화가 됩니다. 참고하시면 될 것 같아요.

import java.io.*;
import java.util.*;
	
	public class Main {
		
		public static void main(String[] args) throws IOException {
			BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
			
			int a = Integer.parseInt(input.readLine());
			int[] arr1= new int[a];
			int[] arr2= new int[a];
			StringTokenizer str1 = new StringTokenizer(input.readLine());
            StringTokenizer str2 = new StringTokenizer(input.readLine());

			for(int i =0 ; i< a;i++) {
				arr1[i]=Integer.parseInt(str1.nextToken());
				arr2[i]=Integer.parseInt(str2.nextToken());
			}

			int Location= find(arr2, arr1[0]); //맨 첫번째 원소의 위치를 찾음
			boolean check = true;
            boolean checkreverse = true;
             
			for (int i =0; i<a;i++) {
				if(arr1[i]!=arr2[(Location + i) % a]) { //하나라도 다르면 false
					check=false;
                    break;
                }
            }
            
            for (int i = 0; i < a ; i++) {
                if(arr1[i] != arr2[(Location - i + a) % a]) {
                    checkreverse = false;
                    break;
                }
            }
            
			if(check || checkreverse) {
				System.out.println("good puzzle");
			}
			else {
				System.out.println("bad puzzle");
			}
		}

        // 특정 숫자의 위치를 찾음
		public static int find(int[] arr, int value) {
			for(int i=0; i< arr.length;i++) {
				if (arr[i]==value)return i;
			}
			return -1;
		}
	}//main

kisi1023 6년 전 1

성실한 답변 감사드립니다.

일단 입력방식을 StringTokenizer 써보니 900MS로 진입하네요... 입출력방식이 어떻게 그렇게 큰차이를 만드는지 알아봐야겠네요.

말씀하신대로 로직에 필요없는 부분에 많군요. 답변보고 바로 코드수정해보았습니다.

그리고 링크도 감사합니다. 나들이를 그만하고 다시 초보자로돌아가서 단계별문제부터 풀어야겠습니다.

많은 도움이 되었습니다. 감사합니다.

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

문제

문제

출처

ICPC

문제는 어찌어찌 풀었는데 너무 느립니다 조언 부탁드려요 JAVA

kisi1023 6년 전 0

jwvg0425 6년 전 0

kisi1023 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말