문제https://www.acmicpc.net/problem/1774 풀이크루스칼을 이용해 MST를 구하는 문제입니다. 백준의 4386번. 별자리 만들기 문제와 상당히 비슷합니다. 이 문제의 핵심은 좌표(x, y)를 하나의 인덱스로 다루는 것이라고 생각합니다. 좌표를 입력받고, 좌표들을 간선으로 연결할 때에 인덱스를 매겨주며 ArrayList에 추가하고, 간선에 추가된 좌표의 위치는 거리를 구하기 위해서 필요할 뿐이지 더는 필요가 없으므로 시작과 종료 지점의 인덱스로 변환하고 좌표는 버립니다. 그리고 크루스칼 알고리즘을 인덱스로 실행하며 union시에 통로 길이 합을 더해주었습니다. 아래는 소스 코드입니다.소스 코드import java.util.ArrayList;import java.util.Col..
Java
문제https://www.acmicpc.net/problem/20310 풀이0과 1로 이루어진 문자열 S가 있으면, 0과 1을 절반씩 제거하는데 사전 순으로 가장 빠른 것을 구하는 문제입니다. 아이디어를 생각해보면, 사전 순이라는 것은 0이 1보다 우선이라는 얘기입니다. 다르게 말하면, 제거할 때 0은 뒤에서부터 제거하여 최대한 앞의 0을 남겨야하고, 1은 앞에서부터 제거하여 사전 순을 미루어야합니다. 전체 문자열 중 0과 1의 숫자를 구하고, 0은 뒤에서 1은 앞에서 인덱스를 찾아가며 각각의 절반에 다다르면 while문을 종료합니다. 아래는 소스 코드입니다.소스 코드import java.util.Scanner;public class Main { public static void main(St..
문제https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이 구현 문제인데, 구현도 구현이지만 자료 구조를 얼마나 잘 이해하고 쓰는지가 중요한 문제라고 생각했습니다. 이 문제를 풀면서, 구현과 시간 초과를 내지 않기 위해 생각했던 중요한 포인트 두 가지는 조합을 구현하는 것과 Map 자료 구조를 사용하는 것이었습니다. 조합을 구현할 때에, 손님을 순차적으로 돌며 손님이 주문한 메뉴 내에서만 조합을 통해 문자열을 찾아내었습니다. 그리고 조합을 통해..
문제https://www.acmicpc.net/problem/1138 풀이 이 문제의 포인트는 큰 숫자부터 LinkedList에 집어넣는다 라고 생각합니다. 76 1 1 1 2 0 0 :왼쪽의 자기보다 큰 수의 개수1 2 3 4 5 6 7 :idx 예제 4번입니다. 여기서 가장 큰 수인 idx=7 부터 LinkedList에 집어넣습니다. LinkedList : 7 그리고 idx 6을 집어넣는데 arr값이 0이므로 왼쪽에 큰 값이 없습니다. LinkedList : 6 7 idx 5는 arr값이 2입니다. 왼쪽에 자기보다 큰 값이 2개이므로 아래와 같습니다. LinkedList : 6 7 5 이렇게 반복해나가다보면 결국, LinkedList라는 삽입이 용이한 자료구조 특성상, 인덱스를 지정해서 Linked..
문제https://school.programmers.co.kr/learn/courses/30/lessons/67256 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이구현 문제입니다. 우선 키패드 간의 거리는 행렬 격자 상에 있다고 가정했습니다. 키패드를 누를 때마다 현재 left, right의 위치가 갱신됩니다. 그리고 다음 번호와 left, right의 거리를 비교해야합니다. 저는 각 번호를 행렬의 열과 행으로 바꾸어준 뒤, Math.abs(r1-r2)+Math.abs(c1-c2)의 식을 통해 거리를 계산했습니다. 해당 번호를 각각의 행과 열로 표현..
문제https://www.acmicpc.net/problem/17266풀이세 가지 구역을 체크했습니다. 길 시작점부터 첫 가로등까지의 구역, 가로등과 가로등 사이의 구역, 그리고 마지막 가로등과 도착점의 구역입니다. 세 가지 구역의 특징은 가로등과 가로등 사이면, 사이의 구간을 두 개의 가로등이 절반씩 나눠서 커버할 수 있다는 것이고 시작 구역과 도착 구역은 가로등 하나가 온전히 구간을 커버해야합니다. 그래서 아래처럼 세 구간으로 나누어 커버 범위의 최대 값을 구해주었습니다. 주의해야할 것은 만약 가로등과 가로등 사이 구간의 길이가 홀수라면, 사이의 길이/2 +1을 해주어야 한다는 것입니다. 홀수를 2로 나누기만 하면 중간을 커버하지 못하게 됩니다. (3이면 3/2 -> 1, 그러나 3을 1 두개로..
