프로그래머스

프로그래머스: 불량 사용자(JS, backtracking) feat. 현대캐피탈 2024 상반기 공개채용

알고리즘을 하도 오랜만에 풀었더니 백트래킹이라는 알고리즘을 까먹었어서 되새길겸 쓰는 글이다.문제는 간단하다. 불량 사용자 배열의 원소들이 각각 가능한 경우의 수를 구하고 이 중 중복이 존재할 수 있고, 불량 사용자 배열의 길이 및 사용자 아이디 배열의 길이가 8이하로 매우 작으니 백트래킹을 이용해 가능한 모든 경우의 수를 구하면 된다. 백트래킹을 사용하는 이유는 매번 빈 배열을 dfs에 넣어야하기 때문이다. 현대 캐피탈 2024 상반기 공채 3번이 딱 이런 문제였는데 난 그때 백트래킹을 생각을 못해서 재귀함수의 depth가 0일때 재귀함수 안에서 빈 배열을 생성하여 그 배열에 원소를 넣고 재귀함수에 다시 prop으로 넣는 방식으로 풀었었다. 참고로 1번은 구현, 2번은 그래프탐색(BFS사용), 3번은 백..

프로그래머스: 단속카메라(javascript, greedy)

문제는 쉬우나 처음 접근을 잘못해 헤맨 문제이다. 이전에 호텔방 예약하는 문제와 비슷하여 시작 시간과 끝시간만 비교했으나 다음 차의 범위가 이전 차의 범위안에 들더라도 비교가 계속 되면 과거 차들의 정보가 반영이 안되는 문제를 고려 안했다. 그 부분을 수정하기 위해 시작 시간과 끝 시간을 계속 변경 시키는 알고리즘을 추가하여 문제풀이에 성공하였다. greedy algorithm은 떠올리기는 쉬우나 그것이 절대해인지 증명하는 것이 매우 어려워 사실상 운에 맡기거나 반례를 열심히 생각해내야 한다.. function solution(routes) { let answer = 0; routes.sort((a,b)=>a[0]-b[0]) let start = 30001 let end = -30001 routes.fo..

프로그래머스: 숫자 변환하기(javascript, deque, bfs)

BFS를 이용해 푼 문제이다. 처음에 BFS로만 풀려 했으나 계속 시간초과가 나서 백준 소꿉놀이처럼 미리 배열을 선언해두고, 시작점을 1로 해둔다. 그리고 방문안한 점을 방문할 때만 이전 지점에 1을 더해서 연산 횟수를 기록하는 방식이다. 글까지 써가며 기록하게 된 이유는 자바스크립트의 배열은 shift와 unshift연산이 모두 되는 deque이기에 bfs를 쓸 때 그냥 배열에 저장했었는데 테스트 케이스 두개가 계속 시간초과가 나서 자료구조를 다른 사람이 구현해놓은 deque을 사용했는데 훨씬 빠르게 통과돼서 놀랐었다. 왜냐하면 보통 내장함수나 내장 자료구조보다 잘 구현하기는 힘들기 때문이다. 앞으로 deque이나 queue자료구조가 필요한 알고리즘 문제는 자료구조를 직접 구현해서 써야겠다. class..

프로그래머스: 프렌즈 4 블록(javascript, 구현)

애니팡같은 게임을 구현하는 문제이며 구현문제이나 javascript는 문자열이 immutable이라서 처리하는데 조금 애를 먹었던 문제였다. 파이썬으로는 되게 쉽게 풀었던것 같은데.. 로직은 간단하다. 2차원 배열을 2x2 정사각형으로 탐색하며 2x2블록안의 문자가 모두 같다면 배열에 그 위치를 모두 저장하면 된다. 배열에 저장하는 이유는 한 위치가 두 블록에 중복되게 포함될 수 있으므로 위치들을 모두 저장했다가 탐색이 끝나면 한번에 지워야 한다. 그 후 빈 블록을 제외한 나머지 블록들을 아래로 내리는 작업을 반복하면 된다. javascript의 문자열이 immutable이라서 문자열을 [행,열]로 접근하지 않고 행을 통채로 교체하는 방식으로 배열을 바꿨다. function solution(m, n, b..

프로그래머스: 파일명 정렬(javascript, 구현)

문제는 구현하기 쉬웠으나 배울만한 점 두가지가 있어 글을 남기게 된다. 문제는 기본적인 정렬 문제로 간단한 구현 문제였다. 주어지는 파일명마다 head와 number로 나누고 tail부분은 무시 후, head를 대소문자 구분없이 기준삼아 정렬 후 두번째 정렬기준으로 number로 정렬하면 된다. head와 number를 구분하기 위해 javascript의 내장함수인 isNaN함수를 사용하고, number이후의 tail를 무시하기 위해 number가 빈값이 아닐때 알파벳이 들어오면 파일명 저장을 멈추도록 하였다. 그 후 head와 number, 원래 파일명을 배열로 하여 빈배열에 저장하였다. 파일명들을 head, number, 원래 파일명으로 나누어 모두 저장하고 나면 배열을 정렬하기만 하면 된다. 이를 ..

프로그래머스: 주차 요금 계산 (파이썬, 구현)

문제 자체는 어렵지 않았는데 구현에 시간이 좀 걸리는 문제였다.. 푸는데 40분정도 걸린 것 같다. 시간과 번호판의 자리수가 정해져 있기에 파이썬의 list indexing과 sort함수를 이용하면 쉽게 풀 수 있는 문제였다. 먼저 문제에서 봐야할 조건은 크게 두가지 였던것 같다. 첫째로 누적 주차시간을 계산하여 요금을 일괄로 정산한다는 점, 둘째로 입차 후 당일에 출차를 안할 시 23:59분에 출차로 계산한다는 점이다. 셋째로 차량 번호가 작은 자동차부터 주차요금을 배열에 담아 return해야 한다는 점이다. 이 세가지 조건을 토대로 차량번호별로 주차시간을 계산해야하고, 미리 번호판, 시간순으로 정렬이 필요하겠다는 생각을 하였다. 번호판, 시, 분 순으로 정렬한다면 in, out조건을 신경쓸 필요 없어..

프로그래머스: [3차] 압축 (파이썬, 구현)

간단한 구현 문제이나 푸는데는 30분정도 걸린 것 같다.. 대기업 코딩 테스트에는 구현 문제가 한 두문제씩 나오는 경우가 많아 여러가지 케이스들을 미리 해보는게 빠른 구현에 도움이 될 것 같다. 문제를 살펴보면 주어진 문자열을 LZW라는 알고리즘으로 압축을 해야 하는데 이 알고리즘은 사전의 인덱스를 이용하여 해당하는 문자의 인덱스를 출력하는 방식이다. 따라서 문제를 풀기 위해서는 우선 대문자들로 dictionary를 미리 초기화 시켜야함을 알 수 있다. 그 후 반복문을 이중중첩하여 문자열을 탐색하는데 내부의 반복문은 dictionary가 계속 늘어나기에 그에 맞춰 문자열을 dictionary의 key에 없을때까지 더하는 용도이다. from string import ascii_uppercase def so..

프로그래머스: k진수에서 소수 개수 구하기 (파이썬, 구현)

간단한 구현 문제인데 구현할게 조금 있어서 30분보단 조금 더 걸렸던 문제였다. 문제를 풀기 위해서는 세가지를 구현해야 하는데 첫째로 10진수를 n진수로 변환해주는 함수, 두번째로 소수인지 아닌지 판단하는 함수, 마지막으로 n진수에서 0을 기준으로 숫자들을 나누는 함수이다. 함수는 순서대로 보겠다. 우선 소수인지 아닌지를 판단하는 함수이다. 프로그래머스를 좀 풀어본 사람이라면 알텐데 소수구하는 문제가 은근 많아 소수 구하는 방법은 외울 정도이다. 제곱근보다 작은 구간에서 약수를 가진다면 수를 그 약수로 나눈 수는 제곱근보다 큰 구간에서 약수가 되므로 제곱근까지만 약수가 있는지 없는지를 보면 된다. 다음으로 진법 변환 함수이다. 아마 컴퓨터공학이나 전자전기공학을 전공한 사람들은 다 알텐데 10진수를 n진수..