hackerreath: 한 단어의 사전 순위

8366 단어 discuss algorithms career java

이것은 일련의 리코더와 기타 정성스럽게 기획된 해결 방안 해석 (인덱스) 의 일부분이다.
만약 당신이 이 해결 방안을 좋아하거나 그것이 유용하다고 생각한다면, 이 댓글을 좋아하세요.

HackerEarth Problem (Medium): Rank of a Word

어순

문제.

찰은 배열과 조합을 연구하고 있다.그는 한 문제에 깊이 빠져들었다. 이 문제는 단어 S의 사전 순위 계산을 요구한다. (사전은 S에 존재하는 자모표만 포함하고 사전의 모든 단어는 S의 길이와 같으며 자모표의 수량은 S와 같다)
계산 과정에 관해서는 주어진 링크를 참고하십시오: - 단어의 순위
너의 임무는 매우 간단하다. Cham이 단어의 등급을 계산하는 것을 돕는다.

솔루션

Rank of a word is basically deduced from making all combinations of the alphabets from the given word - sorting them in order as in dictionary and checking the position of our given word.

예: word=BALL

가능한 모든 조합 = 4/2! (L 2회) = 12

정렬->[A, B, L, L]

 1 : ABLL
 2 : ALBL
 3 : ALLB
 4 : BALL  -- this is our desired word
 5 : BLAL
 6 : BLLA
 7 : LABL
 8 : LALB
 9 : LBAL
10 : LBLA
11 : LLAB
12 : LLBA

그래서 순위가 4입니다.
우리는 몇 가지 예를 들어 그것을 더욱 잘 이해할 수 있다.
우리'비'와'축구'부터 시작합시다.
비라는 단어는 네 개의 자모표가 있는데, 모두 다르다.따라서 "RAIN"이라는 단어를 사용하는 모든 알파벳으로 만들 수 있는 단어의 수는 4!=24이다.
유사하게 축구라는 단어는 여섯 개의 자모가 있는데 그 중 두 개는 비슷하다(C는 두 번 반복).따라서'SOCCER'라는 단어를 사용하는 모든 알파벳으로 만들 수 있는 단어의 수는 6!/2! = 360이다.
이게 첫걸음이야.

단계1: 주어진 단어의 모든 자모표를 사용하여 형성할 수 있는 단어의 총수를 찾아낸다.

일단 네가 이 점을 해낸다면, 너의 다음 단계는 바로 시간 순서에 따라 단어의 자모표를 배열하는 것이다.따라서 단어 비의 자모는 {A, I, N, R},'soccer'의 자모는 {C,C,E,O,R,S}으로 배열해야 한다.주의해야 할 것은 C가 축구 경기에서 두 번 나왔기 때문에 여기도 두 번 써야 한다는 것이다.이것은 너의 두 번째 걸음이다.

2단계: 단어의 모든 자모를 알파벳순으로 배열한다.만약 원래 단어에서 중복된 자모가 매우 적다면, 여기서 같은 횟수를 중복하십시오.

이제 우리는 큰 물고기를 가지러 갈 준비가 되었다.만약 우리가 반드시'비'와'축구'라는 두 단어 자체의 등급을 찾아야 한다고 가정한다.

{A,I,N,R}

A 를 선택하세요. 일단 완성되면 세 개의 다른 자모표가 남습니다. 그 중에서 3 = 을 형성할 수 있습니다.여섯 글자.하지만 이 단어들이 모두 비일 수는 없다. 비의 별은 A가 아니라 R이기 때문이다. 그래서 순위가 1부터 6이 아니라는 것을 확신할 수 있다.(동의하십니까?)
다음 단계는 I를 선택하라. 일단 이렇게 하면 세 개의 다른 자모표가 남는다. 그 중에서 3!=6개의 단어가 형성될 수 있다. 그 중 비는 I가 아니라 R로 시작하기 때문이다. 이 단어의 순위는 7에서 12 사이가 아니라는 것은 확실하다.(동의하십니까?)
마찬가지로 우리는 다음에 N을 선택할 것이다.'비'라는 단어의 순위는 13에서 18까지 다양하다.
우리는 지금 R을 받으러 왔습니다. 현재 우리의 순서에는 {A, I, N}만 남았습니다.형성할 수 있는 여섯 단어는요.

Rain
Rani
Rian
Rina
Rnai
Rnia

빗물이 이 6개 종목 중 첫 번째, 18개 종목에 이어 첫 번째인 것은 분명하다.그래서 비라는 단어의 순위는 19다.

{C,C,E,O,R,S}

C를 선택하세요. 일단 이렇게 하면 나머지 5개의 자모가 달라집니다. 5!=120개의 단어를 만들 수 있습니다.그러나 이 단어들은 모두 축구라고 할 수 없다. 축구는 C가 아니라 S에서 시작되기 때문이다. 그래서 당신은 1에서 120 사이의 순위를 매우 확정할 수 있다.(동의하십니까?)
두 번째 C를 선택할 필요가 없습니다. 이미 하나를 선택했기 때문입니다.(이것은 학생들이 가장 흔히 볼 수 있는 실수 중의 하나이다).
다음 단계에서 E를 선택하세요. 만약 당신이 이렇게 한다면, 당신은 지금 5개의 자모표를 남깁니다. 그 중 2개는 비슷합니다.이에 따라 E로 시작할 수 있는 단어 수는 5!/2!=60으로 축구가 될 만한 단어는 하나도 없었다.이 때문에 121부터 180까지 순위가 없다.
마찬가지로 O를 선택하면 181부터 240까지 랭킹이 불가능하다고 말할 수 있다.R을 선택하면 241부터 300까지 랭킹이 불가능합니다.
마지막으로 (바위가 도착했어...) s를 선택하겠습니다.
현재 우리는 {C,C,E,O,R}이 있다.C를 두 번째 자모로 선택했습니다. 4!=24개의 단어는 현재 SC로 시작합니다. 301에서 324 사이에는 어떤 단어도 있을 수 없습니다.
E=4!/2! = 12->를 선택하면 마찬가지로 랭킹 325~336은 SE가 결정한다.
지금, 우리는 337에서 348까지.우리의 축구공은 바로 여기에 있다.다행히도 지금 알파벳순으로 줄을 서면 축구 랭킹 337위를 발견할 수 있을 것이다.

구현

따라서 이론은 이미 완성되었다. 코드에서 그것을 볼 수 있게 한다. (이것은 유일하고 중복된 상황을 처리할 것이다.)

모든 캐릭터 및 출현 맵 만들기

    public static long findRank(String word) {
        long rank = 1;
        long suffixPermCount = 1;
        final Map<Character, Integer> charCounts = new HashMap<>();

        for (int i = word.length() - 1; i >= 0; i--) {
            char x = word.charAt(i);
            int xCount = charCounts.containsKey(x) ? charCounts.get(x) + 1 : 1;

            charCounts.put(x, xCount);

            for (Map.Entry<Character, Integer> e : charCounts.entrySet()) {
                if (e.getKey() < x) {
                    rank += suffixPermCount * e.getValue() / xCount;
                }
            }

            suffixPermCount *= word.length() - i;
            suffixPermCount /= xCount;
        }

        return rank;
    }