백준 15492 자바 - 뒤집기 (boj 15492 java)

문제 : boj15492

 

  바로 직전에 풀었던 19585번 '전설'의 경우 시도횟수가 18번이었는데, 이번엔 29번이었다 ㅂㄷㅂㄷ... 이번에 포기안하고 계속 시도해본 이유는, 테스트케이스 랜덤 생성기로 400만개를 돌려보니 괜찮은 시간이 나왔기 때문이었다. 결론적으로는 '1 2 3 1 2 3 1 2 3 ...'와 같은 케이스를 제대로 못잡아 내서 시도횟수가 많아졌다(랜덤 생성기라 그런 케이스가 안나오니까)

ㅂㄷㅂㄷ..

 

  풀고 보니 다른 분들은 해싱과 KMP 등으로 풀었다는데, KMP까진 적용이 이해가 됬는데 해싱으로 푼다니 생소하다. 해싱은 'Lexicographically Minimal Cyclic Shift' 라는걸 쓰면 된다고 한다. 처음들어본다.

 

  내 경우엔 실력이 부족하니 몸으로 때워서 해결했다. 시뮬레이션으로 짠 후, 하나씩 시간을 줄일 아이디어를 생각해내면서 점점 시간복잡도를 깎아내는 방식으로 진행했다. 결론적으로는 자바임에도 1초정도까지 땡겼으므로 이것도 하나의 정해로 볼 수 있다(제가 풀었을 때 기준 언어 전체로 봤을 때도 시간 3위).

 

  다이아문제이니 세세한 풀이보다는 메인 로직 및 아이디어 위주로 작성한다.

 

1. 두 부분으로 나누어서 두 부분으로 나누어 각각 순서를 반대로 한 뒤 다시 이어붙인다.

-> 이건 사실 그냥 좀 꼬기위해 추가한 것에 불가하다. 미리 역순으로 입력을 받는다면, 덱에서 좌측껄 빼서 우측으로 넣는 식으로 쉬프트 한다고 쉽게 생각하면 되는 부분이다.

-> 예를들어 '1 2 3'이 입력으로 왔다면, 배열에 '3 2 1'로 넣어두고, 3을 빼서 뒤로 보낸 것(2-1-3)과 또 거기서 좌측을 빼서 뒤로 보낸 것(1-3-2) 중 사전순으로 앞서는걸 생각하면 된다.

 

2. 그렇다면 결국 봐야할 것은 마지막 값을 제외한 나머지 값 중 가장 작은 값들만 보면 된다. 무조건 가장 작은 값이 맨 앞에 와야 하기 때문이다.

-> 마지막 값을 제외해야하는 이유는 '3 2 1'과 같은 입력이 있다면 '1 2 3'이 답으로 생각하기 쉽지만, '0이 아닌 두 부분'으로 나눠야 하므로 '2 3 1'이 답이다.

-> 가장 낮은 값을 가진 위치를 '모두' 알고 있어야 한다. 그걸 'minPos'라고 해보겠다.

 

3. 이제 minPos에 해당하는 값부터, 각각 한 칸씩 전진하면서 더 낮은 값이 나온다면 높은값을 가진건 제외하는 방식으로 진행한다. 예를들어 '3 1 2 1' 이라면 minPos에는 0과 2가 들어있을 것이다(역순으로 1-2-1-3 이므로 가장 낮은 값인 1을 가진 곳 두 곳이 0과 2). 한 번 시뮬레이션을 돌면서 한칸씩 전진 후 확인하면 1-2를 가진 minPos만 남는다. minPos에 남은게 1개이면 거기서부터 출력해주면 된다.

-> 이 때 주의점은, 배열의 끝에 도달했다고 제거하거나 비교를 안하면 안된다. 배열의 끝에 도달한 녀석은 자기자신을 다시 비교해야 한다.

-> 예를들어 역순으로 입력받은값이 '4 1 2 3 1 2 3 1 2 3'이 있다면 minPos는 '1'에서 시작하는 3개가 존재한다. 이후 모두 '1-2-3'을 가지게 되고, 그 다음번에 마지막 minPos는 끝에 도달한다. 그럼 다시 자기 자신의 처음으로 돌아가 '1-2-3'을 봐야 한다. 그럼 첫번째 녀석은 '1-2-3-1-2-3-1-2-3'으로 전체를 돌게 될 것이고, 두번째 녀석은 '1-2-3-1-2-3-반복' 세번째는 '1-2-3-반복'으로 진행된다.

 

4. 문제는 역순으로 봤을 때 '4 1 2 3 1 2 3 1 2 3 4 1 2 3 ...'과 같이 일정한 형태에서 중간에 한 번씩 값이 튀는 경우이다. 이 경우 100만개 이상의 minPos가 생기고, 계속 동일한 값들이 비교되는 중에, '1 2 3 4'가 떴던 minPos만 제거될 것이다. 그럼 나머지 애들끼리 무한히 돌게 된다. 이걸 해결하기 위해 n/[현재 minPos 사이즈]+1 번 이상 돌았다면 멈춰준다. 해당 값 이상 돌았다면 모두 동일한 애들끼리 무한히 돌고 있는게 된다. (이게 통과 가능하게 한 핵심이었다.)

 

5. (여기부터 코드의 78 line에 해당함) 그럼 이제 남은 녀석들은 모두 똑같이 생겼는데, 어딘가 값이 튀는 경우가 있는 녀석들이다. 만약 400만개가 '1 2 3 1 2 3 ...' 모두 이랬다면 78line까지 왔어도 100만개 이상의 minPos가 존재한다. 이 중 하나를 선택해야 한다. 그럼 규칙을 찾아보자.

 

5-1. 역순으로 봤을 때 '4 2 3 4 2 3 4 10 2 3 4'와 같이 튄 값이 minPos 애들이 가진 반복 패턴보다 큰 값인 경우

-> 이 경우 튄 값 바로 뒤의 minPos를 택해야 한다. (그래야 출력을 2 3 4 2 3 4 2 3 4 10 과 같이 큰 값을 뒤로 보낼 수 있다.)

-> 단, 튄 값이 역순으로 맨 뒤에 있다면 맨 처음 패턴을 선택해야 한다.

 

5-2. 역순으로 봣을 때 '4 2 3 4 2 3 4 3 2 3 4'와 같이 튄 값이 작은 값인 경우(2-3-4 패턴에서 4보다 작다.)

-> 이 경우엔 튄 값 바로 직전의 반복 패턴을 선택해야 한다. 그래야 '2 3 4 3 2 4 3 2 4 4 3'와 같이 최대한 앞쪽으로 보낼 수 있다.

 

6. 일단 minPos가 하나로 확정된다면, 출력은 간단하다. 우선 minPos는 이하 코드에서도 동일한 역할인데, from 이라고 맨 처음에 어디서 시작했는지를 기록해뒀다. 따라서 해당 위치부터 n번만큼 배열을 출력해주면 된다. 이 때, 배열 인덱스를 넘어가면 앞쪽으로 보내면 된다. 따라서 for (int i = 0; i < n; i++) print(arr[(from+i)%n]) 와 같은 방식으로 출력해주면 된다.

 

7. 추가로 시간을 더 깎아야 통과가 됬는데,

-> 마지막 값을 제외한 모든 값이 동일한 경우엔 그냥 역순으로 출력한다.

-> n이 짝수일 때 반으로 나눠서 동일하다면 그냥 역순으로 출력한다.

 

 

.... 중간중간 시도해봤던 것 중 크게 의미 없던 시간 깎기들 제외하고 정리한게 위와 같다. kmp나 해싱으로 문자열 대소비교하는 위에서 말한 이상한 무언가를 알고 있는 분이라면 이렇게 손가락이 고생하지 마세요 ㅠ

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    class Pos{
        int from, idx;
        public Pos(int idx) {this.from = idx; this.idx=idx+1;}
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int min = Integer.MAX_VALUE;
        int[] arr = new int[n];
        for (int i = 1; i < n; i++) {
            arr[n-i] = Integer.parseInt(st.nextToken());
            if (arr[n-i] < min)
                min = arr[n-i];
        }
        arr[0] = Integer.parseInt(st.nextToken());

        ArrayList<Pos> minPos = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            if (arr[i] == min) {
                minPos.add(new Pos(i));
            }
        }
        if (minPos.size() == n) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(arr[i]).append(' ');
            }
            System.out.print(sb);
            return;
        }
        if (n%2 == 0) {
            boolean halfSame = true;
            for (int i = 0; i < n/2; i++) {
                if (arr[i] != arr[n/2+i]) {
                    halfSame = false;
                    break;
                }
            }
            if (halfSame) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) {
                    sb.append(arr[i]).append(' ');
                }
                System.out.print(sb);
                return;
            }
        }

        int cnt = 0;
        while (minPos.size()!=1 && cnt<(n/minPos.size())+1) {
            cnt++;
            ArrayList<Pos> tmp = new ArrayList<>();
            min = Integer.MAX_VALUE;
            for (int i = 0; i < minPos.size(); i++) {
                Pos cur = minPos.get(i);
                int see = cur.idx % n;
                if (min > arr[see]) {
                    min = arr[see];
                }
            }
            for (int i = 0; i < minPos.size(); i++) {
                Pos cur = minPos.get(i);
                int see = cur.idx % n;
                if (min != arr[see]) continue;
                cur.idx++;
                tmp.add(cur);
            }
            minPos = tmp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            min = arr[(minPos.get(0).from+i)%n];
            for (int m = 0; m < minPos.size(); m++) {
                int cur = arr[(minPos.get(m).from+i)%n];
                if (min > cur) {
                    ArrayList<Pos> tmp = new ArrayList<>();
                    tmp.add(minPos.get(m));
                    minPos = tmp;
                    break;
                } else if (min < cur) {
                    ArrayList<Pos> tmp = new ArrayList<>();
                    tmp.add(m+1>=minPos.size()?minPos.get(0):minPos.get(m+1));
                    minPos = tmp;
                    break;
                }
            }
            sb.append(min).append(' ');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}