🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 🔗최소 신장 트리(MST, Minimum Spanning Tree)를 활용하는 문제입니다. 최소 신장 트리를 구축하는 과정에서 크루스칼(Kruskal) 또는 프림(Prim)의 알고리즘이 사용되며, 저는 크루스칼(Kruskal)의 알고리즘을 사용하여 풀었습니다. 신장 트리의 조건 중 하나로 사이클이 있으면 안된다가 있는데, 분리 집합(Disjoint set)의 개념인 🔗유니온 파인드(Union Find)라 불리는 자료구조로 쉽게 점검할 수 있습니다. 이번 기회에 공부하여 개념을 ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻 풀이 과정 처음엔 다익스트라(Dijkstra) 알고리즘을 먼저 떠올렸는데, BFS로도 간단하게 풀 수 있겠단 생각이 들어 BFS로 풀었습니다. 알고리즘은 다음과 같습니다. 행 번호는 노드의 번호, 열 번호는 행 번호 노드와 연결된 다른 노드들의 번호로 이루어진 2차원 배열을 선언한다. 1번 노드를 방문 처리 후 Queue에 넣고, BFS 탐색을 시작한다. Queue에서 노드(source)를 꺼낸 후, 해당 노드와 연결된 다른 노드들을 방문 처리 후 Queue에 넣는다. 이 때, sour..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 문제를 보자마자 양 쪽에 인덱스를 가리키는 변수 2개를 두고 구간을 줄여가며 구해야겠다고 생각했는데, 이게 투 포인터(Two pointer) 알고리즘이더군요. 몰랐지만 자연스럽게 사용하게 되었습니다..? 풀이 방식은 다음과 같습니다. gems 배열을 순회하며 보석의 종류 개수를 알아낸다. 시작 인덱스(start)와 끝 인덱스(end) 변수를 각각 0으로 두고, 보석의 종류 개수를 다 포함하는 구간이 될 때까지 end를 증가시킨다. 보석의 종류를 모두 포함하는 가장 작은 구간까지..

🔗문제 보러가기 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🧑‍💻풀이 과정 string을 스택(stack)처럼 사용하여 풀었습니다. 정답을 저장할 string 변수(answer)를 따로 준비한 후, 주어진 문자열을 차례대로 순회하였습니다. 그리고 다음과 같은 과정을 진행해 주었습니다. 현재 읽은 문자열을 answer 변수에 넣습니다. 현재 읽은 문자열이 폭발 문자열의 마지막 문자와 같다면, 다음 과정을 거칩니다. answer와 폭발 문자열을 뒤에서부터 차례대로 읽으며 비교합니다. 두 문자열..

🔗문제 보러가기 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 🧑‍💻풀이 과정 등간격으로 설치할 수 있는 가장 큰 간격을 매개변수 탐색으로 구하면 됩니다. 입력 받은 집 위치들을 배열(arr)에 담고, 오름차순으로 정렬해준 뒤에 다음 과정을 진행해 주었습니다. left = 0 (첫 번째 ~ 첫 번째 공유기 사이의 범위), right = arr[N - 1] (첫 번째 ~ 마지막 공유기 사이의 범위) mid = (left + right) / 2로 중간 범위값을..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 (1)자동으로 오름차순으로 정렬되고, (2)중복 숫자 저장이 되며, (3)최솟값과 최댓값에 바로 접근할 수 있는 자료구조를 선정해야 합니다. 네, 바로 multiset이죠. multiset을 이용하면 쉽게 구현할 수 있습니다. 알고리즘은 다음과 같습니다. 공백을 기준으로 입력을 분리하여, "명령어"와 "데이터" 문자열로 분리합니다. "명령어"가 'I(대문자 i)'라면, multiset에 데이터를 삽입합니다. "명령어"가 'D'라면, 그 뒤에 오는 데이터가 1이냐, -1이냐에 따..