'Java' 카테고리의 글 목록 (17 Page) :: da9dac

Java

[백준] 15665번 : N과 M (11)

da9dac 2023. 10. 30. 14:58

2023. 10. 30. 14:58

728x90

문제

접근 방식

같은 수를 여러번 골라도 상관 없지만 이전 글에서와 같이

9a, 9b 같은 값이 9로 동일한 경우는 순서가 바껴도 똑같기 때문에

이 부분만 중복으로 취급하여 넘어가주면 된다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0);

		System.out.println(sb);
	}

	private static void createSequence(int size) {
		if (size == m) {
			for (int seq : sequence) {
				sb.append(seq).append(" ");
			}
			sb.append("\n");
			return;
		}

		int before = 0;

		for (int i = 0; i < n; i++) {
			if (before != arr[i]) {
				sequence[size] = arr[i];
				before = arr[i];
				createSequence(size + 1);
			}
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 9663번 : N-Queen (1)	2023.11.01
[백준] 15666번 : N과 M (12) (0)	2023.10.30
[백준] 15664번 : N과 M (10) (0)	2023.10.30
[백준] 15663번 : N과 M (9) (0)	2023.10.30
[백준] 15657번 : N과 M (8) (0)	2023.10.30

[백준] 15664번 : N과 M (10)

da9dac 2023. 10. 30. 14:22

2023. 10. 30. 14:22

728x90

문제

접근 방식

수열 [1, 7]과 수열 [7, 1]을 같은 경우로 취급하여

오름차순으로 출력하기 위해 [1, 7]만 출력해야 한다.

그러면 [1, 7, 8, 9, 9] 라는 배열이 주어졌을 때

1로 시작하는 경우의 수가 7로 시작하는 경우보다 많을 것이고

8보다는 7이, 9보다는 8이 경우의 수가 더 많아지는

시작에서 끝으로 갈수록 경우의 수가 적어지는 규칙이 있다.

즉 정렬된 배열에서 이미 사용한 인덱스는 다시 사용할 필요가 없기 때문에

재귀 메서드의 파라미터로 인덱스를 추가로 전달해준다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int seq : sequence) {
				sb.append(seq).append(" ");
			}
			sb.append("\n");
			return;
		}

		int before = 0;

		for (int i = start; i < n; i++) {
			if (before != arr[i]) {
				sequence[size] = arr[i];
				before = arr[i];
				createSequence(size + 1, i + 1);
			}
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15666번 : N과 M (12) (0)	2023.10.30
[백준] 15665번 : N과 M (11) (0)	2023.10.30
[백준] 15663번 : N과 M (9) (0)	2023.10.30
[백준] 15657번 : N과 M (8) (0)	2023.10.30
[백준] 15656번 : N과 M (7) (1)	2023.10.29

[백준] 15663번 : N과 M (9)

da9dac 2023. 10. 30. 13:41

2023. 10. 30. 13:41

728x90

문제

접근 방식

주어진 수들을 정렬하여 오름차순으로 출력하는건 이전 문제들과 똑같지만

이미 뽑은 수를 재사용하면 안되고 중복된 수열은 제외해야 한다는 조건이 붙었다.

중복된 수열을 제외하는 부분이 많이 힘들었는데

이미 뽑은 수를 체크하는 배열 외에도

현재 재귀 호출에서 이전에 뽑은 수를 기록해둘 지역변수를 하나 추가해서 해결했다.

예를 들어 [1, 7, 9, 9] 같은 수들이 주어진 경우

두 번 등장하는 9를 각각 9a, 9b라고 했을 때

1 7 9a 9b와 1 7 9b 9a는 같은 수열로 취급하여 하나만 출력해야 하는데

이때 9a를 이전에 사용한 값이라고 저장해둘 지역변수에 담아두면

나중에 1 7 까지 뽑고 9b를 뽑는 순간에 비교하여 넘어갈 수 있다.

글로 적으려니 설명을 잘 못하겠어서 재귀 호출 순서를 일부만 적어보겠다.

[1, 7, 9a, 9b]

size = 0일 때 1을 뽑는다. >> before = 1
	size = 1일 때 7을 뽑는다. >> before = 7
    	size = 2일 때 9a을 뽑는다. >> before = 9a
        	size = 3일 때 9b을 뽑는다. >> before = 9b
        size = 2일 때 9b을 뽑는다. >> 9a == 9b 해당 재귀 호출을 넘어감
    size = 1일 때 9a을 뽑는다. >> 7 != 9a >> before = 9a
    	...

주의할 점이 있다면 이전에 사용한 값을 담을 변수는 전역 변수가 아니라

재귀 메서드 내에서 각각의 스택에서 사용될 지역 변수로 선언해야 한다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;
	private static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];
		isUsed = new boolean[n];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0);

		System.out.println(sb);
	}

	private static void createSequence(int size) {
		if (size == m) {
			for (int seq : sequence) {
				sb.append(seq).append(" ");
			}
			sb.append("\n");

			return;
		}

		int before = 0;

		for (int i = 0; i < n; i++) {
			if (!isUsed[i] && before != arr[i]) {
				sequence[size] = arr[i];
				isUsed[i] = true;
				before = arr[i];
				createSequence(size + 1);
				isUsed[i] = false;
			}
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15665번 : N과 M (11) (0)	2023.10.30
[백준] 15664번 : N과 M (10) (0)	2023.10.30
[백준] 15657번 : N과 M (8) (0)	2023.10.30
[백준] 15656번 : N과 M (7) (1)	2023.10.29
[백준] 15655번 : N과 M (6) (0)	2023.10.29

[백준] 15657번 : N과 M (8)

da9dac 2023. 10. 30. 08:56

2023. 10. 30. 08:56

728x90

문제

접근 방식

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

위와 같이 주어진 배열을 정렬하여 오름차순으로 수열을 출력해 주면 되는데

다음에 오는 숫자는 처음이 아니라 항상 이전 숫자와 같은 인덱스에서부터 시작한다

예를 들어 이전에 1231을 뽑았으면 다음에 뽑을 수 있는 수는 1231, 1232, 1233, 1234고

이전에 뽑은 수가 1233이라면 다음에 뽑을 수 있는 수는 1233, 1234 뿐이다.

그래서 재귀를 호출할 때마다 현재 자신이 선택한 인덱스를 넘겨주면 된다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		arr = new int[n];
		sequence = new int[m];

		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(sequence[i]).append(" ");
			}
			sb.append("\n");

			return;
		}

		for (int i = start; i < n; i++) {
			sequence[size] = arr[i];
			createSequence(size + 1, i);
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15664번 : N과 M (10) (0)	2023.10.30
[백준] 15663번 : N과 M (9) (0)	2023.10.30
[백준] 15656번 : N과 M (7) (1)	2023.10.29
[백준] 15655번 : N과 M (6) (0)	2023.10.29
[백준] 15654번 : N과 M (5) (0)	2023.10.29

[백준] 15656번 : N과 M (7)

da9dac 2023. 10. 29. 23:47

2023. 10. 29. 23:47

728x90

문제

접근 방식

주어진 배열을 정렬하여 중복해서 선택할 때

M개의 수를 고르는 모든 경우를 출력하면 된다.

모든 수를 중복해서 계속 사용할 수 있기 때문에

사용 여부를 체크하거나 인덱스에 변화를 줄 필요 없이

계속해서 재귀호출과 M번의 반복문을 돌아주면 된다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] sequence;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");

		arr = new int[n];
		sequence = new int[m];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0);

		System.out.println(sb);
	}

	private static void createSequence(int size) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(sequence[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = 0; i < arr.length; i++) {
			sequence[size] = arr[i];
			createSequence(size + 1);
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15663번 : N과 M (9) (0)	2023.10.30
[백준] 15657번 : N과 M (8) (0)	2023.10.30
[백준] 15655번 : N과 M (6) (0)	2023.10.29
[백준] 15654번 : N과 M (5) (0)	2023.10.29
[백준] 15652번 : N과 M (4) (0)	2023.10.29

[백준] 15655번 : N과 M (6)

da9dac 2023. 10. 29. 23:26

2023. 10. 29. 23:26

728x90

문제

접근 방식

N과 M 시리즈 2번 문제와 같은 문제로

추가로 주어진 배열 입력에 대해 정렬하여 오름차순으로

수열을 만들어 출력하는 문제다.

이전에 등장한 수열이라면 순서 상관없이 중복으로 취급하여

다시 출력하는 경우가 없어야 한다.

예를 들어 1 7 8을 출력했으면 8 7 1 같은걸 출력할 필요가 없다.

즉, 주어진 배열을 순회하며 수열을 만들 때,

다음 자리 수를 뽑는 재귀 호출 시 시작 인덱스를 1씩 증가시켜주면 된다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] permutation;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");

		arr = new int[n];
		permutation = new int[m];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createSequence(0, 0);

		System.out.println(sb);
	}

	private static void createSequence(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(permutation[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = start; i < arr.length; i++) {
			permutation[size] = arr[i];
			createSequence(size + 1, i + 1);
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15657번 : N과 M (8) (0)	2023.10.30
[백준] 15656번 : N과 M (7) (1)	2023.10.29
[백준] 15654번 : N과 M (5) (0)	2023.10.29
[백준] 15652번 : N과 M (4) (0)	2023.10.29
[백준] 15651번 : N과 M (3) (0)	2023.10.28

[백준] 15654번 : N과 M (5)

da9dac 2023. 10. 29. 22:33

2023. 10. 29. 22:33

728x90

문제

접근 방식

N과 M (1) 문제와 같은 문제에 조건만 조금 달라져서 풀기가 쉬웠다.

1 ~ 4번 시리즈와는 다르게 정수 배열에 대한 입력이 추가되는데

이를 정렬된 순서로 자기 자신은 제외한 순열을 만들어주면 된다.

코드는 N과 M (1) 문제와 같고 정렬만 추가된다고 이해하면 된다.

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;
	private static int[] permutation;
	private static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");

		arr = new int[n];
		permutation = new int[m];
		isUsed = new boolean[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(arr);

		createPermutation(0);

		System.out.println(sb);
	}

	private static void createPermutation(int size) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(permutation[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = 0; i < arr.length; i++) {
			if (!isUsed[i]) {
				permutation[size] = arr[i];
				isUsed[i] = true;
				createPermutation(size + 1);
				isUsed[i] = false;
			}
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15656번 : N과 M (7) (1)	2023.10.29
[백준] 15655번 : N과 M (6) (0)	2023.10.29
[백준] 15652번 : N과 M (4) (0)	2023.10.29
[백준] 15651번 : N과 M (3) (0)	2023.10.28
[백준] 2448번 : 별 찍기 - 11 (0)	2023.10.27

[백준] 15652번 : N과 M (4)

da9dac 2023. 10. 29. 22:09

2023. 10. 29. 22:09

728x90

문제

접근 방식

우선 1부터 N까지의 숫자를 중복이 가능하게 3개를 뽑아서 수열을 만들 수 있을 때

위와 같은 규칙대로 수열을 만들어야 한다.

111, 112, 113 >> 122, 123

위의 숫자를 보면 규칙을 하나 찾을 수 있는데

다음에 올 수 있는 숫자의 범위는

항상 이전의 숫자보다 같거나 커야 한다.

별 찍기도 그렇고 N과 M시리즈도 그렇고

혼자 규칙 찾아서 풀어야 하는거만 빼면

재귀 연습하기는 참 좋긴하다...

어쨋든 이 규칙대로 수열을 만들기 위해서는

재귀 호출을 할 때 다음에 올 숫자의 시작 범위를

파라미터로 넘겨줘야 한다는 것이다.

이 부분만 생각하면서 풀면 어렵지 않게 풀 수 있는데

규칙을 잘못 알아서 삽질을 했던 문제다...

풀이

public class Main {

	private static StringBuilder sb = new StringBuilder();
	private static int n;
	private static int m;
	private static int[] arr;

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

		String[] nm = br.readLine().split(" ");

		n = Integer.parseInt(nm[0]);
		m = Integer.parseInt(nm[1]);

		arr = new int[m];

		makeNumber(0, 1);

		System.out.println(sb);
	}

	private static void makeNumber(int size, int start) {
		if (size == m) {
			for (int i = 0; i < m; i++) {
				sb.append(arr[i]).append(" ");
			}

			sb.append("\n");

			return;
		}

		for (int i = start; i <= n; i++) {
			arr[size] = i;
			makeNumber(size + 1, i);
		}
	}
}

저작자표시

'Java > Algorithms' 카테고리의 다른 글

[백준] 15655번 : N과 M (6) (0)	2023.10.29
[백준] 15654번 : N과 M (5) (0)	2023.10.29
[백준] 15651번 : N과 M (3) (0)	2023.10.28
[백준] 2448번 : 별 찍기 - 11 (0)	2023.10.27
[백준] 2447번 : 별 찍기 - 10 (0)	2023.10.27

PREV 이전 1 ···14 15 16 17 18 19 20 ···29 NEXT 다음

+ Recent posts

Powered by Tistory, Designed by wallel

티스토리툴바