백준 영화 수집(3653)

영화 수집

1. 힌트

1)

2)

3)

2. 접근

1) 비슷한 문제를 풀어본 적이 있던가?

2) 단순한 방법에서 시작할 수 있을까?

3) 내가 문제를 푸는 과정을 수식화할 수 있을까?

4) 문제를 단순화할 수 없을까?

5) 그림으로 그려볼 수 있을까?

6) 수식으로 표현할 수 있을까?

7) 문제를 분해할 수 있을까?

8) 뒤에서부터 생각해서 문제를 풀 수 있을까?

9) 순서를 강제할 수 있을까?

10) 특정 형태의 답만을 고려할 수 있을까?

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder ans = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int[] S = new int[M]; // 보려고 하는 영화
			int[] P = new int[N]; // 현재 가지고 있는 i번째 영화의 위치
			for (int i = 0; i < N; i++) P[i] = M + i;
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < M; i++) S[i] = Integer.parseInt(st.nextToken());
			// 구간 노드를 [0, M) + [M, M + N)으로 정의한다
			FenwickTree t = new FenwickTree(N + M);
			for (int i = 0; i < N; i++) t.add(M + i, 1);
			int head = M - 1;
			for (int i = 0; i < M; i++) {
				ans.append(t.sum(P[S[i] - 1]) - 1);
				t.add(P[S[i] - 1], -1);
				P[S[i] - 1] = head;
				t.add(head--, 1);
				if (i != M - 1) ans.append(" ");
			}
			ans.append("\n");
		}
		System.out.print(ans);
	}
	
}

class FenwickTree {
	int[] tree;
	
	public FenwickTree(int n) { tree = new int[n + 1]; }
	
	void add(int pos, int val) {
		pos++;
		while (pos < tree.length) {
			tree[pos] += val;
			pos += (pos & -pos);
		}
	}
	
	int sum(int pos) {
		pos++;
		int ret = 0;
		while (pos > 0) {
			ret += tree[pos];
			pos -= (pos & -pos);
		}
		return ret;
	}
	
}

1) 시간 복잡도

2) 테스트 케이스