• 코드

정답 코드 : 입력한 배열 중 연속된 수의 합이 S이상일 때의 최소길이를 찾는 것이었다. 투 포인터를 사용하면 될 것 같아서 투포인터를 활용하여 풀었다.

 

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 N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());

		int[] array = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			array[i] = Integer.parseInt(st.nextToken());

		int start = 0, end = 0, sum = 0, answer=N+1,length=0;

		while (true) { 
			if (sum >= S) { 
				answer = Math.min(length, answer);
				sum -= array[start++];
				length--;
			} else if(end >= N) { 
				break;
			}
			else { 
				sum += array[end++];
				length++;
			}

		}

		if (answer==N+1) {
			System.out.println(0);
		} else {
			System.out.println(answer);
		}
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 15650번 : N과 M (2)  (0) 2020.09.01
[JAVA] 백준 15649번 : N과 M (1)  (0) 2020.09.01
[JAVA] 백준 14003번 : 가장 긴 증가하는 부분 수열 5  (0) 2020.08.31
[JAVA] 백준 14002번 : 가장 긴 증가하는 부분 수열 4  (0) 2020.08.31
[JAVA] 백준 13022번 : 늑대와 올바른 단어  (0) 2020.08.29

 

 

  • 코드

정답 코드 : 기존의 이진탐색, LIS 알고리즘 코드만으로는 풀 수 없어서, index를 배열에 저장해놨다가 출력할 때 index를 활용해서 차례대로 출력이 나오게 풀었다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] inputArray = new int[N];
		int[] LIS = new int[N];
		int[] arrayIndexes = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			inputArray[i] = Integer.parseInt(st.nextToken());
		}

		LIS[0] = inputArray[0];
		arrayIndexes[0] = 0;
		int j = 0;
		for (int i = 1; i < N; i++) {
			if (LIS[j] < inputArray[i]) {
				LIS[++j] = inputArray[i];
				arrayIndexes[i] = j;
			} else {
				int index = binary(LIS, 0, j, inputArray[i]);
				LIS[(int) index] = Math.min(LIS[index], inputArray[i]);
				arrayIndexes[i] = index;
			}
		}

		System.out.println(j + 1);

		String printString = "";
		for (int i = N - 1; i >= 0; i--) {
			if (arrayIndexes[i] == j) {
				printString = inputArray[i] + " " + printString;
				j--;
			}
		}
		System.out.print(printString);
	}

	static int binary(int[] LIS, int startIndex, int endIndex, int key) {
		while (startIndex <= endIndex) {
			int mid = (int) ((startIndex + endIndex) / 2);
			if (LIS[mid] < key) {
				startIndex = mid + 1;
			} else {
				endIndex = mid - 1;
			}
		}
		return startIndex;
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 15649번 : N과 M (1)  (0) 2020.09.01
[JAVA] 백준 1806번 : 부분합  (0) 2020.08.31
[JAVA] 백준 14002번 : 가장 긴 증가하는 부분 수열 4  (0) 2020.08.31
[JAVA] 백준 13022번 : 늑대와 올바른 단어  (0) 2020.08.29
[JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3  (0) 2020.08.28

 

 

  • 코드

정답 코드 : 기존의 이진탐색, LIS 알고리즘 코드만으로는 풀 수 없어서, index를 배열에 저장해놨다가 출력할 때 index를 활용해서 차례대로 출력이 나오게 풀었다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] inputArray = new int[N];
		int[] LIS = new int[N];
		int[] arrayIndexes = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			inputArray[i] = Integer.parseInt(st.nextToken());
		}

		LIS[0] = inputArray[0];
		arrayIndexes[0] = 0;
		int j = 0;
		for (int i = 1; i < N; i++) {
			if (LIS[j] < inputArray[i]) {
				LIS[++j] = inputArray[i];
				arrayIndexes[i] = j;
			} else {
				int index = binary(LIS, 0, j, inputArray[i]);
				LIS[(int) index] = Math.min(LIS[index], inputArray[i]);
				arrayIndexes[i] = index;
			}
		}

		System.out.println(j + 1);

		String printString = "";
		for (int i = N - 1; i >= 0; i--) {
			if (arrayIndexes[i] == j) {
				printString = inputArray[i] + " " + printString;
				j--;
			}
		}
		System.out.print(printString);
	}

	static int binary(int[] LIS, int startIndex, int endIndex, int key) {
		while (startIndex <= endIndex) {
			int mid = (int) ((startIndex + endIndex) / 2);
			if (LIS[mid] < key) {
				startIndex = mid + 1;
			} else {
				endIndex = mid - 1;
			}
		}
		return startIndex;
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 1806번 : 부분합  (0) 2020.08.31
[JAVA] 백준 14003번 : 가장 긴 증가하는 부분 수열 5  (0) 2020.08.31
[JAVA] 백준 13022번 : 늑대와 올바른 단어  (0) 2020.08.29
[JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3  (0) 2020.08.28
[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열  (0) 2020.08.28

 

 

  • 코드

정답 코드 : wolf의 올바른 순서는 정규식으로 맞는지 틀린지 판단을 했다. 근데 문제는 wolf을 제대로 썼는데 woolf이런식으로 쓴 경우가 문제가 되었다. 그래서 카운트를 세어서 w,o,l,f의 개수가 모두 같을 때 1을 출력하게 했는데 또 문제가 발생을 했다. wwolfwoolfwollfwolff 이런식으로 테스트 데이터를 넣으면 0을 출력해야 되는데, 1을 출력하는 것이었다. 그래서 이 부분은 반복문 안에서 f다음에 w가 올때 그 전 wolf의 개수가 모두 동일한지 판단을 해서 boolean형식으로 체크를 했다.

 

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 S = br.readLine();
		String test = "(w+o+l+f+)+";
		int wCount=0,oCount=0,lCount=0,fCount=0;
		boolean check = false;
		
		for(int i=0;i<S.length();i++) {			
			if(S.charAt(i)=='w')
				wCount++;
			else if(S.charAt(i)=='o')
				oCount++;
			else if(S.charAt(i)=='l')
				lCount++;
			else
				fCount++;
			
			if(i<S.length()-1 && S.charAt(i)=='f' && S.charAt(i+1)=='w') {
				if(!(wCount==oCount && oCount==lCount&& lCount==fCount && fCount == wCount)) {
					check = true;
					break;
				}
			}
		}
		
		if(!check && S.matches(test) && wCount==oCount && oCount==lCount&& lCount==fCount && fCount == wCount)
			System.out.println(1);
		else
			System.out.println(0);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 14003번 : 가장 긴 증가하는 부분 수열 5  (0) 2020.08.31
[JAVA] 백준 14002번 : 가장 긴 증가하는 부분 수열 4  (0) 2020.08.31
[JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3  (0) 2020.08.28
[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열  (0) 2020.08.28
[JAVA] 백준 13711번 : LCS 4  (0) 2020.08.27

 

 

  • 코드

성공 코드 : 이분 탐색을 통해서 LIS배열보다 큰값은 LIS배열 뒤에 붙여주었고, LIS배열 맨 뒤에 값보다 작은 값은 이분탐색을 통해서 INDEX를 가져와서 값을 바꿔주었다.

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		long N = Integer.parseInt(br.readLine());
		long[] inputArray = new long[(int) N];
		long[] LIS = new long[(int) N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (long i = 0; i < N; i++) {
			inputArray[(int) i] = Integer.parseInt(st.nextToken());
		}

		LIS[0] = inputArray[0];
		long j = 0;

		for (long i = 1; i < N; i++) {
			if (LIS[(int) j] < inputArray[(int) i]) {
				LIS[(int) ++j] = inputArray[(int) i];
			} else {
				long ans = binarySearch(LIS, 0, j, inputArray[(int) i]);
				LIS[(int) ans] = Math.min(LIS[(int) ans], inputArray[(int) i]);
			}
		}
		System.out.println(j + 1);
	}

	static long binarySearch(long[] LIS, int startIndex, long endIndex, long key) {
		while (startIndex <= endIndex) {
			int mid = (int) ((startIndex + endIndex) / 2); 
			if (LIS[mid] < key) {
				startIndex = mid + 1;
			} else {
				endIndex = mid - 1;
			}
		}
		return startIndex;
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 14002번 : 가장 긴 증가하는 부분 수열 4  (0) 2020.08.31
[JAVA] 백준 13022번 : 늑대와 올바른 단어  (0) 2020.08.29
[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열  (0) 2020.08.28
[JAVA] 백준 13711번 : LCS 4  (0) 2020.08.27
[JAVA] 백준 1958번 : LCS 3  (0) 2020.08.27

 

 

  • 코드

성공 코드 : 점화식을 통해 문제를 풀었다. 점화식은 현재 위치에 있는 값보다 작은 위치에 있는 값의 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)의 시간 복잡도가 나온다고 한다. 

 

'algorithm' 카테고리의 다른 글

[JAVA] 백준 13022번 : 늑대와 올바른 단어  (0) 2020.08.29
[JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3  (0) 2020.08.28
[JAVA] 백준 13711번 : LCS 4  (0) 2020.08.27
[JAVA] 백준 1958번 : LCS 3  (0) 2020.08.27
[JAVA] 백준 1027번 : 고층 건물  (0) 2020.08.27

 

  • 코드

실패 코드 : 기존 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);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 12738번 : 가장 긴 증가하는 부분 수열 3  (0) 2020.08.28
[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열  (0) 2020.08.28
[JAVA] 백준 1958번 : LCS 3  (0) 2020.08.27
[JAVA] 백준 1027번 : 고층 건물  (0) 2020.08.27
[JAVA] 백준 1644번 : 소수의 연속합  (0) 2020.08.26

 

 

  • 코드

정답 코드 : 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()]);
	}
}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 11053번 : 가장 긴 증가하는 부분 수열  (0) 2020.08.28
[JAVA] 백준 13711번 : LCS 4  (0) 2020.08.27
[JAVA] 백준 1027번 : 고층 건물  (0) 2020.08.27
[JAVA] 백준 1644번 : 소수의 연속합  (0) 2020.08.26
[JAVA] 백준 2671번 : 잠수함식별  (0) 2020.08.25

+ Recent posts

티스토리툴바