[G1] 백준 1700번 멀티탭 스케줄링 C++ 그리디 알고리즘, 해시 셋

리뷰

 

https://www.acmicpc.net/problem/1700

문제를 어렵게 생각해서 계속 틀리다가 간단하게 생각하니 AC를 받게 된 문제

 

 

전역 변수

• n : 콘센트의 구멍 개수를 저장할 변수
• k : 콘센트에 꽂고자 하는 제품의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• dic : 콘센트에 꽂힌 물품 정보를 저장할 해시 셋

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, 정수형 벡터 lst를 k크기로 초기화 해준다.
2. k개의 제품 정보를 입력 받고, lst에 저장해 준다.
3. k개의 제품을 순회하며 dic이 n보다 작거나, 이미 존재하는 제품일 경우 dic에 insert해준다.
4. 콘센트에 연결된 제품을 제거해야 할 경우 정수형 변수 Del과 Midx를 -1로 초기화 해준다.
5. dic을 순회하며 아직 사용하지 않은 제품 중 동일한 id를 가진 제품 중 가장 빠른 인덱스를 찾아준다.
6. 만약 그러한 제품이 존재하지 않는다면 Del을 해당 제품의 id로 저장하고 break처리해 준다.
7. 존재할 경우 해당 제품의 인덱스가 Midx보다 작다면 Del과 Midx를 제품의 id, 인덱스로 교체해 준다.
8. ans를 1만큼 증가시켜 주고, dic에서 Del을 제거하고, id를 추가해 준다.
9. 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 처음엔 해시맵에 각 제품의 등장 인덱스를 모두 매핑해 주고, 탐색 시 해시맵을 참고하는 방식으로 로직을 구현했다.
2. 하지만 코드가 복잡해졌고, 작성한 나조차 알아보기 힘들어 틀린 부분을 디버깅하기 힘들었다.
3. N과 K는 상충 관계이며, 제한 값도 적기 때문에 비효율적이라도 선형 탐색을 통해 구현하도록 했다.
4. dic의 모든 요소에 대해 find를 통해 선형 탐색을 진행하여 AC를 받았다.

 

참고 사항

• N, K가 작기 때문에 탐색 시 선형 탐색으로 구현해 주어도 문제가 없다.

 

정답 코드

#include<iostream>
#include<vector>
#include<unordered_set>
#include<algorithm>
using namespace std;

int n, k, ans;
unordered_set<int> dic;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;
	vector<int> lst(k);
	for (int i = 0; i < k; ++i) cin >> lst[i];

	for (int i = 0; i < k; ++i) {
		int id = lst[i];
		if (dic.size() < n || dic.count(id)) dic.insert(id);
		else {
			int Del = -1, Midx = -1;
			for (int num : dic) {
				auto it = find(lst.begin() + i, lst.end(), num);
				if (it == lst.end()) {
					Del = num;
					break;
				}
				int idx = it - lst.begin();
				if (idx > Midx) {
					Del = num;
					Midx = idx;
				}
			}
			ans++;
			dic.erase(Del);
			dic.insert(id);
		}
	}
	cout << ans;
}