SWEA 14361. 숫자가 같은 배수

양의 정수 N을 0으로 시작하지 않는 수로 재배치 하여 N의 배수를 만들 수 있는지 확인하는 문제이다.

 

N의 배수들 중에 N의 자릿수를 넘지 않으면서 재배치하여 만들 수 있는지 확인하기 위해 목표값을 N*2부터 자릿수가 넘지 않을때까지 N을 더하면서 String으로 변환 후, 문자열의 문자들을 비교하여 동일하면 만들 수 있고 아니라면 불가능하게 된다. 비교는 Map<Character, Integer>로 하여 각 문자열의 문자의 갯수를 비교하여 없거나 갯수가 다르면 목표값을 재배치하여 만들 수 없음을 의미한다.

private static boolean contentEqual(String a, String b) {
    Map<Character, Integer> mapB = new HashMap<>();
    for(int i=0; i<a.length(); i++) {
        char currentB = b.charAt(i);
            
        if(mapB.get(currentB) == null) mapB.put(currentB, 1);
        else mapB.put(currentB, mapB.get(currentB)+1);
    }
    for(Character key: mapA.keySet()) {
        if(mapB.get(key) == null) return false;
        if(mapA.get(key) != mapB.get(key)) return false;
    }
    return true;
}

String input = br.readLine();
mapA = new HashMap<>();
for(int i=0; i<input.length(); i++) {
    char current = input.charAt(i);
                
    if(mapA.get(current) == null) mapA.put(current, 1);
    else mapA.put(current, mapA.get(current)+1);
}
int n = Integer.parseInt(input);
int num = n * 2;
int limit = 0;
int mul = 1;
for(int i=1; i<=input.length(); i++) {
    limit += 9*mul;
    mul *= 10;
}
            
while(num <= limit) {
    String number = String.valueOf(num);
    if(contentEqual(input, number)) {
        sb.append("possible").append('\n');
        continue outer;
    }
    num += n;  
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    static Map<Character, Integer> mapA;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        
        outer: for(int tc=1; tc<=T; tc++) {
            sb.append('#').append(tc).append(' ');
            String input = br.readLine();
            mapA = new HashMap<>();
            for(int i=0; i<input.length(); i++) {
                char current = input.charAt(i);
                
                if(mapA.get(current) == null) mapA.put(current, 1);
                else mapA.put(current, mapA.get(current)+1);
            }
            int n = Integer.parseInt(input);
            int num = n * 2;
            int limit = 0;
            int mul = 1;
            for(int i=1; i<=input.length(); i++) {
                limit += 9*mul;
                mul *= 10;
            }
            
            while(num <= limit) {
                String number = String.valueOf(num);
                if(contentEqual(input, number)) {
                    sb.append("possible").append('\n');
                    continue outer;
                }
                num += n;
            }
            sb.append("impossible").append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static boolean contentEqual(String a, String b) {
        Map<Character, Integer> mapB = new HashMap<>();
        for(int i=0; i<a.length(); i++) {
            char currentB = b.charAt(i);
            
            if(mapB.get(currentB) == null) mapB.put(currentB, 1);
            else mapB.put(currentB, mapB.get(currentB)+1);
        }
        for(Character key: mapA.keySet()) {
            if(mapB.get(key) == null) return false;
            if(mapA.get(key) != mapB.get(key)) return false;
        }
        return true;
    }
}