문제 이해

N개의 자연수가 주어진다. 이를 통해 수열을 하나 만들 수 있을 것이다.
이렇게 만든 수열을 통해 M개를 골라 출력하는 문제이다.
이 때 조건은 2가지가 존재한다.

1. 중복되는 수열을 여러 번 출력하면 안된다.

   • (9, 9) Case가 2개 있을 경우, 한번만 (9,9)를 출력해야 한다.

2. 같은 인덱스에 존재하는 숫자를 여러 번 고를 수 없다.

   • 이는 문제에 내포되어 있는 조건이라 이해하기 어려울 수도 있다.
   • (1,2,3)이라는 수열이 존재했을 때, (1,1)이나 (2,2)나 (3,3)과 같은 수열은 선택 될 수 없다(같은 index 번호가 2번 선택되었기 때문)

출력은 사전 순으로 출력한다.

---

문제 풀이

지금까지 풀었던 N과 M문제의 집합과 같은 문제가 아니였나 생각한다.

먼저, 위에서 설명한 2번 조건을 확인하기 위해서 index를 활용하기로 하였다. index는 0~N-1까지 한 개 씩 밖에 존재하지 않아야 하기 때문에 지금까지 풀어왔던 N과 M문제로 해결할 수 있을 것이라고 생각하였다.

이렇게 해서 2번 조건을 충족시켰다.

1번 조건은 충족시키가 조금 더 까다로웠다. index번호를 중복 없이 고르는 것은 쉬운 방법이지만, 우리가 결국 구해야 하는 것은 arr[index]의 집합이기 때문에 다시 주어진 수열에 접근하는 과정이 추가되어야 하는 것이다.

나는 이를 따로 내부 클래스를 정의하여, 내부 클래스에 list가 주어지면 클래스 자체에서 자동으로 이 과정을 수행하도록 지정하였다.

마지막으로 equals명령을 Override하여 리스트의 .contains() 명령을 통해 1번 조건 충족 여부를 확인하려고 하였다.

출력 시 사전 순으로 출력되어야 하는데, 다른 N과 M 문제에서 이런 방식으로 문제를 해결하면 index는 사전 순으로 정렬된다는 것을 알고 있다. 따라서, 처음에 주어진 수열이 Sorting되어 있으면 자동으로 결과물도 Sorting될 것이다.

따라서, 입력을 받자마자 해당 수열을 Sorting하는 방식으로 출력에 대한 고민을 해결했다

---

코드

import java.util.*;

public class Main {
	static int N, M;
	static Integer[] arr;
	static ArrayList<Value> ans_list = new ArrayList<Value>();
	
	static class Value { 
    // index값을 저장한 index를 arr[index]로 바꿔주는 클래스
		int[] val; // arr[index] 값을 저장할 배열
		int n;     // val array에 대한 길이
		
		public Value(LinkedList<Integer> list) {
			n = list.size();
			val = new int[n];
			
			for(int i = 0;i<n;i++) {
				val[i] = arr[list.get(i)];
			}
		}
		
		@Override
		public boolean equals(Object o) { 
            // contains()를 활용하기 위한 메서드
            // arr를 모두 비교하여, 한 개의 값이라도 다르면 false를 반환한다.

			Value v2 = (Value) o;
			for(int i =0;i<n;i++) {
				if(val[i]!=v2.val[i]) {
					return false;
				}
			}
			
			return true;
		}
	}
	
	static void N_M(LinkedList<Integer> list) {
		if(list.size()==M) {
			Value v = new Value(list);
			if(!ans_list.contains(v)) {
				ans_list.add(v);
			}
			return;
		}
		
		for(int i = 0;i<N;i++) {
			if(!list.contains(i)) {
				list.add(i);
				N_M(list);
				list.removeLast();
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new Integer[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		
		N_M(new LinkedList<Integer>());

		StringBuilder sb = new StringBuilder();
		for(Value v:ans_list) {
			for(int i =0;i<v.n;i++) {
				sb.append(v.val[i]+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}

---

결과

• 출력 초과 : 문제 이해 할 때 2번 조건을 이해하지 못하여 생겼다.

• 틀렸습니다 : 처음 이 문제를 풀 때 중복이 없다라는 말을 듣고 Set을 활용할 생각을 했다. 하지만 Set같은 경우 원소의 순서를 보장하지 않기 때문에 다시 한 번 Sorting을 할 필요가 있었다. 따라서 Set의 결과값을 list에 담고 Collections.sort()를 활용하여 sorting시켰다.
  이 때 문제점이 발생했다.
  Set에 String형으로 저장을 했는데, 만약 답이 (1,2,19)일 경우 String형 Sorting 이기 때문에 (1, 19, 2)로 답이 나온다는 사실을 알게 되었다.
  즉, Set으로 풀기 위해서는 Integer Class를 생성하거나 String을 쪼개서 Integer형으로 변환한 이후 Sorting 시켜야 했다.
  이렇게 변환을 하는 시간이 더 오래 걸린다고 생각하여 새로운 내부 클래스를 통해 문제를 해결하는 방향으로 풀이 방법을 바꿨다.