아이디어

• 기본적으로 입력을 오름차순 정렬 후 순열을 이용한 브루트포스 문제
• 이제 중복 문자열을 걸러야 하는데, 메모리 제한이 널널하다는 점에서 공간복잡도가 큰 방법이 가능함을 의심해볼 수 있다.
  • 만들어진 문자열을 HashSet에 저장해서 중복되는 문자열일 경우 제거한다.
  • 이것이 가능하다고 판단하기 위해서는 HashSet에 대해 이해해야 한다.

HashSet이란?

• 해시 함수를 사용하여 구현한 Set
• 조회 시간 복잡도가 거의 $O(1)$: 문제 없음
• 내부적으로는 HashMap으로 구현되어 있다.
  • 특정 크기의 배열을 만들고, 0에서 배열 크기 사이에 있는 key의 해시값을 인덱스로 사용하여 접근하는 방식
  • Set의 원소를 key로 사용하고 value에는 의미 없는 상수값(PRESENT)을 공유한다.
• 한편, 해시 함수는 int 타입의 정수값을 가진다.
• 최악의 경우 나올 수 있는 문자열의 수가 $8^8 = 16,777,216$이므로, key가 차지하는 공간은 최대 $67,108,864$ 바이트 = $64$ MB 정도라고 추측할 수 있다.
• 한편, 메모리 제한이 $512$ MB 정도이므로 위와 같은 방법이 충분히 가능할 수 있다고 합리적으로 의심할 수 있다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, M, A[];
	static int[] buf;
	static Set<String> set = new HashSet<>();

	static StringBuilder sb2;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		A = new int[N];
		tk = new StringTokenizer(rd.readLine());
		for (int i=0; i<N; i++)
			A[i] = Integer.parseInt(tk.nextToken());
		
		Arrays.sort(A);
		
		buf = new int[M];
		
		for (int i=0; i<N; i++)
			perm(i, 0);

		System.out.println(sb);
	}

	static void perm(int idx, int d) {
		if (d == M) {
			sb2 = new StringBuilder();
			for (int i=0; i<M; i++) {
				sb2.append(buf[i]).append(' ');
			}
			sb2.append('\n');
			
			String s = sb2.toString();
			if (set.contains(s)) return;
			sb.append(s);
			set.add(s);
			return;
		}
		
		buf[d] = A[idx];

		for (int i=0; i<N; i++) {
			if (buf[d] > A[i]) continue;
			perm(i, d + 1);
		}
		
	}
}

메모리 및 시간

• 메모리: 25196 KB
• 시간: 216 ms

리뷰

• SSAFY 2학기 이후 제대로 알고리즘을 풀지 못했다.
• 기초적인 알고리즘부터 까먹었기에 차근차근 복습해나가고자 한다.