백준 1700

백준 1700

이 문제는 n개의 멀티탭 구멍이 있고, k개의 전기용품 순서가 있을 때 최소한으로 플러그를 뽑는 횟수를 구하는 문제이다.

처음에 k개의 전기용품을 chk 배열을 둬서 n개의 구멍에 콘센트를 꽂는 것을 체크한다. 만약 n개의 구멍에 다 꽂혀 있다면 현재 꽂아야할 전기용품을 연결하지 못할 때는 뒤에 전기용품을 꽂혀있는 n개의 전기용품 중에 제일 나중에 연결해야하는 전기용품을 뽑거나 아예 연결할 필요가 없는 전기용품을 뽑는다. chk2 배열을 둬서 뒤에 전기용품이 있는지를 체크한다.

1. 멀티탭에 다 안꽂혀 있을 때
2. 멀티탭에 다 꽂혀있을 때
   2.1 꽂혀 있는 전기용품 중 제일 나중에 연결해야할 전기용품이나 아예 연결할 필요가 없는 전기용품의 index 찾기

#include<bits/stdc++.h>
using namespace std;
int n, k;
vector<int> v;
int chk[102],chk2[102]; int cnt = 0; int ans;
int main() {

	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;

	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	for (int i = 0; i < v.size(); i++) {

		if (!chk[v[i]]&& cnt!=n) { // 1. 콘센트 다 안꽂혀 있을 때 
			chk[v[i]] = 1;
			cnt++;
		}
		else if (cnt==n) { // 2. 콘센트 다 꽂혀있을때

			memset(chk2, 0, sizeof(chk2));
			if (!chk[v[i]]) { // 2.1 콘센트가 다 꽂혀있는데, 빼야할 때 ( 뒤에서 다신 안나오는 걸 빼거나, 제일 나중에 쓰일 것을 뺌)

				int lastidx = -1; int flag = 0;

				for (int j = i+1; j < v.size(); j++) {
					
					int t = v[j]; //제일 나중에 쓰일 인덱스 찾기

					if (chk[t] && !chk2[t]) {
						chk2[t]++;
						lastidx = j;
					}
				}

				for (int r = 0; r < i; r++) {
					if (chk[v[r]] && !chk2[v[r]]) {
							chk[v[r]] = 0;
							chk[v[i]] = 1;
							ans++;
							break;
					}
					if (r == i - 1) flag = 1;
				}

				if (flag) {
					chk[v[lastidx]] = 0;
					chk[v[i]] = 1;
					ans++;
					}
			}
		}
	}
	cout << ans;
}

생각 할 수 있는 로직은 맞다고 생각했는데, 틀려서 어디가 문제인지 알아보느라 시간이 많이 걸렸던 문제.. 로직은 맞는데 구현할 때 잘못 구현해서 틀렸었음..