인프런 커뮤니티 질문&답변

저는 37번 LRU 문제를 Deque랑 삽입 정렬로 풀었습니다.

삽입 정렬은 강사님 설명대로 반복된 입력값을 정렬시킬 때 사용했습니다.

deque는 캐시메모리 크기를 초과할 때 pop(제거)를 위해 사용했습니다.

처음에는 vector로 풀었는데, 이럴 경우

입력값 : 1 2 3 2 6 2 3 5 7

index :

0 1 2 3 4

vector<int> v :

1 6 2 3 5

에서 처음 입력됐던 1이 삭제돼야하는데, vector는 pop_back()만 있어서 앞쪽인 1이 아니라 뒤쪽인 5가 삭제됩니다.

그래서 pop_front() 혹은 pop_back()랑 push_front가 동시에 컨테이너가 없을까 찾아보다가, 양방향 입력/제거 가능한 deque를 사용했습니다!

(queue도 앞으로 들어오고 뒤로 나가는 거지만 정렬하기 힘드니까 패스!)

아래 코드 첨부합니다!

최근에 해시 공부하면서 익힌 iterator(반복자)도 사용했는데, iterator가 처음이신 분들은 대충 index처럼 요소 접근하는걸로 이해해주시면 됩니다!(정확히는 주소 접근이지만!)

#include<iostream>
#include<deque>
#include<algorithm>

using namespace std;

int main() {
	int S{}, N{};
	deque<int> dq;

	// 중복 값 정렬
	cin >> S >> N;
	for (int i = 0; i < N; i++) {
		int tmp{};
		cin >> tmp;

		// 중복값 찾기
		deque<int>::iterator it = find(dq.begin(), dq.end(), tmp);
		if (it == dq.end()) dq.push_front(tmp); // 중복 없으면 그냥 앞에서 삽입
		else { // 중복값 있다면
			// (tmp = *it을 할 필요없음 : 그 값이 그 값이니까)
			// 하나씩 뒤로 밀기. 제일 앞쪽에 도착하면 it-1을 못하니까 반복 종료
			for (it; it != dq.begin(); it--) {
				*it = *(it - 1);
			}
			*it = tmp;
		}

		// 제일 뒤쪽 삭제
		if (dq.size() > S) dq.pop_back();
	}

	for (int i = 0; i < dq.size(); i++)
		cout << dq[i] << " ";
}