기계는 거짓말하지 않는다

프로그래머스 - 캐시 문제 입니다. 일반적인 캐시와 캐시 교체 정책을 생각하면됩니다. LRU 교체 정책이므로 cache hit이면 항상 앞으로 옮겨주고 miss이면 cache가 가득 찼을 경우 맨 뒤의 요소를 제거 후 가장 앞에 현재 데이터를 넣습니다. 앞, 뒤 삽입, 삭제가 빈번하므로 list 사용 #include #include #include using namespace std; int solution(int cacheSize, vector cities) { int answer = 0, i, j; list cache; list::iterator itr; bool find = false; for(i = 0; i < cities.size(); i++) { for(j = 0; j < cities[i].l..

프로그래머스 - 124 나라의 숫자 문제입니다. 숫자 3개가 끝이므로 3진법을 생각했습니다. 3진법에서 0, 1, 2로 표현되고 정확히 3으로 나누어 진다면 4로 바꾸면 되겠다는 생각을 했습니다. 재귀함수를 이용하여 3진법 string을 거꾸로 출력하면서 조건을 답니다. 주의점은 6, 9처럼 정확히 나누어 떨어질 때 3진법에서는 20, 100이 되지만 문제는 1이 적기 때문에 1을 뺀 후의 몫을 붙입니다. #include #define NOTATION 3 using namespace std; string chg(int n) { int num; num = n % NOTATION == 0 ? 4 : n % NOTATION;// 나머지가 0일 경우 4로 치환 if(NOTATION >= n) {// 마지막 몫 ..

프로그래머스 - 튜플 문제입니다. 양쪽의 중괄호를 먼저 제거하고, 다음 중괄호 안의 원소만 ,를 포함해서 string 벡터에 담아야겠다는 생각을 했습니다. 원소 수가 적은 집합을 오름차순으로 정렬 후 중복되지 않게 차례대로 정답 벡터에 추가합니다. ,를 기준으로 끊어 number를 확인 합니다. 중복 확인은 unordered_set 을 사용했습니다. 마지막에는 ,가 없으므로 배열 길이의 마지막에 도달하면 number를 한번 더 확인합니다. #include #include #include #include using namespace std; bool cmp(string a, string b) { return a.length() < b.length(); } vector solution(string s) { ..

프로그래머스 - 야근 지수 문제입니다. 각 work의 제곱을 더한 값이 최소가 되려면 가장 큰 works 부터 줄여야겠다는 생각을 했습니다. max heap을 이용하여 n과 works를 1씩 줄이면 답을 낼 수 있고, 효율성을 올리려면 가장 큰 work 와 두번째로 큰 work의 차이를 한번에 n에서 빼면 될 것 같습니다. #include #include using namespace std; long long solution(int n, vector works) { priority_queue pq;// max heap long long answer = 0; int preValue; for(int i = 0; i < works.size(); i++) { pq.push(works[i]); } while(!p..

프로그래머스 - 단어 변환 문제입니다. BFS를 사용하여 시작 단어부터 문자가 단 1개 차이나는 단어를 depth를 늘려 추가해야겠다는 생각을 했습니다. #include #include #include using namespace std; class WordDepth { public: string word; int depth; WordDepth() {} WordDepth(string word, int depth) { this->word = word; this->depth = depth; } }; int solution(string begin, string target, vector words) { int i, j, differCnt = 0; bool check = false; vector wordChec..