[JAVA/프로그래머스]두 정수의 짝꿍 찾기: 알고리즘 문제 해결 방법

이 글에서는 두 정수 X, Y에서 공통된 숫자를 이용해 만들 수 있는 가장 큰 정수, 즉 '짝꿍'을 찾는 알고리즘 문제의 해결 방법을 상세하게 설명합니다.

algorithm-problem-solving-find-pair
소개: 두 정수의 공통된 숫자를 이용해 '짝꿍'을 찾는 문제는 언뜻 보기에 단순하지만, 효율적인 해결 방법을 요구합니다.

두 정수의 짝궁

 

글에서는 자바를 사용한 알고리즘 문제 해결 과정을 통해, 문자열 처리와 해시맵을 활용하는 방법을 배워봅

 

두 정수 X와 Y가 주어졌을 떄 , 이 두 수에서 공통으로 나타나는 숫자들만을 이용하여 만들 수 있는 가장 큰 정수를 찾는 것이 목표입니다. 이때, 공통 숫자가 전혀 없다면 '-1'을, 공통 숫자가 있으나 0만으로 구성되어 있다면 '0'을 반환해야 합니다. 이 문제의 핵심은 두 가지입니다. 먼저, 두 수에서 공통된 숫자를 효율적으로 찾는 것, 그리고 찾은 숫자들을 정렬하여 최대값을 구성하는 것입니다.

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.stream.Collectors;

class Solution {
    public String solution(String X, String Y) {
        HashMap<String, Integer> Ymap = new HashMap<>();
        HashMap<String, Integer> Xmap = new HashMap<>();

        for(int i=0; i<Y.length(); i++){
            String Yvalue = String.valueOf(Y.charAt(i));
            Ymap.put(Yvalue,  Ymap.getOrDefault(Yvalue ,0)+1);
        }

        for(int i=0; i<X.length(); i++){
            String Xvalue = String.valueOf(X.charAt(i));
            Xmap.put(Xvalue,  Xmap.getOrDefault(Xvalue ,0)+1);
        }

        String distin = X.chars() // IntStream 생성
                .distinct() // 중복 문자 제거
                .mapToObj(c -> String.valueOf((char) c)) // 각 int를 char로 변환 후 String으로 매핑
                .collect(Collectors.joining()); // 결과를 하나의 문자열로 결합

        ArrayList<String> temp = new ArrayList<>();

        for(int i=0; i<distin.length(); i++){
            String v = String.valueOf(distin.charAt(i));
            if(Xmap.get(v) != null && Ymap.get(v) != null){
                for(int j=0; j<Math.min(Xmap.get(v), Ymap.get(v)); j++){
                    temp.add(v);
                }
            }
        }

        Collections.sort(temp , Collections.reverseOrder());
        
        if(temp.size() == 0){
            return "-1";
        }
        
        StringBuilder answer = new StringBuilder();
        for(String a : temp){
            answer.append(a);
        }
        
        if(answer.toString().matches("0*")){
            return "0";
        }
        
        return answer.toString();
    }
}

 

1.해시맵을 사용한 데이터 저장

 

두 수 X,Y 각각에 대해 나타나는 숫자들의 빈도수를 저장하기 위해 해시맵을 사용합니다. 이는 각 숫자가 몇 번 나타났는지 빠르게 찾아내고, 공통 숫자의 최소 빈도수를 계산하는 데 유용합니다. 이렇게 하지않으면 for 문으로 하나씩 찾게 되면 건수가 많을때 시간 오류가 나타날수도 있습니다.

 

2.공통 숫자의 정렬

 

찾아낸 공통 숫자들을 큰 숫자부터 작은 숫자 순으로 정렬합니다. 이떄, 자바의 'Collection.sort()' 메소드와 'Collections.reverseOrder()' 를 활용하여 내림차순 정렬을 실행 합니다.

 

3.최종 문자열의 구성

 

정렬된 공통 숫자들을 이어 붙여 최종 문자열을 구성합니다. 이 문자열이 바로 두 수의 '짝꿍' 입니다. 단, 만약 공통 숫자가 0밖에 없다면. ' 0'을 반환합니다.

 

결론

이 문제를 해결하기 위해서는 해시맵을 활용한 데이터 저장을 하여서 최대한 효율적으로 접근을 해야 합니다.

처음에는 'ArrayList' 의 'indexof' 를 이용하여 순회하면서 해당 객체를 찾았지만 리스크의 크기가 커질수록 성능에 영향을 줘서 주의를 해야합니다.