간만에 머리도 풀어볼 겸, 프로그래머스에서 알고리즘 문제를 풀어봤다. lv1은 쉽게 풀었지만, 2에서는 효율성에서 실패가 떴고 푸는데 조금 고민을 하게 되어 정리를 해보고자 한다. 문제 링크는 다음과 같다. https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(land) { var answer = 0; const depth = land.length; const width = land[0].length; //이중배열 ..
Algorithm
주어진 정수 num에 대해 결과가 한 자릿수만 남을 때까지 반복해서 모든 자릿수를 더하고 그 값을 반환하는 문제이다. 아래처럼 간단히 재귀로 풀었다. var addDigits = function(num) { const numArray = num.toString().split("").map(str => Number(str)); if(numArray.length === 1){ return numArray[0] }else{ return addDigits(numArray.reduce((acc, cur) => acc + cur)) } }; 다른 사람들 풀이를 보니 아래처럼 기발하게 푸는 방법도 있었다. var addDigits = function(num) { return 1 + (num - 1) % 9; };
anagram인지 판단하는 문제이다. anagram은 각 String의 구성요소들의 순서만 바꾸어서 생성한 다른 String을 의미한다. var isAnagram = function(s, t) { if(s.length !== t.length) return false; const mapper = {}; for(const letter of s.split("")){ if(!mapper[letter]){ mapper[letter] = 1; }else{ mapper[letter] += 1; } } for(let i = 0; i < t.length; i++){ const letter = t[i]; if(mapper[letter] < 0 || mapper[letter] === undefined){ return fal..
leetCode의 Valid Palindrome 문제를 해결하고 정리한다. 1. 먼저 정규표현식으로 알파베틱 글자이외를 전부 없애준다. 2. 소문자로 변경 3. 글자의 처음과 마지막을 two pointer로 비교하며 리턴한다. var isPalindrome = function(s) { let str = s.replace(/[^a-zA-Z0-9]/g, ''); str = str.toLowerCase(); let start = 0; let end = str.length-1; for(let i = start; start < end ; i++){ if(str[start] === str[end]){ start ++; end --; }else{ return false } } return true; };
문제의 상세내역은 링크를 참고하자. 문제는 간단해 보인다. 10진법 의 숫자를 3진법의 숫자로 바꾸는 것이다. 하지만, 문제에서 특이한 점은 0을 사용하지 않고 4를 사용한다는 것이다. 1. 문제 접근 이 나라에서는 1은 1, 2는 2, 3은 4를 가르킨다고 생각하자. 예를 통해 이해해 보자. 10진법으로 9가 주어졌다면, 3으로 나누었을 때 몫은 3, 나머지는 0이 될 것이다. 하지만, 이 말도 안되는 나라는 0을 싫어하나보다. 0을 쓰지 못한다. 나머지를 3으로 바꿔주고, 몫을 하나 줄여주자. 그렇게 되면, 우리는 몫이 2, 나머지가 3이 되게 될 것이다. 이 나라에서 2는 2, 3은 4를 의미하므로, 최종적으로 24라는 답이 나오게 되는 것이다. 2. 전체 코드 function solution(n)..
1. 문제 문제는 아래와 같다. 결국, 늑대에게 잡아 먹히지 않고 최대한 많은 양을 모으고 그 양의 수를 리턴 해야 하는 문제이다. 2. Idea 💡 해당 문제에서 키 포인트는 갔던 길을 다시 돌아서 다른 곳으로 갈 수 있다는 것이다. 예를 들어, 1번 -> 8번 -> 7번 -> 9번 -> 5번 과 같은 방식으로도 이동이 가능하다는 것이다. 이렇게 되면 결국 모든 경우의 수를 탐색하여 각 노드에서 얻을 수 있는 양의 최대 수를 리턴 해야 한다. 단, 만약 해당 노드를 방문했을 때, 양들이 늑대에게 잡아 먹히게 된다면, 해당 노드를 물리고, 다음 노드를 탐색한다.(Backtracking) 3. Solution 완전 탐색을 하는 방법으로는 가장 크게 dfs(depth first search), bfs(bre..
