Q. 25758 자바 : 유전자 조합

문제 : 유전자 조합

실버 1 난이도의 문제이다.

 

유전자가 주어지고 이를 조합한다.

두 유전자를 조합하면 첫 번째 유전자의 첫 번째 형질(글자)와 두 번째 유전자의 두 번재 형질(글자)가 붙는다

주의해야 할 점은 들어오는 입력값은 최대 10만개이지만

실제로 유효한 값은 AA - ZZ, 중복 최대 1개 => 26 * 26 * 2 = 1352개이므로 중복 처리가 필요하다.

 

아래와 같은 방식으로 풀었다.

1. 유전자들을 Set에 저장하되, 중복을 한 번은 허용해야 하므로

만약 중복된 값이 들어온다면 중복 값들을 저장한 Set에 추가한다. (두 번 까지만 고려하면 된다)

 

2. 유전자들을 문제 조건에 따라 섞는다.

이 때 중복해서 들어온 유전자를 따로 처리하면 시간을 좀 더 줄일 수 있다

 

3. 문제 조건에 따라 표현형을 계산한다

 

4. 문제 조건에 따라 알파벳 순서대로 정렬해서 출력한다

 

이 문제에서 시간 복잡도를 계산하면,

1. 입력값 저장 - O(100,000)

2. 유전자 조합 - O(26 * 26 * 2 = N이라고 가정)

3. 표현형 계산 - O(N)

4. 정렬 - O(N log N)

 

이 문제는 위 연산이 모두 독립적이므로 시간 초과는 걱정하지 않아도 된다.

비둘기집 원리라는게 생소해서 예전에 찾아봤었는데

입력값에 비해 유효한 값이 작아서 이를 처리해줘야 하는 내용이었던 것으로 기억한다.

나름 어렵게 풀었던 문제였고 풀이와 시간은 아래와 같다.

import java.io.*;
import java.util.*;

public class Main {

    static StringBuilder sb = new StringBuilder();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int N;

    static ArrayList<String> InputList, SameList;

    static HashSet<String> MixSet;

    static void input() throws IOException
    {
        N = Integer.parseInt(br.readLine());
        //InputList = new ArrayList<>();
        st = new StringTokenizer(br.readLine());

        // 입력값을 넣을 Set
        HashSet<String> inputSet = new HashSet<>(); 

        // 중복된 입력값을 넣을 Set
        HashSet<String> sameSet = new HashSet<>();
        while (N-- > 0) {
            String s = st.nextToken();
            // 입력값 Set에 넣고, 
            // 만약 중복이라면 중복 Set에 넣음
            // (중복값일 경우 add의 return값이 false)
            if (!inputSet.add(s)) sameSet.add(s);
        }
        InputList = new ArrayList<>(inputSet);
        SameList = new ArrayList<>(sameSet);
        // 입력값의 수는 10000만이지만, 실제로 가능한 입력값은
        // aa - zz -> 26 * 26,
        // 중복된 값이 들어올 수 있으므로 * 2
        // 이후 중복값은 무시됨
        // 즉 가능한 경우의 수는 26 * 26 * 2 = 1352가 최대
        MixSet = new HashSet<>();
    }

    static void pro()
    {
        // 가능한 조합은 문자를 앞 / 뒤에 붙일 수 있으므로 고려
        mix();
        LinkedList<Character> printType = calPrintType();
        sb.append(printType.size()).append('\n');
        for (char c : printType) {
            sb.append(c).append(' ');
        }
        System.out.println(sb);
    }

		
    static void mix() { 
    	// 가능한 모든 조합의 수
		// 다른 유전자끼리 합쳐도 동일한 유전자가 나올 수 있으므로
		// 중복 제거를 위해 Set에 입력

        for (int i = 0; i < InputList.size() - 1; i++) {
            for (int j = i + 1; j < InputList.size(); j++) {
                String a = InputList.get(i);
                String b = InputList.get(j);
                MixSet.add(a.charAt(0) + "" + b.charAt(1));
                MixSet.add(b.charAt(0) + "" + a.charAt(1));
            }
        }
        
        // 중복되서 들어온 유전자의 경우
        // 동일한 형질끼리 섞을 경우만 더함
        // 다른 형질은 이미 위에 반복문에서 처리됨
        for (int i = 0; i < SameList.size(); i++) {
            String s = InputList.get(i);
            MixSet.add(s.charAt(0) + "" + s.charAt(1));
            MixSet.add(s.charAt(1) + "" + s.charAt(0));
        }
    }

    // 출력 타입을 계산하는 함수
    // 문제 조건대로 하지만, 위와 동일하게 중복 제거를 위해 Set에 입력
    // 마지막에 알파벳 순으로 출력하라 했으므로 정렬해서 반환
    static LinkedList<Character> calPrintType() {

        HashSet<Character> printType = new HashSet<>();
        for (String s : MixSet) {
            char front = s.charAt(0);
            char back = s.charAt(1);
            if (front > back) printType.add(front);
            else if (front < back) printType.add(back);
            else printType.add(back);
        }
        LinkedList<Character> sortList = new LinkedList<>(printType);
        Collections.sort(sortList);
        return sortList;
    }


    public static void main(String[] args) throws Exception{

        input();
        pro();
    }

}