저는 37번 LRU 문제를 Deque랑 삽입 정렬로 풀었습니다.삽입 정렬은 강사님 설명대로 반복된 입력값을 정렬시킬 때 사용했습니다. deque는 캐시메모리 크기를 초과할 때 pop(제거)를 위해 사용했습니다. 처음에는 vector로 풀었는데, 이럴 경우입력값 : 1 2 3 2 6 2 3 5 7index :0 1 2 3 4vector<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] << " "; }