Hackerrank Bigger is greater

Hackerrank Bigger is greater

• 문제 : https://www.hackerrank.com/challenges/bigger-is-greater/problem

source

• 순열의 다음 수를 구하는 문제와 동일.
• 최악의 경우 시간복잡도 O(n 제곱)
• 문제 푸는 방법은 아래 주석에 있고, 간략히 요약하면 turning point 를 찾은 뒤, turning point 보다 크지만 가장 작은 수를 찾는게 핵심
• 아래 테스트케이스 소스도 같이 있음.

public class BiggerIsGreater {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int count = scan.nextInt();
        String[] str = new String[count];
        for (int i = 0; i < count; i++) {
            str[i] = scan.next();
        }

        for (int i = 0; i < count; i++) {
            System.out.println(solve(str[i]));
        }
    }

    /**
     * 1. brute-force
     * - X
     *
     * 2. 규칙으로 풀기.
     * - 일단 맨 끝 알파벳에서 for 문 돌려서 줄어드는 구간을 찾는다.
     * - abdec 라면, c < e, e > d 이니 d 가 줄어드는 구간임.
     * - d 보다 크지만 가장 작은 수를 찾아보자. e 임.
     * - 그럼 e 랑 d 를 바꿈. abedc
     * - 그런 뒤, d 의 위치부터 sorting 한다.
     * - abecd 가 된다.
     *
     * @return
     */
    public static String solve(String input) {
        char[] chars = input.toCharArray();
        int lastIdx = chars.length - 1;
        int minVal = Integer.MAX_VALUE;
        int minIdx = Integer.MAX_VALUE;
        int turningPoint = 0;
        String result = input;
        for (int i = lastIdx; i > 0; i--) {
            /** 작아지는 구간을 찾는다. */
            if (chars[i] > chars[i - 1]) {
                turningPoint = i - 1;
                for (int k = i; k <= lastIdx; k++) {
                    if (chars[turningPoint] < chars[k] && minVal > chars[k]) {
                        minVal = chars[k];
                        minIdx = k;
                    }
                }
                swap(chars, turningPoint, minIdx);
                Arrays.sort(chars, turningPoint + 1, lastIdx + 1);
                result = new String(chars);
                break;
            }

        }

        return input.equals(result) ? "no answer" : result;
    }

    private static void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }
}









import org.junit.Assert;
import org.junit.Test;

import static org.hamcrest.Matchers.is;

public class BiggerIsGreaterTest {

    @Test
    public void solveTest() {
        Assert.assertThat(BiggerIsGreater.solve("abcde"), is("abced"));
        Assert.assertThat(BiggerIsGreater.solve("abced"), is("abdce"));
        Assert.assertThat(BiggerIsGreater.solve("abdce"), is("abdec"));
        Assert.assertThat(BiggerIsGreater.solve("abdec"), is("abecd"));
        Assert.assertThat(BiggerIsGreater.solve("abecd"), is("abedc"));
        Assert.assertThat(BiggerIsGreater.solve("abedc"), is("acbde"));

        Assert.assertThat(BiggerIsGreater.solve("aaa"), is("no answer"));
        Assert.assertThat(BiggerIsGreater.solve("fvincndjrurfh"), is("fvincndjrurhf"));

        Assert.assertThat(BiggerIsGreater.solve("ab"), is("ba"));
        Assert.assertThat(BiggerIsGreater.solve("bb"), is("no answer"));
        Assert.assertThat(BiggerIsGreater.solve("hefg"), is("hegf"));
        Assert.assertThat(BiggerIsGreater.solve("dhck"), is("dhkc"));
        Assert.assertThat(BiggerIsGreater.solve("dkhc"), is("hcdk"));
    }
}