[JAVA] 프로그래머스 LEVEL2 테이블 해시 함수

https://school.programmers.co.kr/learn/courses/30/lessons/147354

프로그래머스

코딩테스트 연습 > 연습문제 > 테이블 해시 함수

 

난이도: LEVEL2

문제 설명

문제를 읽어보고 문제에서 요구하는 그대로를 구현하는 간단한 문제이다. 

 

정답코드1 방식으로 푸는데 필요한 지식 3가지 

 

1. XOR 연산: 배타적 논리합 두 비트가 서로 다르면 1(참) 같으면 0(거짓)

1 0 0 1 

0 1 0 1

1 1 0 0 

 

2. 10진수 → 2진수, 2진수 →  10진수  (진법 변환) 

 

3. 정렬 

정답 코드1

import java.util.*;
// XOR 배타적 논리합 두 비트가 서로 다르면 1(참) 같으면 0(거짓)
class Solution {
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        
        Arrays.sort(data, (o1, o2) ->{
           if(o1[col-1] != o2[col-1]) return o1[col-1] - o2[col-1]; // 오름차순 
           return o2[0] - o1[0]; // 기본키(첫 번째 컬럼) 내림차순  
        });
        row_begin -= 1;
        row_end   -= 1;
        
        int init = sum(row_begin + 1, data[row_begin]);
        String cur = toBinary(init);
        
        for(int i = row_begin + 1; i <= row_end; i++){
            int next_i = sum(i + 1, data[i]);
            String next_s = toBinary(next_i);
            
            int size1 = cur.length();
            int size2 = next_s.length();
            
            if(size1 != size2){
                int size = Math.abs(size1 - size2);
                if(size1 > size2){
                    next_s = addString(size, next_s);
                }
                else{
                    cur = addString(size, cur);
                }
            }
            cur = xor(cur, next_s);
        }
        return calculate(cur);
    }
    public static int calculate(String input){
        int sum = 0;
        int cnt = 0;
        for(int i = input.length() - 1; i >= 0; i--){
            if(input.charAt(i) == '0'){
                cnt++;
                continue;
            }
            sum += Math.pow(2, cnt++);
        }
        return sum;
    }
    
    public static String xor(String input1, String input2){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < input1.length(); i++){
            if(input1.charAt(i) != input2.charAt(i)) sb.append(1);
            else sb.append(0);
        }
        return sb.toString();
    }
    
    public static String addString(int size, String input){
        return "0".repeat(size) + input;
    }
    
    public static int sum(int mod, int [] data){
        int sum = 0;
        for(int i = 0; i < data.length; i++){
            sum += (data[i] % mod);
        }
        return sum;
    }
    public static String toBinary(int input){
        StringBuilder sb = new StringBuilder();
        while(input >= 2){
            sb.append(input % 2);
            input /= 2;
        }
        sb.append(input);
        return sb.reverse().toString();
    }  
}

 

정답코드2 방식으로 푸는데 필요한 지식 3가지 

 

1. stream 연산

 

2. 정렬

 

3. 자바에서 지원하는 정수 xor 연산

int answer = 4 ^ 10; // 배타적 논리합

 

정답 코드2

import java.util.*;
// XOR 배타적 논리합 두 비트가 서로 다르면 1(참) 같으면 0(거짓)
class Solution {
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        
        Arrays.sort(data, (o1, o2) ->{
           if(o1[col-1] != o2[col-1]) return o1[col-1] - o2[col-1]; // 오름차순 
           return o2[0] - o1[0]; // 기본키(첫 번째 커럼) 내림차순  
        });
        row_begin -= 1;
        row_end   -= 1;
        
        int init = sum(row_begin + 1, data[row_begin]);
        
        for(int i = row_begin + 1; i <= row_end; i++){
            int next = sum(i + 1, data[i]); // 나머지 더하기 
            init = (init ^ next); // 배타적 논리합 
        }
        return init; 
    }
    public static int sum(int mod, int [] data){
        return Arrays.stream(data).map(o -> o % mod).sum();
    } 
}