백준 17162 자바 - 가희의 수열놀이 (Small) (BOJ 17162 JAVA)

문제 : boj17162

 

 

  mod가 최대 10^2라서 뭐 복잡한 알고리즘 필요없이 풀 수 있다. 결국 나누었을 때 0, ..., mod-1인 수가 어느 idx 위치에 있냐가 중요하다. 이걸 빨리 알 수 있으면 되는건데, mod가 10^2이니깐 대충 O(Q * mod) 정도의 시간복잡도만 가져도 풀 수 있다. 그럼 해볼만한게 많이 있다.

 

  내 경우엔 어차피 맨 뒤에서만 수가 추가되고 빠지니 스택을 사용했다. 그리고 mod개 만큼의 스택을 마련했다. 스택배열을 arr이라고 하고, 현재 넣을 위치를 idx라고 하겠다. 그럼 각 쿼리에 대해 다음과 같이 대응할 수 있다.

 

---

[ 쿼리 : 1 num ]

  arr[num % mod]에 num을 추가하고 idx++ -> O(1)

 

[ 쿼리 : 2 ]

  최대 10^2개인 arr을 전부 peek 해보면서 idx-1 값을 가진 스택을 pop한다. 그리고 idx--  -> O(mod)

이건 메모리를 좀 더 써서 HashMap같은걸로 (key, value) = (num, num%mod)를 유지한다면 더 빠르게 구할 수 있다. 하지만 내 경우엔 어차피 쿼리 '3'을 처리하는게 O(mod)만큼 필요하므로, 굳이 메모리 복잡도를 올리지 않기 위해 제외했다.

 

[ 쿼리 : 3 ]

  arr[0]부터 arr[mod-1] 까지 확인하면서 이 중 빈 스택이 있다면 -1이다. 그렇지 않다면 peek을 해봐서 넣었던 idx 중 최소인 값을 찾는다. 최종적으로 '현재 idx - 찾은 최소 idx'가 답이다. -> O(mod)

 

---

 

  그리고 저런 쿼리가 총 Q개 있으므로 총 O(Q*mod)의 시간복잡도를 가지게 된다.

 

  예시로 다음의 테스트케이스를 한번 그림으로 그려봤다.

8 4
1 2
1 3
1 4
3
2
1 16
1 1
3

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Stack;

public class Main extends FastInput {
    private void solution() throws Exception {
        int q = nextInt();
        int mod = nextInt();
        Stack<Integer>[] arr = new Stack[mod];
        for (int i = 0; i < mod; i++) arr[i] = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        while (q-->0) {
            switch (nextInt()) {
                case 1 :
                    int num = nextInt();
                    arr[num%mod].push(idx++);
                    break;
                case 2 :
                    for (int i = 0; i < mod; i++) {
                        if (!arr[i].isEmpty() && arr[i].peek() == idx-1) {
                            arr[i].pop();
                            idx--;
                            break;
                        }
                    }
                    break;
                case 3 :
                    int min = Integer.MAX_VALUE;
                    for (int i = 0; i < mod; i++) {
                        if (arr[i].isEmpty()) {
                            min = -1;
                            break;
                        }
                        if (arr[i].peek() < min) {
                            min = arr[i].peek();
                        }
                    }
                    sb.append(min==-1?min:idx-min).append('\n');
                    break;
            }
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 10;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}