• 코드

정답 코드 : 기존 N과 M (1) 문제에서 visit을 체크 해줬던 이유는 중복된 수가 나오지 않게하기 위해서였기때문에, 제거해줬다.

 

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

public class Main {
	private static int list[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			
			for (int i = 0; i < m; i++) {
				sb.append(list[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 1; i <= n; i++) {
			list[cnt] = i;
			dfs(cnt + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];

		sb = new StringBuilder();

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 15654번 : N과 M (5)  (0) 2020.09.01
[JAVA] 백준 15652번 : N과 M (4)  (0) 2020.09.01
[JAVA] 백준 15650번 : N과 M (2)  (0) 2020.09.01
[JAVA] 백준 15649번 : N과 M (1)  (0) 2020.09.01
[JAVA] 백준 1806번 : 부분합  (0) 2020.08.31

 

 

  • 코드

정답 코드 : 기존  N과 M (1)을 풀었던 코드에서 오름차순 일때만 추가할 수 있게 하였다.

 

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

public class Main {
	private static int list[];
	private static boolean visit[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			boolean check = true;
			for (int i = 1; i < m; i++) {
				if(list[i-1]>list[i])
					check = false;
			}
			if(check) {
				for (int i = 0; i < m; i++) {
					sb.append(list[i]).append(" ");
				}
				sb.append("\n");
			}
			return;
		}

		for (int i = 1; i <= n; i++) {
			if (visit[i])
				continue;
			visit[i] = true;
			list[cnt] = i;
			dfs(cnt + 1);
			visit[i] = false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		visit = new boolean[9];

		sb = new StringBuilder();

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 15652번 : N과 M (4)  (0) 2020.09.01
[JAVA] 백준 15651번 : N과 M (3)  (0) 2020.09.01
[JAVA] 백준 15649번 : N과 M (1)  (0) 2020.09.01
[JAVA] 백준 1806번 : 부분합  (0) 2020.08.31
[JAVA] 백준 14003번 : 가장 긴 증가하는 부분 수열 5  (0) 2020.08.31

 

 

  • 코드

정답 코드 : 백트래킹을 아직 한번도 정확하게 써본 적이 없어서 그런지 코드를 이해했지만 다시 풀라고하면 풀지 못할 것 같은 느낌이 든다. cnt가 m일 때만 출력하고 return해주면서, 앞의 숫자가 X일 떄, N-1개만큼 출력해준다.

 

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

public class Main {
	private static int list[];
	private static boolean visit[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			for (int i = 0; i < m; i++) {
				sb.append(list[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 1; i <= n; i++) {
			if (visit[i])
				continue;
			visit[i] = true;
			list[cnt] = i;
			dfs(cnt + 1);
			visit[i] = false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		list = new int[9];
		visit = new boolean[9];

		sb = new StringBuilder();

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}

'algorithm' 카테고리의 다른 글

[JAVA] 백준 15651번 : N과 M (3)  (0) 2020.09.01
[JAVA] 백준 15650번 : N과 M (2)  (0) 2020.09.01
[JAVA] 백준 1806번 : 부분합  (0) 2020.08.31
[JAVA] 백준 14003번 : 가장 긴 증가하는 부분 수열 5  (0) 2020.08.31
[JAVA] 백준 14002번 : 가장 긴 증가하는 부분 수열 4  (0) 2020.08.31

 

 

  • 코드

정답 코드 : 입력한 배열 중 연속된 수의 합이 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

+ Recent posts

티스토리툴바