Lexicographical permutation (순열)

Study/알고리즘2019.01.09 15:20

오늘 Hackerrank  에서 문자열 배열 문제를 풀다가 특이해서 포스팅을 해본다. 문자 아스키 값이 큰 값을 순으로 정렬하는 문제였다.

단순한 문제 지만, 결과값이 예상을 빗나갔다.


문제 사이트


Sample Input 0

5
ab
bb
hefg
dhck
dkhc

Sample Output 0

ba
no answer
hegf
dhkc
hcdk


이해가 되지만   이건 이상하다.



문자열 배열에 규칙이 있는 것 같다.  보충학습이 필요하다.  여기 링크를 참고하라!

알고리즘 (https://www.nayuki.io/page/next-lexicographical-permutation-algorithm)

(0, 1, 2, 5, 3, 3, 0)

다음 순열을 계산할 때 순서 를 가능한 한 적게 "증가시켜야"한다는 것 입니다. 
숫자를 사용하여 계산할 때와 마찬가지로 가장 오른쪽 요소를 수정하고 왼쪽을 변경하지 않습니다.

를들어 (0, 1) --> (0, 2) 

1) 증가하지 않는 가장 긴 마지막 값을 찾는다. 

(0, 1, 2, 5, 3, 3, 0) 에서  (5, 3, 3, 0) 이 속성이 있는 접미사이다.
이 접미어는 이미 가장 높은 순열이므로 수정만 하면 다음 순열을 만들 수 없다.
그러므로 왼쪽에 있는 일부 요소를 수정해야 한다.

2) 접미사의 왼쪽에 있는 원소가 피봇이다.
(전체 시퀀스가 증가하지 않는 다면, 이것은 이미 마지막 순열이다.)
 피벗은 필연적으로 접미사의 머리보다 작습니다 (이 예에서는 5입니다). 
따라서 접미사의 일부 요소가 피벗보다 큽니다.  

그림으로 표현한다면 이렇다!

Pseudo code

  1. Find largest index i such that array[i − 1] < array[i].
    (If no such i exists, then this is already the last permutation.)

  2. Find largest index j such that j ≥ i and array[j] > array[i − 1].

  3. Swap array[j] and array[i − 1].

  4. Reverse the suffix starting at array[i].


C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <stdio.h>
#include <iostream>
#include <string>
#include <limits>
using namespace std;
 

//    [0,1,2,5,3,3,0] --> [0,1,3,0,2,5,3]
string biggerIsGreater(string w) 
{
    
//find longest suffix
    size_t length = w.size();
    string newW = w;
    
    size_t i = length -1;
   
     while(i > 0 && newW[i - 1>= newW[i])
    {
        i--;         // 순환
    }
    
    if(i == 0)
      return "no answer";
    // find pivot & swap pivot
    size_t j = length -1;
     // right pivot :
    while( newW[i - 1>= newW[j])
    {
        --j;    
    }
    
    char tmp = newW[i -1];
    newW[i - 1= newW[j];
    newW[j] = tmp;
    // swap suffix
    while(i < j)
    {
        tmp = newW[i];
        newW[i] = newW[j];
        newW[j] = tmp;
        i--;
        j++;
    }
  
    
  return newW;
}
 
int main()
{
    int T;
    cin >> T;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    for (int T_itr = 0; T_itr < T; T_itr++)
    {
        string w;
        getline(cin, w);
        string result = biggerIsGreater(w);
        cout << result << "\n";
    }
    return 0;
}
cs

  



'Study > 알고리즘' 카테고리의 다른 글

Queen's Attack 2 : Chess game - 생각하기  (0) 2019.01.10
Queen's Attack 2 : Chess game  (0) 2019.01.10
Lexicographical permutation (순열)  (0) 2019.01.09
Depth First Search 코드로 만들기  (0) 2018.08.28
Tree search  (0) 2018.08.28
LongestWord - C++  (2) 2018.02.20

작성자

Posted by 비타오백

관련 글

댓글 영역

티스토리 툴바