개발자 톡
연습문제 톡
CPTI
java 정답 코드
- 등록일
- 2025-01-24 18:08:17
- 조회수
- 426
- 작성자
- tjsqls2067
O(N^2) 버전
import java.util.*; // 1.982s , 31.03MB public class Main_N_Squre { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); // CPTI 입력 받기 int[] cptiList = new int[N]; for(int i = 0; i < N; i++) { String cpti = sc.next(); cptiList[i] = Integer.parseInt(cpti, 2); } // 전체 친밀감을 느끼는 쌍의 수 계산 int totalPairs = 0; for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { // XOR 연산으로 다른 비트 수 계산 int diffBits = Integer.bitCount(cptiList[i] ^ cptiList[j]); // 다른 비트가 2개 이하면 친밀감을 느끼는 쌍 if(diffBits <= 2) { totalPairs++; } } } System.out.println(totalPairs); } }
O(NM^2) 버전
import java.io.*; import java.util.*; /* - 요구사항 - 최대 두 가지 영역에서만 성격이 다르면 친밀감 느낌 - 동일, 1개 다름, 2개 다름 - 서로 친밀감을 느끼는 사람 쌍의 수 계산 - 사람 쌍은 순서를 고려하지 않음 */ // 1.089s, 65.86MB public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int[] cptiList = new int[N]; HashMap<Integer, Integer> cptiMap = new HashMap<>(); for(int i = 0; i < N; i++){ cptiList[i] = Integer.parseInt(sc.next(),2); cptiMap.put(cptiList[i],cptiMap.getOrDefault(cptiList[i], 0) + 1); } int ssang = 0; HashSet<Integer> checkedCptiSet = new HashSet<>(); for(final int curCpti : cptiMap.keySet()){ HashSet<Integer> otherSet = new HashSet<>(); // 1. 동일한 경우 otherSet.add(curCpti); // 2. 한 영역만 다른 경우 for(int i = 0; i < M; i++){ final int oneDiffCpti = curCpti ^ (1 << i); if(cptiMap.containsKey(oneDiffCpti) && !checkedCptiSet.contains(oneDiffCpti)){ otherSet.add(oneDiffCpti); } } // 3. 두 영역만 다른 경우 for(int i = 0; i < M; i++){ for(int j = i + 1; j < M; j++){ final int twoDiffCpti = curCpti ^ ((1 << i) + (1 << j)); if(cptiMap.containsKey(twoDiffCpti) && !checkedCptiSet.contains(twoDiffCpti)){ otherSet.add(twoDiffCpti); } } } // 쌍으로 생성가능한 조합 순회하며 개수 더하기 for(final int otherCpti : otherSet){ if(otherCpti == curCpti){ int curCptiCnt = cptiMap.get(curCpti); if(curCptiCnt > 1){ ssang += (int)((curCptiCnt - 1) + 1) * ((curCptiCnt -1) / 2.0); } }else{ ssang += cptiMap.get(otherCpti) * cptiMap.get(curCpti); } } checkedCptiSet.add(curCpti); } System.out.println(ssang); } }
#CPTI