알고리즘 문제풀이/프로그래머스
-
프로그래머스 타겟넘버 자바(java) 풀이 Level 2 BFS/DFS 타겟넘버 문제 정리 n개의 음이아닌 정수가 있다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하여라 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1이상 50이하의 자연수 이다. 문제 풀이 이 문제가 프로그래머스에는 BFS/DFS로 분류되어 있지만 저는 조합을 이용하여 풀었습니다. 조합을 이용하여 모든 경우의 수를 따져주었습니다. 1,2,...len개 선택하는 경우 모두 따져주었습니다. len(numbers의 개수) 개중 i개 선택하기 예를들어 1개를 선택한다면 1개만 visited가 true로 될 것입니다. 그러면 하나만 더하기..
[조합] 프로그래머스 level2 타겟넘버 자바 풀이프로그래머스 타겟넘버 자바(java) 풀이 Level 2 BFS/DFS 타겟넘버 문제 정리 n개의 음이아닌 정수가 있다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하여라 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1이상 50이하의 자연수 이다. 문제 풀이 이 문제가 프로그래머스에는 BFS/DFS로 분류되어 있지만 저는 조합을 이용하여 풀었습니다. 조합을 이용하여 모든 경우의 수를 따져주었습니다. 1,2,...len개 선택하는 경우 모두 따져주었습니다. len(numbers의 개수) 개중 i개 선택하기 예를들어 1개를 선택한다면 1개만 visited가 true로 될 것입니다. 그러면 하나만 더하기..
2020.05.08 -
프로그래머스 카펫 자바(java) 풀이 Level 2 완전탐색 카펫 문제 정리 카펫은 중앙에는 빨간색, 테두리 1줄은 갈색으로 칠해져 있었다. 카펫의 갈색격자 수, 빨간색 격자 수는 알고 있다. 카펫의 가로, 세로 크기를 순서대로 담아 return 하여라. 카펫의 가로 길이 >= 세로길이 문제 풀이(Solution) level2의 문제이지만 level1이 더 맞지 않나 생각합니다. 카펫의 갈색의 개수와 빨간색의 개수를 더하여 카펫에서 총 격자의 개수를 구합니다. 총 격자 개수의 약수의 쌍을 구합니다. brown=10, red=2 인 경우 총 격자의 개수는 12입니다. 이때 카펫은 다음과 같이 가능합니다(1,12), (2,6), (3,4), (4,3), (6,2), (12,1)하지만 행의 길이가 3보다 작..
[완전탐색, 약수] 프로그래머스 level2 카펫 자바 풀이프로그래머스 카펫 자바(java) 풀이 Level 2 완전탐색 카펫 문제 정리 카펫은 중앙에는 빨간색, 테두리 1줄은 갈색으로 칠해져 있었다. 카펫의 갈색격자 수, 빨간색 격자 수는 알고 있다. 카펫의 가로, 세로 크기를 순서대로 담아 return 하여라. 카펫의 가로 길이 >= 세로길이 문제 풀이(Solution) level2의 문제이지만 level1이 더 맞지 않나 생각합니다. 카펫의 갈색의 개수와 빨간색의 개수를 더하여 카펫에서 총 격자의 개수를 구합니다. 총 격자 개수의 약수의 쌍을 구합니다. brown=10, red=2 인 경우 총 격자의 개수는 12입니다. 이때 카펫은 다음과 같이 가능합니다(1,12), (2,6), (3,4), (4,3), (6,2), (12,1)하지만 행의 길이가 3보다 작..
2020.05.08 -
프로그래머스 소수찾기 자바(java) 풀이 Level 2 완전 탐색 소수 찾기 문제 정리 한자리 숫자가 적힌 종이가 있다. 종이 조각으로 만들 수 있는 소수가 몇 개 인지 return 하여라. 입력으로 주어지는 numbers는 길이 1 이상 7 이하의 문자열이다. 문제 풀이 numbers를 파싱하여 이용해서 만들 수 있는 모든 수를 만든 후 소수인지 확인합니다. 모든 순열을 확인합니다. n개의 수중 1,2,3..n개를 뽑는 모든 순열을 구합니다. 구한 문자를 숫자로 바꾸어 소수인지 판단합니다. 소수라면 set에 저장합니다. set에 저장하는 이유는 중복된 숫자를 방지하기 위함입니다. 소수인지 판단은 그 수의 루트값 까지 나눠보면 알 수 있습니다. 순열(Permutaion) 오랜만에 순열을 구현하려니 생각..
[완전탐색, 소수, 순열] level2 프로그래머스 소수 찾기 자바 풀이프로그래머스 소수찾기 자바(java) 풀이 Level 2 완전 탐색 소수 찾기 문제 정리 한자리 숫자가 적힌 종이가 있다. 종이 조각으로 만들 수 있는 소수가 몇 개 인지 return 하여라. 입력으로 주어지는 numbers는 길이 1 이상 7 이하의 문자열이다. 문제 풀이 numbers를 파싱하여 이용해서 만들 수 있는 모든 수를 만든 후 소수인지 확인합니다. 모든 순열을 확인합니다. n개의 수중 1,2,3..n개를 뽑는 모든 순열을 구합니다. 구한 문자를 숫자로 바꾸어 소수인지 판단합니다. 소수라면 set에 저장합니다. set에 저장하는 이유는 중복된 숫자를 방지하기 위함입니다. 소수인지 판단은 그 수의 루트값 까지 나눠보면 알 수 있습니다. 순열(Permutaion) 오랜만에 순열을 구현하려니 생각..
2020.05.04 -
프로그래머스 연습문제 제일 작은 수 제거하기 자바 풀이 Level 1 제일 작은 수 제거하기 문제 정리 주어진 배열에서 가장 작은 수를 제거한 배열을 리턴하여라. 배열에 숫자가 하나밖에 없다면 -1을 담은 배열을 리턴하여라. 배열에 주어진 수는 모두 다르다 문제 풀이 배열을 오름차순이나 내림차순으로 정렬해서 제거하면 안됩니다. 주어진 원소 순서대로 출력해야 합니다. 가장 작은 수의 인덱스를 찾습니다. 그 인덱스의 수만 빼고 새로운 배열에 숫자를 모두 넣습니다. 그러면 원래 순서대로 들어가게 됩니다. 문제 풀이 class Solution { public static void main(String[] args){ int[] arr = {4,3,2,1}; int[] arr2 = {10}; // debug in..
[최소값 찾기] level1 프로그래머스 제일 작은 수 제거하기 자바 풀이프로그래머스 연습문제 제일 작은 수 제거하기 자바 풀이 Level 1 제일 작은 수 제거하기 문제 정리 주어진 배열에서 가장 작은 수를 제거한 배열을 리턴하여라. 배열에 숫자가 하나밖에 없다면 -1을 담은 배열을 리턴하여라. 배열에 주어진 수는 모두 다르다 문제 풀이 배열을 오름차순이나 내림차순으로 정렬해서 제거하면 안됩니다. 주어진 원소 순서대로 출력해야 합니다. 가장 작은 수의 인덱스를 찾습니다. 그 인덱스의 수만 빼고 새로운 배열에 숫자를 모두 넣습니다. 그러면 원래 순서대로 들어가게 됩니다. 문제 풀이 class Solution { public static void main(String[] args){ int[] arr = {4,3,2,1}; int[] arr2 = {10}; // debug in..
2020.04.22 -
프로그래머스 연습문제 x만큼 간격이 있는 n개의 숫자 자바 풀이 Level 1 x 만큼 간격이 있는 n개의 숫자 문제 정리 정수 x와 자연수 n이 주어질때 x부터 시작해 x씩 증가하는 숫자 n개를 리스트에 담아 return 한다. 문제 풀이 x는 최대 천만이고 그걸 1000번 더할 수 있으므로 int형을 넘게 되므로 리스트는 long형이어야 합니다.(자바 기준) for문을 반복하며 x의 배수를 모두 배열에 넣어주면 됩니다. 이때 주의할 점은 i와 x의 곱 계산시 int형으로만 계산되기 때문에 int 범위를 넘는 값은 answer 배열에 제대로 담을 수 없습니다. 그렇기 때문에 처음에 x를 long형으로 바꾸어 계산합니다. 자바 코드 class Solution{ public static long[] sol..
[for문] level1 프로그래머스 x만큼 간격이 있는 n개의 숫자 자바, 파이썬 풀이프로그래머스 연습문제 x만큼 간격이 있는 n개의 숫자 자바 풀이 Level 1 x 만큼 간격이 있는 n개의 숫자 문제 정리 정수 x와 자연수 n이 주어질때 x부터 시작해 x씩 증가하는 숫자 n개를 리스트에 담아 return 한다. 문제 풀이 x는 최대 천만이고 그걸 1000번 더할 수 있으므로 int형을 넘게 되므로 리스트는 long형이어야 합니다.(자바 기준) for문을 반복하며 x의 배수를 모두 배열에 넣어주면 됩니다. 이때 주의할 점은 i와 x의 곱 계산시 int형으로만 계산되기 때문에 int 범위를 넘는 값은 answer 배열에 제대로 담을 수 없습니다. 그렇기 때문에 처음에 x를 long형으로 바꾸어 계산합니다. 자바 코드 class Solution{ public static long[] sol..
2020.04.22 -
프로그래머스 연습문제 정수 제곱근 판별 풀이 Level 1 정수 제곱근 판별 문제 정리 양의 정수 n이 주어질때 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 한다. n이 어떤 정수 x의 제곱이라면 (x+1)^2을 리턴 아니라면 -1을 리턴한다. 문제 풀이 주어진 수 n을 루트 취해본다. 취한 값이 floor한 값과의 차이가 없다면 n은 Math.sqrt(n)의 제곱이 된다. 예를들어 121이라면 루트를 했을때 11입니다. 이 경우 floor한 값은 그대로 11 입니다. 뒤의 소수점이 없기 때문입니다. 이 경우 (Math.sqrt(a)+1)^2을 구합니다. 만약 어떤 수의 제곱이 아니라면 루트를 취했을때 뒤에 소수점이 남기 때문에 floor한 값과 차이는 0이 아니게 됩니다. 프로그래머스 정수 제곱근 판..
[수학] level1 프로그래머스 정수 제곱근 판별 자바(java) 풀이프로그래머스 연습문제 정수 제곱근 판별 풀이 Level 1 정수 제곱근 판별 문제 정리 양의 정수 n이 주어질때 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 한다. n이 어떤 정수 x의 제곱이라면 (x+1)^2을 리턴 아니라면 -1을 리턴한다. 문제 풀이 주어진 수 n을 루트 취해본다. 취한 값이 floor한 값과의 차이가 없다면 n은 Math.sqrt(n)의 제곱이 된다. 예를들어 121이라면 루트를 했을때 11입니다. 이 경우 floor한 값은 그대로 11 입니다. 뒤의 소수점이 없기 때문입니다. 이 경우 (Math.sqrt(a)+1)^2을 구합니다. 만약 어떤 수의 제곱이 아니라면 루트를 취했을때 뒤에 소수점이 남기 때문에 floor한 값과 차이는 0이 아니게 됩니다. 프로그래머스 정수 제곱근 판..
2020.04.22