선장 일지

• 코드

성공 코드 : 점화식을 통해 문제를 풀었다. 점화식은 현재 위치에 있는 값보다 작은 위치에 있는 값의 dp index 값보다 +1한 값을 가져온다. 없다면 그대로 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));

		int N = Integer.parseInt(br.readLine());
		
		int [] dp = new int[N];
		int [] a = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        int max = 1;
        for (int i = 0; i < N; i++) {
        	if (dp[i] == 0) 
        		dp[i] = 1;
        	for (int j = 0; j < i; j++) {
        		if (a[i] > a[j]) 
        			dp[i] = Math.max(dp[i], dp[j]+1);
        	}
            if(max<dp[i])
            	max=dp[i];
        }

        System.out.println(max);
	}
}

• 부가 설명

현재 위 코드의 시간복잡도는 O(N^2)이고, LIS 알고리즘을 사용하면 O(NlongN)의 시간 복잡도가 나온다고 한다. 

• 코드

실패 코드 : 기존 LCS 방식으로 해보았다. 결과는 메모리 초과, int[]를 stringbuilder로도 해봤지만 메모리 초과

                메모리 초과의 이유는 (10만x10만xsizeof(int))이기 때문이였다.

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));

		long input = Long.parseLong(br.readLine());
		
		int[] firstArray = new int[(int) input];
		int[] secondArray = new int[(int) input];
		
		StringTokenizer string = new StringTokenizer(br.readLine());
		for(long i=0;i<input;i++) {
			firstArray[(int) i] = Integer.parseInt(string.nextToken());
		}
		string = new StringTokenizer(br.readLine());
		for(long i=0;i<input;i++) {
			secondArray[(int) i] = Integer.parseInt(string.nextToken());
		}
		

		int[][] dp = new int[(int) (input + 1)][(int) (input + 1)];

		for (int i = 1; i <= firstArray.length; i++) {
			for (int j = 1; j <= secondArray.length; j++) {
					if (firstArray[i-1] == secondArray[j - 1]) {
						dp[i][j] = dp[i - 1][j - 1] + 1;
					} else {
						dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
					}
				
			}
		}
		
		System.out.println(dp[firstArray.length][secondArray.length]);
	}
}

성공 코드 : 첫번째 배열을 LIS배열에 순서대로 넣고, 두번째 배열을 LIS 알고리즘에 따라서 풀었다.

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));
        
        int input = Integer.parseInt(br.readLine());
        int[] LIS = new int[input + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= input; i++)
            LIS[Integer.parseInt(st.nextToken())] = i;
        
        int[] arrays = new int[input];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < input; i++)
            arrays[i] = LIS[Integer.parseInt(st.nextToken())];
        
        int j = 0;
        LIS[j++] = arrays[0];
        for (int i = 1; i < input; i++) {
            int index = Arrays.binarySearch(LIS, 0, j, arrays[i]);
            if (index == -(j + 1))
                LIS[j++] = arrays[i];
            else
                LIS[-(index + 1)] = arrays[i];
        }
        System.out.print(j);
	}
}

• 코드

정답 코드 : LCS algorithm의 방식을 3차원으로 가져와서 풀었다. (https://www.youtube.com/watch?v=EAXDUxVYquY - 알고리즘 설명 링크)

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 firstInput = br.readLine();
		String secondInput = br.readLine();
		String thirdInput = br.readLine();

		int[][][] dp = new int[firstInput.length() + 1][secondInput.length() + 1][thirdInput.length() + 1];

		for (int i = 1; i <= firstInput.length(); i++) {
			for (int j = 1; j <= secondInput.length(); j++) {
				for (int z = 1; z <= thirdInput.length(); z++) {
					if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1) 
							&& secondInput.charAt(j - 1) == thirdInput.charAt(z-1)) {
						dp[i][j][z] = dp[i - 1][j - 1][z - 1] + 1;
					} else {
						dp[i][j][z] = Math.max(dp[i][j][z-1] ,Math.max(dp[i][j - 1][z], dp[i - 1][j][z]));
					}
				}
			}
		}
		
		System.out.println(dp[firstInput.length()][secondInput.length()][thirdInput.length()]);
	}
}

• 코드

실패 코드 : 처음 코드는 아니고 많이 바꾼 코드인데, 젤 긴 건물의 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);
				
    }
}