박카스러버

https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 저는 해당 문제를 크루스칼을 통해서 문제를 해결하였습니다. 크루스칼을 통해 MST를 구성하면서 가장 작은 가중치의 합을 구하였습니다. import java.util.*; class Solution { public int solution(int n, int[][] costs) { int answer = kruskal(n,costs); return answer; } private int findSet(int now, int[] parent){ if(now == p..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 저는 이분탐색을 통해 문제를 해결하였습니다. 이분 탐색을 통해 해당 시간이 해당 인원을 검사할 수 있는지 판단하였습니다. 해당 인원을 검사할 수 있는 시간이 된다면 end를 줄이고, 검사할 시간이 안된다면 start를 늘려가면서 검사에 필요한 최소 시간을 찾아나갔습니다. class Solution { public long solution(int n, int[] t..

https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 저는 재귀를 통해 해당 문제를 해결하였습니다. 전체를 3으로 이동시키기 위해서는 맨 밑을 제외한 것을 모두 2에 옮겨야하고 맽 밑을 3으로 옮겨야합니다. 이 위층 또한 같은 매커니즘입니다. 맨 밑을 제외한 것을 모두 2에 옮기려면 맨 밑에서 2개를 제외한 것을 3으로 옮겨야합니다..... 위의 로직을 재귀를 통해 구현하였습니다. impor..

https://programmers.co.kr/learn/courses/30/lessons/12924 코딩테스트 연습 - 숫자의 표현 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 programmers.co.kr 저는 투포인트를 이용해 문제를 해결하였습니다. 저는 투 포인트를 통해 사이 간격의 합을 구하였고, 이 합이 n과 같다면 결과를 늘렸습니다. 끝포인트가 n을 넘기면 바로 끝나도록 구현하였습니다. class Solution { public int solution(int n) { int answer = countSumCnt(n); return an..

https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 저는 여는 괄호의 개수를 세어 문제를 해결하였습니다. 여는 괄호가 나오면 cnt를 늘려고 닫는 괄호면 cnt를 줄였습니다. cnt가 0 미만으로 떨어지면 그 순간은 )가 하나 더 많은 것이기 때문에 바로 false를 리턴하였습니다. 또한 for문을 다 돌고 cnt가 0이 아니라면 남는 괄호가 존재하는 것이기 때문에 이..

https://programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 저는 해당 문제를 dp를 이용하여 문제를 해결하였습니다. 저는 DP를 통해 해당 위치까지 가는데 몇개의 경로가 있는지 저장하였습니다. import java.util.*; class Solution { private static final int LIMIT = 1234567; private static fi..

https://programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 저는 해당 문제를 문자열을 처리하여 해결하였습니다. 먼저 저는 문제의 조건을 만족하면서 다음 수는 어떻게 구해야할까를 고민하였습니다. 저는 뒤에서부터 찾아가면서 처음 1을 발견하고 나서 0을 발견한 곳을 구하고 이를 1과 자리를 옮겨주고 뒤에있는 1들은 낮은 자리부터 채워나가면 된다는 규칙을 찾았습니다. 저는 뒤에서부터 찾아가면서..

https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 저는 스택을 통해 문제를 해결하였습니다. 스택은 현재 가격보다 작은 인덱스를 가지고 있게 하여 해당 값이 작다면 현재 인덱스를 비교하여 가격이 안 떨어지고 얼마나 있었는지를 계산하였습니다. import java.util.*; class Solution { public int[] solution(int[] prices) {..

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 저는 해당 문제를 그리디를 이용해 문제를 해결하였습니다. 먼저 저는 각각의 문자를 비교하여 앞에서부터 앞의 숫자가 뒤의 숫자보다 작다면 지웠습니다. 그리고 지운 횟수를 체크하면 이 값이 k보다 커지면 바로 for문에서 나오도록 구현하였습니다. 마지막으로 cnt가 k보다 작은데 for문이 끝나거나서 숫자가 모두 같거나 마지막 숫자를 지워야하는 경우가 존재하기 때문에 while문을 돌려 뒤에서부터 문자를 지워나갔습니다. class Solution { public String solution(String number, int k) { Strin..

https://programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 저는 dp를 이용해 문제를 해결하였습니다. dp[depth] = dp[depth -1] + dp[depth -2] 공식을 세워 dp를 풀었습니다. class Solution { private static final int LIMIT = 1_000_000_007; private static final int NOT_VALID = 0; public in..