DS & Algorithm/programmers

[프로그래머스] 괄호 변환 - 자바스크립트

문제 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이 문제가 상당히 길지만 당황하지 말고 천천히 읽어보면 의외로 쉽게 풀리기도 한다. 핵심 키워드는 다음과 같다. 균형잡힌 괄호 문자열 : 두 괄호 "(" ")"의 개수가 같다. 올바른 괄호 문자열 : 균형잡힌 괄호 문자열이면서, "(" ")" 의 순서 짝이 맞는 경우이다. 임의의 "균형잡힌 괄호 문자열" p를 입력받아 "올바른 괄호 문자열"로 바꿔서 출력하는 문제이다. 풀이 방향 문제를 보면, 임의의 p를 입력받으나 이는 이미 "균형잡힌 괄호 문자열"임이 ..

[프로그래머스] 게임 맵 최단거리 - 자바스크립트

문제 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 풀이 n x m 행렬에서 (1,1)에서 시작해서 (n,m)에 도달하는 최단경로를 출력한다. (n,m)에 도달할 수 없다면 -1을 출력한다. 풀이 방법 최단경로를 구해야 하므로 BFS 유형의 문제이다. 현재 위치에서, 상하좌우 이동 가능 여부를 판단한다. 상하좌우가 벽(0)이거나, 행렬의 범위를 벗어났다면 이동할 수 없다. 이동할 수 있다면 이동할 좌표와 이동한 횟수를 큐에 넣는다. FIFO를 따라 BF..

[프로그래머스] 땅따먹기 - 자바스크립트

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 처음에는 DFS로 접근했다. N회까지 재귀를 돌면서, X행에서는 X-1행에서 선택하지 않은 열을 선택하여 더했다. 각각의 경우의 수로부터 N행까지 도달했을 때, 최댓값일 경우 최댓값을 갱신하도록 했다. 물론 주어진 행 N이 최대 100,000이기 때문에 재귀 호출로 인한 시간초과 이슈가 발생했다. 모든 경우의 수를 조회할 수 없다면, DP(동적 계획법)를 생각해봐야 한다. 풀이방법 DP답게 생각해보자. land 행렬은 N x 4 크..

[프로그래머스] 다리를 지나는 트럭 - 자바스크립트

문제 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무..

[프로그래머스] 크레인 인형뽑기 게임 - 자바스크립트

문제 게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. 죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인 이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에 는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인 형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 ..

[프로그래머스] 위장 - 자바스크립트

문제 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의..