알고리즘 이론 & 풀이/프로그래머스

프로그래머스 Lv.1 | 전화번호 목록 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42577 풀이 통과한 풀이 sort()로 정렬을 하면 앞글자가 비슷한 것끼리 이웃에 위치하게 된다. ["119", "11923", "119763"] 처럼 아무리 접두어가 같은 게 여러 개 있어도 바로 인접한 요소가 자신을 접두어로 가진다면 return false를 하고 끝내면 되므로 i, i+1 만 비교하면 된다. for문을 돌려 i+1 범위가 넘치지 않게 phone_book.length -1 까지 검사하면서 [i + 1]이 [i]를 접두어로 가지는지 startsWith로 검사한다. 완전히 일치한다면 접두어가 아니게 되므로 일치하지 않는 것만 통과시킨다. 그리고 return false for문 ..

프로그래머스 Lv.1 | 완주하지 못한 선수 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42576 풀이 통과한 풀이 두 배열을 정렬한다. completion을 돌며 completion[i]가 participant[i]와 어긋나기 시작한 최초의 지점이 바로 완주하지 못한 참가자가 위치한 곳이므로 그 참가자를 반환한다. completion을 다 돌아도 어긋난 지점을 찾지 못한다면 participant의 마지막에 위치한 참가자가 완주 못한 것이므로 그 사람을 반환한다. function solution(participant, completion) { participant.sort(); completion.sort(); for(let i = 0; i < completion.length; i+..

프로그래머스 Lv.1 | 폰켓몬 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1845 이 문제의 유형은 '해시'이다. 해시란 key: value의 쌍으로 값을 관리하는 것이다. js에서는 해시를 구현할 때 Map obbject를 이용한다. 그런데 이 문제는 최빈값을 구하는 것처럼 각 요소가 몇 번 나오는지 세는 게 중요한게 아니고, 얼마나 다양한 종류의 폰켓몬을 고를 수 있는지가 중요하다. 즉, key만 중요하기 때문에 중복을 제거한 배열을 만들면 굳이 Map을 만들어 value까지 셀 필요가 없다는 말이다. 풀이 중복을 제거해 폰켓몬의 종류만 남긴다. 중복제거.length보다 골라야 하는 폰켓몬 수(N/2)가 작거나 같다면 N/2를 모두 다른 종류로 채울 수 있으므로 N..

프로그래머스 Lv.0 | 영어가 싫어요 js

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120894 풀이 function solution(numbers) { const numberList = { zero: 0, one: 1, two: 2, three: 3, four: 4, five: 5, six: 6, seven: 7, eight: 8, nine: 9 }; Object.entries(numberList).forEach(([key, value]) => { numbers = numbers.split(key).join(value); }); return Number(numbers); } 객체에 문자열과 숫자를 쌍으로 넣어놓는다. Object.entries로 순회하며 key, value를 이..

프로그래머스 Lv.0 | 소인수분해

https://school.programmers.co.kr/learn/courses/30/lessons/120852 💻 코드 12는 2, 2, 3으로 소인수분해 된다는 것을 생각해보자. while문을 통해 i=2부터 시작해 수를 i로 나눠보는 것을 반복한다. 더 이상 나누어 떨어지지 않으면 2로 인수분해할 것이 떨어졌다는 뜻이므로 i++ 해서 다음 수로 계속 나누는 식으로 반복한다. 중간에 if문으로 이미 소인수로 배열에 등록된 수가 들어가지 않도록 검사해준다. (혹은 그냥 if문 없이 계속 answer.push(i)를 하고, 마지막 결과 반환 부분에서 return [...new Set(answer)]를 해도 된다. function solution(n) { const answer = []; let i =..

프로그래머스 Lv.0 | 이진수 더하기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120885 💻 풀이 풀이 1 - 진법 변환 이용 2진수를 10진수로 변환해서 계산 후, 다시 2진수로 변환하기 function solution(bin1, bin2) { const sum = parseInt(bin1, 2) + parseInt(bin2, 2); return sum.toString(2); } 풀이 2 - 2진수 자릿수 올림 이용 예를 들어 1001 + 1111을 숫자 그대로 더하면 2110이 된다. 맨 뒷자리부터 검사해서 만약 숫자가 2라면 그 자릿수는 0으로 바꾸고 앞자리에는 1을 더해준다. 원래 2였는데 뒷자리로부터 1을 올림받아 3이 된 경우도 있을 것이다. 그런 경우에는 그 ..

프로그래머스 Lv.0 | 문자열 계산하기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120902 💻 풀이 이 문제를 보고 eval()로 풀고 싶다는 유혹을 받았으나... 정정당당하게 알고리즘으로 승부를 보자. 공백으로 split 해서 숫자와 연산자를 순서대로 담은 배열을 만든다. 짝수번째 인덱스에는 숫자가, 홀수번째 인덱스에는 연산자가 담겨있다. sum 변수를 생성하고, i=0부터 2씩 증가시키며 i번째 숫자를 계속 sum에 축적하면 된다. 덧셈인지 뺄셈인지는 바로 앞에 위치한 i-1번째 연산자를 확인하면 된다. 다만 0번 인덱스에 있는 숫자부터 sum에 축적하려고 보면 확인할 i-1번째 연산자라고 할 게 없으므로, sum에 기본적으로 arr[0]을 설정한 다음 i=2부터 축적하..

프로그래머스 Lv.0 | 공던지기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120843 💻 코드 풀이 1 '오 이건 원형리스트고 맨 앞에가 공 던지는 사람이 되도록 배열을 2개씩 shift, push, shift, push 반복하면 되겠다!' 하고 냅다 풀었는데 너무 날것이라 내가 생각해도 좀 웃김 function solution(numbers, k) { for(let i = 1; i 0번째 수인 1 이라는 결과가 나오는 것이다. 그러면 4번째 인덱스가 최종적으로 공을 던진다는 것을 어떻게 하면 한번에 알 수 있을까? 공을 건너뛰어서 던지지 않고 바로 옆자리 사람에게 패스하면 [3-1] 인덱스의 사람이 마지막으로 던졌을 텐데 (3번째 사람이긴 한데 인덱스로 따지면 1을 ..