[백준 25758] 유전자 조합

자바 연습 겸 자바로 품

자바혐오증 걸릴듯 ㅇㅇ

 

초반에 그냥 BitSet으로 존재여부만 파악했는데

특정 유전자가 중복으로 존재하면 자기보다 낮지 않아도 발현될 수 있다는걸 뒤늦게 깨달음

AA AA 이렇게 있으면 A가 발현됨

 

그래서 HashMap 사용해서 품

HashMap이랑 HashSet 사용하는게 핵심이라 자료구조 탭에 넣어둔다

 

참고로 HashSet 사용한 이유는 중복되지 않는 배열을 막판에 받기 위해서인데

c++이면 그냥 unique하면 되는데 자바는 또 unique를 지원하지 않는다

그래서 HashSet으로 받고 ArrayList로 바꿔서 sort 해주었다.

 

다 풀고 c++로도 풀어보았다 

맨 마지막 코드가 c++ 코드

 

---

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashSet<Character> ans = new HashSet<>();

        HashMap<Character, Integer> first = new HashMap<>();
        HashMap<Character, Integer> second = new HashMap<>();

        int N = Integer.parseInt(br.readLine());
        String[] dna = br.readLine().split(" ");
        for(int i=0;i<N;i++){
            char dna1 = dna[i].charAt(0);
            char dna2 = dna[i].charAt(1);
            if(first.containsKey(dna1)){
                if(first.get(dna1)==1) first.put(dna1, 2);
            }else{
                first.put(dna1, 1);
            }

            if(second.containsKey(dna2)){
                if(second.get(dna2)==1) second.put(dna2, 2);
            }else{
                second.put(dna2, 1);
            }
        }

        // 1번째 놈들 검사
        for(int i=0;i<N;i++){
            char curdna = dna[i].charAt(0);
            char notavailable = dna[i].charAt(1);

            for(Character key : second.keySet()){
                if(key==notavailable && second.get(key)==1) continue;
                if(key <= curdna) {
                    ans.add(curdna);
                    break;
                }
            }
        }

        // 2번째 놈들 검사
        for(int i=0;i<N;i++){
            char curdna = dna[i].charAt(1);
            char notavailable = dna[i].charAt(0);

            for(Character key : first.keySet()){
                if(key==notavailable && first.get(key)==1) continue;
                if(key <= curdna) {
                    ans.add(curdna);
                    break;
                }
            }
        }

        ArrayList<Character> list = new ArrayList<>(ans);
        Collections.sort(list);

        System.out.println(list.size());
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i)+" ");
        }
    }
}

 

---

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	vector<string> v;
	unordered_set<char> ans;
	unordered_map<char, int> first, second;

	int N; cin >> N;

	string input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		v.push_back(input);
		char dna1 = input[0];
		char dna2 = input[1];

		first[dna1]++;
		second[dna2]++;
	}
	
	// 1번째 놈 확인
	for (int i = 0; i < N; i++) {
		char target = v[i][0];
		char notavailable = v[i][1];
		
		for (auto it = second.begin(); it!=second.end();it++){
			if ((*it).first == notavailable && (*it).second == 1) continue;
			else if((*it).first <= target){
				ans.insert(target);
				break;
			}
		}
	}

	// 2번째 놈 확인
	for (int i = 0; i < N; i++) {
		char target = v[i][1];
		char notavailable = v[i][0];

		for (auto it = first.begin(); it != first.end(); it++) {
			if ((*it).first == notavailable && (*it).second == 1) continue;
			else if((*it).first <= target){
				ans.insert(target);
				break;
			}
		}
	}

	vector<char> temp(ans.begin(), ans.end());
	sort(temp.begin(), temp.end());
	cout << temp.size() << "\n";
	for (char ch : temp) cout << ch << " ";

	return 0;
}