본문 바로가기

Algorithm

(140)
Programmers - k진수에서 소수 개수 구하기 with JAVA 문제 N(1 소수 체크시 Long처리를 해야한다. (N의 최대는 100만이고 K의 최소는 3이다. 따라서 3진법으로 100만을 나타낸다면 숫자가 굉장히 커지고 int로 담아낼 수 없다.) -> 소수 체크는 해당 값의 제곱근 + 1까지 구하고 이때까지 해당 수를 나머지 없이 나눌 수 없다면 소수이다. -> 1은 소수가 아니다. 항상, 런타임 오류가 발생하면 웬만하면 범위 초가인 듯 하다. 코드 import java.util.*; class Solution { public int solution(int n, int k) { int answer = 0; StringBuilder check = new StringBuilder(); while(true){ check.insert(0, String.valueOf(n..
Programmers - 소수 만들기 with JAVA 문제 nums라는 배열에서 서로 다른 인덱스의 위치한 3개의 수를 골라 소수를 만들 때, 만들 수 있는 소수의 개수를 구하라. 해결 이 문제는 굉장히 간단하나 소수를 구할 때, 에라토스테네스 공식을 쓰면 아주 시간 복잡도가 개선됨을 깨달았고 Boolean[] 이 아닌 boolean[] 처리시 초기값이 모두 false 처리 됨을 몰랐던 나의 무지함을 기록하기 위해 작성한다. 에라토스테네스의 공식은 간단하게 2부터 시작하여 해당 수를 곱한 모든 수는 소수이다. 예를 들어, 2*2, 2*3, 2*4 ... 3*3, 3*4.... 모두 소수이다 따라서 소수를 미리 체크하고 모든 수 하나하나를 소수 체크할 필요없이 미리 처리해놓는 방식이다. 문제에서 3가지 수로 만들수 있는 가장 큰수가 3000이므로 범위를 아래..
Programmers - 도둑질 with JAVA 문제 문제는 다음과 같다. 집마다 가지고 있는 돈이 정해져있고 도둑은 집을 털어서 최대한 많은 돈을 훔치려고 한다. 이 때, 인접해있는 집은 털 수 없으며, 집의 구조는 원의 형태를 갖고 있다. [1, 2, 3, 1] 이 있을 때, 인덱스 0을 털면 마지막 인덱스는 털 수 없다. 로직 기본적으로 이런 DP 문제의 해결방법은 간단하다. dp[0] = 인덱스 0까지 존재한다고 했을 때 털 수 있는 돈의 최대치 dp[1] = 인덱스 0~1까지 존재한다고 했을 때 털 수 있는 돈의 최대치 dp[2] = 인덱스 0~2까지 존재한다고 했을 때 털 수 있는 돈의 최대치 ... 하지만 이 문제는 좀 다르다 집의 구조가 원형이기에 처음인덱스를 털면 마지막인덱스를 털 수 없게 된다. 해결방법은 두개의 리스트를 만들어 값을..
Programmers - N개의 최소공배수 with JAVA (V) 문제 배열로 숫자 리스트가 주어질 떄, 모든 수의 최소 공배수를 구하라. 로직 - 두 수의 최대 공약수를 구한다. - 두 수의 최소 공배수 = AxB/최대공약수 - 반복 - 또는 아래 다른 공식 활용 a%b==c 일때, b%c가 0이될때까지 반복하는 방식 코드 import java.util.*; class Solution { public int solution(int[] arr) { Arrays.sort(arr); int length = arr.length; int now_value = arr[length-1]; for(int i=length-2; i>=0; i--){ int value = arr[i]; while(true){ if(now_value % value == 0 && arr[i] % value..
Programmers - 예상 대진표 with JAVA (V) 문제 N명의 사람이 대진표를 따라 경기를 진행하는데 A,B는 몇번째 경기에 만날것인지 구하라 로직 만나는 경우는 항상 같다 (1, 2), (3, 4), (5, 6) 과 같이 첫번째 인덱스가 홀수이면서 1차이가 나야한다. 예를 들어, (2, 3)과 같은 경우는 안된다. 또한 위의 경우에 해당하지 않는다면 각각의 인덱스를 2로 나누고 올림처리를 하면 된다. 예를 들어, 인덱스 4라고 가정한다면, 4는 3과 경기를 하고 이기면 2가 되는 방식인 것이다. 코드 class Solution{ public int solution(int n, int a, int b){ int answer = 1; int x = Math.min(a, b); int y = Math.max(a, b); while(true){ if(x%2 ..
Programmers - 크기가 작은 부분 문자열 with JAVA (V) 문제는 굉장히 간단하나 실수가 하나있어 기록을 한다. 문제에서 문자열의 주어진 범위는 10000이다. 즉, 문자열의 최대 범위는 1000이고 이를 숫자로 변환시 굉장히 숫자가 커진다. 따라서, Integer가 아닌 Long으로 변환을 해야 처리가 가능하다. class Solution { public int solution(String t, String p) { int answer = 0; int p_size = p.length(); for(int i=0; i
Programmers - 짝지어 제거하기 with JAVA 문제 소문자로 이루어진 문자열이 주어지고 같은 글자를 짝지어 삭제하여 모든 문자열을 삭제가능한지를 확인하는 문제이다. 해결 스택을 해결하여 간단히 해결가능하다. 예를들어, baabaa가 있을 때, 처음에는 b를 넣는다. 그 이 후, a를 넣는데, 스택에 마지막 값과 비교해 같으면 넣지 않고 마지막 인덱스를 제거하고 다르면 넣는다 따라서, a는 들어간다. 그 이 후, a가 제거되므로 b만 남는데, 이 후, b가 들어오므로 모두 제거된다. 이런식으로 해결해 결과적으로 스택이 모두 비면 1 아니면 0을 반환한다. 코드 import java.util.*; class Solution{ public int solution(String s){ if(s.length() == 0 | s.length() == 1){ re..
Programmers - N으로 표현 with JAVA (V) 문제 주어진 N이라는 숫자와 사칙연산을 가지고 number라는 숫자를 만들 떄, N이라는 숫자를 최소한으로 사용해 만들고자 한다. 이 떄, 최소한의 개수를 구하라. 로직 ( DP : i개의 N으로 만들 수 있는 수) 1. 우선적으로, 만약 N==number라면 숫자 1개로 number를 만들 수 있으므로 1을 return 한다. 2. 문제에서 주어진 N을 사용할 수 있는 횟수는 최대 8회이다. 따라서 1회부터 8회까지 만들 수 있는 리스트를 담을 dp를 선언한다. (Set을 사용하여 중복을 허용하지 않는다.) 3. 초기값으로 그냥 HashSet을 넣는다. (인덱스 0을 위함.) 4. 1개로 만들 수 있는 수는 N밖에 없으므로 그대로 넣는다. 5. 이 후 2개를 사용하여 만들 수 있는 수부터 8개를 사용하..