프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 DFS로 현재 문자열에서 한 글자씩 지워가며 비교하는 방식으로 탐색합니다. 예를 들어 begin이 hit라면, 순차적으로 *it, h*t, hi* 과 같은 위치인 글자가 words배열에도 존재하는지 확인하여 존재하면 진입 횟수를 카운트하여 재탐색합니다. 이때 이미 방문했던 단어들은 제외하기 위해 방문 배열을 설정하여 관리합니다. target이 발견되면 현재까지 저장했던 result 카운트를 갱신한 후 DFS가 완전히 끝날 때 남아있는 result의 값이 최소 비교 횟수가 됩니다. 코드 설명 1. ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 최고의 집합 접근한 방법 문제 예시들을 보면 곱이 최대인 경우는 항상 0~s의 중간값이 가장 많은 집합의 곱이 가장 큰 값임을 알 수 있습니다. s가 짝수인 경우는 그대로 중간값들로 이루어진 배열을 리턴하면 되지만 홀수인 경우는 s를 n으로 나눈 나머지 횟수만큼 1씩 더해주어야 합니다. 문제 예시를 예로 들면 n = 2, s = 9일 경우 일단 원소가 s / n인 [4, 4]의 배열을 구성하고 s는 홀수이므로 나머지인 1회만큼 앞에서부터 원소를 1씩 더하면 [5, 4]가 되고 이 집합이 최고의 집합이..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 배열의 값들 중 가장 큰 값을 찾아서 1씩 제거해주어야 합니다. 이중 for문을 쓰면 시간 초과가 발생하므로 힙 구조를 이용해 제거해주면 됩니다. 주어진 works를 맥스 힙으로 구성한 후 n만큼 반복하여 매 순회 시 힙에서 값을 1제거한 후 다시 넣어주는 방식을 사용합니다. 자료를 넣고 빼는 과정은 각각 logn시간이 걸리므로 제한 시간 내에 풀이할 수 있습니다. def solution(n, works): import heapq as hq q = [] for i in works: hq.heapp..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 섬 연결하기 접근한 방법 최소 신장 트리를 찾아낼 수 있는지를 묻는 기본 문제입니다. 프림, 크루스칼 알고리즘 중 선택해서 풀이하면 되고 저는 크루스칼을 이용해서 풀이했습니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 이용해서 간단히 구현할 수 있습니다. 파인드(findP)는 노드의 부모 노드를 찾는 함수이며, 유니온(unionP)은 두 노드 집합의 부모를 연결해주는 함수입니다. 주어진 costs 배열을 비용순으로 정렬해주는 과정이 꼭 필요하고 정렬된 엣지를 순회하면서 싸이클이 없는 경우에만 두 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 이중우선순위큐 접근한 방법 문제에서 우선순위큐를 쓰고 있으므로 우선순위 큐를 사용할 수 있는 heapq 라이브러리를 사용합니다. 두 개의 힙큐(최대힙, 최소힙)를 사용해서 최댓값과 최솟값을 관리하면 됩니다. Insert일 경우에는 두 힙에 모두 값을 넣어주고 최대힙의 경우 음수로 관리하면 구현할 수 있습니다. Delete일 경우 두 힙에서 동일한 값을 모두 빼주어야 하는데 최댓값을 빼는 경우 최소힙에서는 최대힙에서 pop된 값에 음수를 붙여 제거해야 값을 찾을 수 있으며 최솟값을 빼는 경우 최대힙에서..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Lv3. 기지국 설치 접근한 방법 각 자리의 기지국 설치 여부를 배열로 다루게 되면 효율성 테스트에서 탈락됩니다. 굳이 설치여부를 다룰 필요 없이 해당 범위만 건너뛰면서 탐색했습니다. 주어진 stations를 먼저 고려하기 위해 이 어레이를 큐나 스택으로 활용합니다. 오름차순으로 되어있는 김에 큐로 사용하는 것이 낫고 자바스크립트에서는 front 포인터를 두어서 큐 처럼 활용합니다. 현재 위치에 기지국을 설치할지 말지를 결정하는데 그 위치가 미리 설치된 기지국(A)의 범위 안에 들면 탐색할 필요 없이 A의 범..