기계는 거짓말하지 않는다

프로그래머스 - 올바른 괄호 문제 입니다. 괄호가 열리고 나면 무조건 닫혀야 올바른 괄호가 된다는 것만 숙지하면 됩니다. 열린 괄호를 하나씩 판별 하면서 개수를 더하다가 닫힌 괄호를 만나면 개수를 빼줍니다. 열린 괄호 개수가 음수가 되면 잘못 된 것이고, 판별이 끝났을 때 양수이면 열린 개수보다 닫힌 개수가 적은 경우입니다. (ex: ((()) ) 판별이 끝난 후 개수가 0개이면 맞는 경우이므로 true를 리턴합니다. #include using namespace std; bool solution(string s) { int open = 0; for(int i = 0; i < s.length(); i++) { if(s[i] == '(') open++; else { open--; if(open < 0) br..

프로그래머스 - 등굣길 문제 입니다. 주의사항은 행, 열이 반대라는점과 시작 지점이 [0, 0]가 아닌 [1, 1] 입니다. 오른쪽과 아래로만 움직인다면 최단 경로는 어떻게 가더라도 동일합니다. cost에 대한 것을 배제하고 경우의 수만 따지면 됩니다. 첫 번째 행과 열을 1로 만들어 주되, 물이 잠긴 곳의 뒷 부분 부터는 갈 수 없으므로 0으로 만듭니다. 그 후 [2, 2] 부터 경로의 갯수를 합산합니다. #include #include #include using namespace std; bool cmp(vector a, vector b) {// 내림차순 정렬 if(a[0] != b[0]) return a[0] > b[0]; else return a[1] > b[1];// 행이 같으면 열로 정렬 } ..

프로그래머스 - 이진 변환 반복하기 문제 입니다. 문제 그대로 1인 문자 개수를 이진수로 변경하고 0인 문자를 계속 카운트 합니다. 이진수 문자열은 재귀함수를 사용했습니다. #include #include using namespace std; string binaryNumber(int n) { if(n < 2) return to_string(n); return binaryNumber(n / 2) + to_string(n % 2); } vector solution(string s) { vector answer; int zeroCnt = 0, tryCnt = 0, i = 0; int len = 0; while(s.length() != 1) { for(i = 0; i < s.length(); i++) { if..

프로그래머스 - 캐시 문제 입니다. 일반적인 캐시와 캐시 교체 정책을 생각하면됩니다. 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..