선장 일지

• 문제 풀기 전 알아야 할 것

정답 코드 : 피보나치 문제풀 때 재귀로 풀었던 것이 생각이 나서 재귀로 풀려니까 시간이 너무 많이 걸릴 것 같아서 배열로 하자니 수가 너무 커서 주기가 있을 것 같아서, 피보나치 주기를 쳐보니 해결책이 나왔다.

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 됩니다. 이를 피사노 주기(Pisano Period)

주기의 길이가 P 이면, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다. M = 10^k 일 때, k > 2 라면, 주기는 항상 15 × 10^(k-1) 입니다. 이 사실을 모른다고 해도, 주기를 구하는 코드를 이용해서 문제를 풀 수 있습니다. 이 문제에서 M = 10^6 이기 때문에, 주기는 15 × 10^5 = 1500000가 됩니다.

• 코드

정답 코드 : 위의 내용을 토대로 코드를 작성하였다. 주기를 찾아서 "입력한 수의 % 1500000 크기"의 배열을 만들어서 피보나치 수열을 정렬하였고, "입력한 수의 % 1500000 크기"번째의 값을 출력했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
		long number = Long.parseLong(br.readLine());
		int cycle = (int)(number % 1500000);
		
		long[] fibonacciArray = new long[cycle+1];
		
		fibonacciArray[0]=0;
		fibonacciArray[1]=1;		
		
		for (int i = 2; i <= cycle; i++) 
			fibonacciArray[i] = (fibonacciArray[i-1] + fibonacciArray[i-2])%(long)Math.pow(10,6);
		
		System.out.println(fibonacciArray[cycle]);		
    }
}

다른 사람의 코드 : 나보다 속도가 빠르다. 사용한 방법은 행렬을 이용한 방법이다. 공부해두면 좋을 것 같다.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    static BigInteger N;
    static long[][] matrix = new long[2][2];
    static int mod = 1000000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = new BigInteger(br.readLine());
        if (N.equals(new BigInteger("1"))) {
            System.out.println(1);
        } else {
            matrix[0][0] = 1;
            matrix[1][0] = 1;
            matrix[0][1] = 1;
            matrix[1][1] = 0; // 피보나치 수를 구하는 하나의 방식, 나머지는 DP와 일반항
            matrix = getFibo(N.subtract(new BigInteger("1")));
            System.out.println(matrix[0][0]);
        }
    }

    private static long[][] getFibo(BigInteger N) {
        if (N.equals(new BigInteger("1")))
            return matrix;
        long[][] P = getFibo(N.divide(new BigInteger("2")));
        if (N.mod(new BigInteger("2")).equals(new BigInteger("0"))) {
            return MultiMatrix(P, P);
        } else {
            return MultiMatrix(MultiMatrix(P, P), matrix); // 아마 오버플로우는 없을 것이다
        }

    }

    private static long[][] MultiMatrix(long[][] A, long[][] B) {
        long[][] M = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    M[i][j] += A[i][k] * B[k][j];
                    M[i][j] %= mod; // 추측: mod 연산은 이것만으로 충분할 것
                }
            }
        }
        return M;
    }

    // private static void Print(long[][] arr) {
    //     System.out.println();
    //     for (int i = 0; i < 2; i++) {
    //         for (int j = 0; j < 2; j++) {
    //             System.out.print(arr[i][j] + " ");
    //         }
    //         System.out.println();
    //     }
    // }
}

• 코드

정답 코드 : 쉽게보고 했는데 시간초과, 틀렸습니다 등등으로 애먹게 했다...

               해결방법은 곱할때마다 바로 모듈로 연산을 해서 오버플로우를 방지하고

               b값 최대값이 꽤 높게 설정되어 있기때문에 분할정복을 이용한  재귀로 계산방법을 최소화 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
 
        System.out.println(Calculation(a, b, c));
    }
 
    public static long Calculation(int a, int b, int c) {
        if (b == 0) return 1;       
        if (b % 2 == 1) {           
            return Calculation(a, b - 1, c) * a % c;
        } else {                    
            long v = Calculation(a, b / 2, c) % c;
            return v * v % c;
        }
    }
}

• 코드

맞은 코드  : GCD구해주는 메소드를 하나 만들어서 재귀형식으로 GCD를 구해서 return해오는 방식으로 풀었다.

                처음에 sum을 int로 했었는데 틀렸다고 떴었음 (이유는 적어놓자..)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		int countGCD = Integer.parseInt(br.readLine());
		
		for(int i=0;i<countGCD;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			long sum = 0;
			int arraySize = Integer.parseInt(st.nextToken());
			int[] array = new int[arraySize];
			
			for(int j=0;j<arraySize;j++)
				array[j] = Integer.parseInt(st.nextToken());
			
			for(int j=0;j<arraySize-1;j++) 
				for(int z=j+1;z<arraySize;z++) 
					sum+= GCD(array[j],array[z]);

			sb.append(sum + "\n");
			
		}
		System.out.println(sb);		
    }
	
    private static int GCD(int x, int y)
    {
        if(x % y == 0) return y;
        return GCD(y, x%y);
    }

}

• 코드

성공 코드 : stack을 써서 풀으면 될 것 같아서 stack을 문자열 뒤에서부터 넣어주면서 폭발시켜야될 문자열이 들어오면

               폭발 시킨다. 처음 stack을 써봐서 좀 헤매긴했는데, 라이브러리로 stack기능을 바로 쓰게 해줘서 편했다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<Character> ();
        
        String BombedString = br.readLine();
        String bombString = br.readLine(); 

        for(int i = BombedString.length() - 1; i >= 0;  i--){
            stack.push(BombedString.charAt(i));   

            if(stack.size() >= bombString.length() && stack.peek() == bombString.charAt(0)){
                boolean isBomb = true;
                for(int j = 1; j < bombString.length(); j++){
                    if(stack.get(stack.size()-j-1) != bombString.charAt(j)){
                        isBomb = false;
                        break;
                    }
                } 

                if(isBomb){  
                    for(int j = 0; j < bombString.length(); j++) 
                    	stack.pop();
                }
            }
        }
        

        int stackSize = stack.size();
        StringBuilder sb = new StringBuilder();
        
        if(stack.isEmpty()){
               System.out.println("FRULA");
        }else{
               for(int i = 0; i < stackSize; i++) sb.append(stack.pop());
        }

        System.out.println(sb);

    }

}

다른 사람 코드 : 나보다 시간이 두배 더 빠르다. 코드가 기능별로 메소드로 정리해서 보기 좋고 잘 정리되어 있는 느낌.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String bomb = br.readLine();
        String answer = solution(str, bomb);
        System.out.println((answer.length() == 0) ? "FRULA" : answer);
    }

    private static String solution(String str, String bomb) {
        char[] result = new char[str.length()];
        int idx = 0;
        for (int i = 0; i < str.length(); i++) {
            result[idx] = str.charAt(i);
            if (isBomb(result, idx, bomb)) idx -= bomb.length();
            idx++;
        }
        return String.valueOf(result, 0, idx);
    }

    private static boolean isBomb(char[] result, int idx, String bomb) {
        if (idx < bomb.length() - 1) return false;
        for (int i = 0; i < bomb.length(); i++) {
            if (bomb.charAt(i) != result[idx - bomb.length() + 1 + i]) return false;
        }
        return true;
    }
}

• 코드

정답 코드 : dp를 이용해서 풀었다. 그 전에 dp값과 현재 number값을 더한값과 현재 number값을 비교해서 큰값을 dp[i]에 저장 dp[i]와 max를 비교해서 큰값을 max 변수에 저장하면 최종으로 max에 가장 큰 값이 저장된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub        
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int [] number = new int[n];
		int [] dp = new int[n];
		
		for(int i=0;i<n;i++)
			number[i]=Integer.parseInt(st.nextToken());
		
	    dp[0] = number[0];
	    int max = number[0];
	    for(int i=1; i<n; i++){
	         dp[i] = Math.max(dp[i-1]+number[i], number[i]);
	           
	         max = Math.max(max, dp[i]);
	    }

	    System.out.println(max);		

    }
}

• 코드

실패 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

               int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		String string = br.readLine().replace(" ","");  //==>>>여기가 런타임의 원인??(추측)
		
		int M = Integer.parseInt(br.readLine());
		
		for(int i=0;i<M;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			System.out.println(isPalindrome(Integer.parseInt(string),a,b));  //==>>여기가 시간초과의 원인
		}

	}
	
	static int isPalindrome(int number,int a, int b) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int temp = (b-a)/2+a;
		for(int i=a-1;i<=temp;i++) {
			if(integerToCharArray[i] != integerToCharArray[--b]) 
				return 0;
		}
		return 1;
	}
}

성공 코드 : String으로 받아서 빈공간 없게 해준다음 사용했는데 여기서 런타임이 뜬건가..? 아마도 여기서 뜨는 듯.

               ==>> int[] 배열로 받아서 가져오니까 런타임은 안떴지만, 시간초과가 떴다.

               시간초과는 반복문안에서 바로바로 출력을 해줬는데, 출력을 하는사이 작업을 하지 못해서? 그런 듯해서

               StringBuilder로 받아온 값을 append 시킨다음 반복문 빠져나온 뒤 한꺼번에 출력해주었다.

               결과는 맞았습니다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] palindrom = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1;i<=N;i++) 			
			palindrom[i] =  Integer.parseInt(st.nextToken());
		
				
		int M = Integer.parseInt(br.readLine());
		StringBuilder result = new StringBuilder();
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			
			result.append(isPalindrome(palindrom,
					Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())) +  "\n");
		}

		System.out.println(result.toString());
	}
	
	static int isPalindrome(int[] palindrom,int a, int b) {
		int temp = (b-a)/2 + a;
		for(int i=a;i<=temp;i++) {
			if(palindrom[i] != palindrom[b--]) 
				return 0;
		}
		return 1;
	}
}

다른 사람 코드 : 시간이 나보다 2배는 빠르게 나온다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int list[];
    static boolean check[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        list= new int[n+1];
        check =new boolean[n+1][n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            list[i] = Integer.parseInt(st.nextToken());
        }

        solve();
        int q = Integer.parseInt(br.readLine());
        for(int i=0; i<q; i++){
            st = new StringTokenizer(br.readLine());
            int start =Integer.parseInt(st.nextToken());
            int end =Integer.parseInt(st.nextToken());
            if(check[start][end]){
                sb.append(1+"\n");
            }else{
                sb.append(0+"\n");
            }
        }

        System.out.println(sb.toString());


    }
    public static void solve(){
        for(int i=1; i<=n; i++){
            check[i][i] = true;
        }

        for(int i=1; i<n; i++){
            if(list[i]==list[i+1]){
                check[i][i+1] = true;
            }
        }

        for(int i=2; i<n; i++){
            for(int k=1; k<=n-i; k++){
                if(list[k]==list[k+i] && check[k+1][k+i-1]){
                    check[k][k+i] = true;
                }
            }
        }

    }
}

• 코드

실패 코드  : 입력 값을 +1 하면서 반복문을 돈다. 안쪽에선 소수, 팰린드롬을 체크하며 소수이면서 팰린드롬이면 출력                    후 반복문 종료. 결과는 시간 초과

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int input = Integer.parseInt(br.readLine())-1;

		while(true) {
			boolean decimalCheck= false;
			boolean palindromeCheck = true;
			
			input++;
			
			for(int i=2;i<input;i++) {
				if(input%i==0) 
					break;
				if(i==input-1) 
					decimalCheck = true;					
			}
			
			int j=(int)(Math.log10(input)+1)-1;
			for(int i=0;i<(int)(Math.log10(input)+1)/2;i++) {
				if(!Character.toString(Integer.toString(input).charAt(i)).equals(Character.toString(Integer.toString(input).charAt(j)))) {
					palindromeCheck = false;
					break;
				}
			}
			
			
			if(decimalCheck && palindromeCheck) {
				bw.write(input + "\n");
				break;
			}
			
		}
		
		bw.flush();
		bw.close();
	}
}

성공 코드 : 소수와 팰린드롬 체크하는 메소드를 만들어서 boolean으로 넘겨 받아서 체크하게 했다.

                소수 체크에서 Math.sqrt(number)를 통해 시간을 단축시켰다.

                결과는 맞았습니다!!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int input = Integer.parseInt(br.readLine());
		if(input==1) {
			System.out.println(2);
			System.exit(0);
		}

		while(true) {
					
			if(isDecimal(input) && isPalindrome(input)) {
				System.out.println(input);
				break;
			}			
			input++;
		}
	}
	
	static boolean isDecimal(int number) {
		for(int i=2;i<=(int)Math.sqrt(number);i++) {
			if(number%i==0) 
				return false;
		}
		return true;
	}
	
	
	static boolean isPalindrome(int number) {
		char [] integerToCharArray = String.valueOf(number).toCharArray();
		int length = integerToCharArray.length-1;
		for(int i=0;i<=integerToCharArray.length/2;i++) {
			if(integerToCharArray[i] != integerToCharArray[length--]) 
				return false;
		}
		return true;
	}
}

다른 사람의 코드 : 시간이 빠르게 나오길래 가지고 왔다.

import java.io.*;
import java.util.*;

public class Main {
	private static boolean[] prime_num;
	public static void main(String[]args)throws IOException
	{
		prime_num= new boolean[1004001];
		prime_num[1]=true;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		if(n <=7) {
			Eratosthenes(10);
			for(int i = n; i<=10;i++) {
				if(!prime_num[i]) {
					System.out.println(i);
					break;
				}
			}
			}
		else {			
			   Eratosthenes(1004000);
				for(int i = n; i<=1004000;i++) {
					if(!prime_num[i]&&isPalindrome(i)==true) {
						System.out.println(i);
						break;
					}
				}
			}
		}
	
	private static void Eratosthenes(int n) {
		for(int i = 2; i*i <= n; i++) {
			if(prime_num[i]==false) {
				for(int k = i*i; k<=n; k+=i)
					prime_num[k]=true;
			}
		}
	} 
	private static boolean isPalindrome(int num) {
		String s = Integer.toString(num);
		if(s.length()%2==0) { 
			int i = 0;
			int j = s.length()-1;
			while(i<j) {
				if(s.charAt(i)!=s.charAt(j))
					return false;
				i++;
				j--;
			}
		}
		else { //홀수일 경우 
			int i =0 ;
			int j = s.length()-1;
			while(i!=j) {
				if(s.charAt(i)!=s.charAt(j)) 
					return false;
				i++;
				j--;
			}
		}
		return true;
	}
}

• 코드

성공 코드 : 괄호가 어디있던 첫번째 -기준으로 앞은 다 더해주고 뒤는 다 빼주면 최소값이 된다는 생각으로 풀었다.

               결과는 맞았습니다!!

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input = br.readLine();
		String[] minusSplit = input.split("-");
		int sum=0;
		
		for(int index=0;index<minusSplit.length;index++) {
			String[] number = minusSplit[index].split("[+]");
			for(int index2=0;index2<number.length;index2++) {
				if(index==0)
					sum+=Integer.parseInt(number[index2]);
				else
					sum-=Integer.parseInt(number[index2]);
			}
		}
		bw.write(sum + "\n");
		
		bw.flush();
		bw.close();
	}
}