[JAVA 알고리즘] 알파벳 재정렬 (중간고사)

자바의 개념과는 거리가 살짝 있는 문제가 나와 많이 당황했지만..!

충분히 나중에도 적용할 만한 개념들이 있을 것 같아서 포스팅을 하려고 한다.

 

문제는 다음과 같다.

 

문제 

영어 단어 하나를 입력 받아 이 단어에 있는 알파벳을 재정렬해서 만들 수 있는 단어의 개수를 구하라. 단, 소문자만 입력 가능하다.

 

실행 시간

1초 이내

 

입력 예시

noon

 

출력 예시

 6

 

 

Hint

위 예제의 경우 가능한 단어는 nnoo, nono, noon, onno, onon, oonn이다.

 

 

아이디어

같은 원소가 있는 순열의 경우의 수를 구하는 방식으로 풀었다.

N개의 원소에서 q, p, r개 만큼 같은 원소가 있는 경우 N! / (p! * q! * r!) (p + q + r = N)

같은 원소를 판별하는 방법은 입력된 값의 아스키 코드에서 97을 빼주어 배열의 인덱스 값으로 사용하였다.

 

 

소스코드

/*
 * 목적 : 알파벳을 재배열해 만들어질 수 있는 단어의 개수를 구한다.
 * 제작일 : 2020.05.**
 * 제작자 : ***
 */
package test;
 
import java.util.Scanner;
 
public class Counting {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        System.out.print("단어를 입력하라 : ");
        int ans = 1;
        int list_size = 26;
        int[] list = new int[list_size];
        String alpha = sc.nextLine();
        for(int i = 0; i < alpha.length(); i++) { // 원소 확인
            int alpha_chk = (int)alpha.charAt(i) - 97; // 아스키코드로 처리
            list[alpha_chk]++;
        }
        for(int i = 1; i <= alpha.length(); i++) { // 분자
            ans *= i;
        }
        
        for(int i = 0; i < 26; i++) {
            int temp = 1;
            if(list[i] > 0) {
                for(int j = list[i]; j > 0; j--) {
                        temp *= j;
                    }
                ans = ans / temp;
            }
        }
        System.out.print("결과 : " + ans);
    }
}
 

총평

맨 처음 문제를 봤을때, 입력의 한계가 정해지지 않았는데 어떻게 1초 안에 답을 내라는 건지 이해가 되지 않았지만,

시험 종료 이후 그 부분에 대한 의견이 나오지 않은 것으로 보아 다들 그 부분까지 생각하지는 못한것 같다.

언어가 조금 달랐을 뿐 큰 맥락은 같아서, 나쁘지 않게 푼 것 같다.