[백준 6603번][Java] 로또 - 백트래킹, 정렬

www.acmicpc.net/problem/6603

6603번: 로또

 

 

완전 탐색을 통해 조합을 찾고, 조합들을 문자열로 변환해 set에 저장합니다.

그리고 set에 저장된 문자열을 다시 정렬해 출력합니다.

 

주목할만한 부분은 Comparator 구현 코드입니다.

"1 2 3 10 11", "1 2 3 4 5" 과 같은 문자열 두 개가 있다고 할 때, 이 두 문자열을 사전식으로 정렬하려면 단순하게 제공되는 라이브러리만으로는 정렬할 수 없습니다. 그냥 Arrays.sort를 이용하면 "1 2 3 10 11", "1 2 3 4 5" 순으로 정렬됩니다.

그 이유는 자바에서 객체들의 우선 순위를 비교하기 위해서 Comparable 인터페이스의 compareTo 와 같은 메서드를 이용합니다.

문자열 비교의 경우 앞에서부터 차례대로 하나의 문자의 아스키 코드 값을 비교하는데 1 2 3 4 5의 4는 1 2 3 10 11에서 10의 1에 대응되기 때문에 1 2 3 10 11이 먼저 나오게 됩니다.

 

그렇기 때문에 커스텀 Comparator를 구현해서 제공해야 됩니다.

구현 방식은 문자열들을 공백을 기준으로 나눠 숫자로 변환한 다음 서로 비교합니다.

 

 

 

 

...

/*
백준 6603번 - 로또
https://www.acmicpc.net/problem/6603
*/
public class Main {
	static HashSet<String> set;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader("testcase.txt");

		while (true) {
			String line = reader.readLine();
			if (line.equals("0")) break;

			StringTokenizer st = new StringTokenizer(line);
			int k = Integer.parseInt(st.nextToken());
			int[] numArr = new int[k];
			for (int i = 0; i < k; i++) {
				numArr[i] = Integer.parseInt(st.nextToken());
			}
			set = new HashSet<>();
			findNumberSet(0,0,new ArrayList<>(), numArr);

			StringBuilder sb = new StringBuilder();
			String[] subsets = new String[set.size()];
			set.toArray(subsets);

			Comparator<String> comparator = (s1, s2) -> {
				StringTokenizer st1 = new StringTokenizer(s1);
				StringTokenizer st2 = new StringTokenizer(s2);

				while(st1.hasMoreTokens() && st2.hasMoreTokens()) {
					int n1 = Integer.parseInt(st1.nextToken());
					int n2 = Integer.parseInt(st2.nextToken());

					if(n1 > n2) return 1;
					if(n1 < n2) return -1;
				}
				return 0;
			};

			Arrays.sort(subsets, comparator);
			Arrays.stream(subsets).forEach(e -> sb.append(e+"\n"));
			sb.deleteCharAt(sb.length()-1);

			System.out.println(sb.toString());
			System.out.println();
		}
	}

	private static void findNumberSet(int here, int cnt, List<Integer> nums , int[] numArr) {
		if(cnt == 6) {
			String subset = nums.stream().map(n -> String.valueOf(n))
					.reduce((n1, n2) -> n1 + " " + n2).get();
			set.add(subset);
		}
		if(here == numArr.length) return;

		//포함하지 않는 경우
		findNumberSet(here+1, cnt, nums, numArr);

		//포함하는 경우
		nums.add(numArr[here]);
		findNumberSet(here+1, cnt+1, nums, numArr);
		nums.remove(nums.size()-1);
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}