5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 5014. 스타트링크 접근한 방법 단순 조건 분할과 반복문으로 풀이합니다. 1. 현재 s값을 기준으로 목표층(target)보다 적을 때, - 위층을 더한 것이 전체층 이내라면 위층으로 간다. - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. 2. 현재 s값을 기준으로 목표층보다 클 때, - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. - 위층을 더한 것이 전체층 이내라면 위층으로 간다. 예를 들면 s가 9, target이 10, u = 2, d = 1 와 같은 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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의 범..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 가장 먼 노드 접근한 방법 BFS를 이용해서 빠르게 해결할 수 있습니다. 주의할 점은 간선 저장 시 인접 행렬을 사용할 경우 시간이 초과됩니다. 노드 보다 간선이 적을 경우 매우 비효율적이므로 상대적으로 탐색에 더 효율적인 인접 리스트를 사용합니다. 간선을 저장했다면 큐를 이용해서 노드(now)와 간선 길이(cnt)를 관리합니다. JavaScript에서는 별도의 큐 라이브러리가 없으므로 shift 메서드를 사용하고 문제에는 영향이 없지만 비효율적이라 싫다면 front를 가리키는 포인터를 설정하여 큐 ..