선장 일지

• 코드

실패 코드 : 처음 코드는 아니고 많이 바꾼 코드인데, 젤 긴 건물의 index를 찾은 뒤, 그 건물부터 보이는 건물의 개수를 왼쪽, 오른쪽을 체크한 뒤 건물의 수를 오른쪽 index - 왼쪽 index로 출력했다. 이게 아닌가 보다... 문제 이해가 안된건가...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
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 number = Integer.parseInt(br.readLine());
		long [] array = new long[number];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<array.length;i++) 
			array[i] = Long.parseLong(st.nextToken());
		
		int maxValueIndex = 0;
		long saveValue=0;
		for(int i=0;i<array.length;i++) {
			if(saveValue<array[i]) {
				maxValueIndex=i;
				saveValue=array[i];
			}				
		}
		
		int max = 0;
		for(int i=1;i<maxValueIndex;i++) {
			if(array[max]<=array[i])
				max=i;
		}
		
		int max1 = maxValueIndex+1;
		for(int i=maxValueIndex+2;i<array.length;i++) {
			if(array[max1]<array[i])
				max1=i;
		}
		
		System.out.println(max1-max);
    }
}

다른 사람 설명 봤는데 CCW 알고리즘을 설명한다.. 다음에 공부해서 풀어봐야겠다..

• 코드

정답 코드 : 소수의 값들을 boolean배열에 false로 해놓고(에라토스테네스의 체) 해당 인덱스를 ArrayList에 넣어둔다. HashSet이 아닌 ArrayList에 넣는 이유는 넣는 순서를 유지시키기 위함. 그리고 입력 값의 수를 세는 것은 주석으로 설명해 놨다.

에라토스테네스의 체, 투 포인터 방식 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
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));
		
		long N = Long.parseLong(br.readLine());
        ArrayList<Integer> primeNumber = new ArrayList<>();
		
        boolean[] prime = new boolean[(int) (N+1)];
        prime[0] = prime[1] = true;
        
        for(int i=2; i*i<=N; i++){
            if(!prime[i]) {
            	for(int j=i*i; j<=N; j+=i) 
            		prime[j]=true;      
            }
        }            
        for(int i=2; i<=N;i++){
        	if(!prime[i]) primeNumber.add(i);     
        }
        
        int start=0, end=0, sum=0, count=0;
        while(true) {
        	if(sum==N) {		
        		count++;
        		sum-=primeNumber.get(start++);
        	}
        	else if(sum>N) {	//sum이 N보다 커지면 작은 소수의 값부터 점점 빼줌
        		sum-=primeNumber.get(start++);
        	}
        	else if(end == primeNumber.size()) { //sum이 N보다 작은데 end의 위치가 primeNumber.size랑 같으면 더이상 더해줄게 없기때문에 break;
        		break;
        	}
        	else {		//sum이 N보다 작으면 소수의 작은 값부터 큰값으로 점점 더해줌
        		sum+=primeNumber.get(end++);
        	}
        }
        
        System.out.println(count);
    }
}

• 코드

정답 코드 : 문제를 읽다보니까, 정규식이 생각나서 정규식으로 한번 풀어보았다.

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));
		
		String sound = br.readLine();
		String check = "(100+1+|01)+";
		
		if(sound.matches(check))
			System.out.println("SUBMARINE");
		else
		    System.out.println("NOISE");
		
	}
}

• 코드

정답 코드 : boolean 배열에 초기 false로 채워두고 지나간 값은 true로 변환해준다. true일시 건너띄고 false일 시 true로 바꿔주면서 count++해준다. count가 K랑 같아질 시 출력하고 종료.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		boolean[] check = new boolean[N+1];

	    int count = 0;

	    Arrays.fill(check, Boolean.FALSE);

	    for(int i = 2; i <= N; i++) {
	        for(int j = i; j <= N; j += i) {
	            if(check[j])
	                continue;
	            check[j] = true;
	            count ++;
	            if(count == K) {
	                System.out.println(j);
	                System.exit(0);
	            }
	        }
	    }
	  }
}

• 코드

실패 코드 : 일단 원하는대로 값은 나오는데 시간 초과가 뜬다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
		
		long min = Long.parseLong(st.nextToken());
		long max = Long.parseLong(st.nextToken());
		
		int count = (int) (max-min+1);
		for(int j=(int) min;j<=max;j++) {
			for(int i=2;i*i<=max;i++) {
				if(j%(i*i)==0) {
					count--;
					break;
				}
			}
		}
		
		System.out.println(count);
				
    }
}

정답 코드  : 에라토스테네스의 체 방식과 비슷한 방식으로 풀어 보았다.

                i가 2일때부터 i*i값을 가져와서 min값에서 가장 가까운 i*i로 떨어지는 값을 찾는다. 찾는 방법이 힘들었는데 찾은 식은 min +(index - (min%index))%index이다. 여기서 index는 i*i 값이다. i*i로 나누어 떨이지는 값들을 min부터 max값까지 모두 체크하고 i+1하고 해당 작업을 반복해주는 방식으로 하였다.

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());
		
		long min = Long.parseLong(st.nextToken());
		long max = Long.parseLong(st.nextToken());
		
		int range = (int) (max-min+1);
		
		boolean [] check = new boolean[range];
		
		for(long i=2;i*i<=max;i++) {
			long index = i*i;
			long startNumber = min +(index - (min%index))%index;
			
			for(long j = startNumber; j<=max;j+=index) {
				check[(int) (j-min)] = true;
			}
		}
		
        int count = 0;
        for(int i = 0; i < range; i++){
            if(!check[i])
                count++;
        }
        System.out.println(count);
				
    }
}

• 문제 풀기 전 알아야 할 것

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

피보나치 수를 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);
    }

}