메모리: 67.2 MB, 시간: 8.99 ms - Answer Code1(2022.02.20)
메모리: 72.9 MB, 시간: 0.09 ms - Answer Code2(2022.02.23)
import java.util.*;
class Solution {
public int solution(int n, int k) {
int answer = 0;
String temp = "";
//N진법 변환
while(n != 0) {
temp = n % k + temp;
n /= k;
}
String [] arr = temp.split("0");
for(String str : arr) {
if(str.equals("")) {
continue;
}
long num = Long.parseLong(str);
if(isPrime(num)) {
answer++;
}
}
return answer;
}
// 소수 확인 메서드
public boolean isPrime(long decimal) {
if(decimal < 2)
return false;
for(int i = 2; i <= Math.sqrt(decimal); i++) {
if(decimal % i == 0) {
return false;
}
}
return true;
}
}
소수 판별 알고리즘 문제였다.
처음에 문제에 대한 설명을 보고 도무지 이해가 안되어서 가만히 생각해봤는데, 0
을 기준으로 분해시켜서 개수를 구하면 되는 문제였다.
[1] N진법 로직으로 구현한다.
[2] N진법으로 푼 문자열을 0
을 기준으로 Split 한다.
주의 1) 1001 처럼 가운데 0이 있는 상태로 분해할 경우 1, “”, 1이 반환이 된다. 빈칸을 숫자로 변환하면 오류가 생기니 이런 경우를 제외해야 한다.
주의 2) 변환할 때 숫자를 Long 타입으로 바꿔야한다. 최대 100만이라는 숫자를 N진법으로 변환하면 엄청난 길의 숫자가 나열되고, int의 범위를 넘어서는 숫자가 생성되기 때문이다.
소수를 판별할 때는 에라토네스 체를 사용하는 걸 권장한다. 권장한 이유는 연산을 최대한 많이 줄이면서 소수인지 판별이 가능하기 때문이다.
class Solution {
public int solution(int n, int k) {
int ans = 0;
String temp[] = Integer.toString(n, k).split("0");
Loop : for(String t : temp) {
if(t.length() == 0) continue;
long a = Long.parseLong(t);
if(a == 1) continue;
for(int i=2; i<=Math.sqrt(a); i++)
if(a%i == 0) continue Loop;
ans++;
}
return ans;
}
}
두 번째 풀이는 좋아요 수가 많은 답안인데, 정말 깔끔한 풀이였다.
10진수 -> k진수로 변경은 String.valueOf(바꾸려는 숫자(10진수), 바꾸려는 k진법)
으로 간단하게 구현 가능하는 것을 구글링을 통해 알게 되었다.
Prime() 메서드를 단 세줄로 작성했다는 점에서 성능이 8배 가까이 개선되었다.
SELECT ANIMAL_ID, NAME, DATE_FORMAT(DATETIME, '%Y-%m-%d') AS DATETIME
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
DATE_FORMAT(DATETIME, '%Y-%m-%d')
을 사용해야 한다.SELECT ANIMAL_ID, NAME,
IF((SEX_UPON_INTAKE LIKE "%Neutered%") OR (SEX_UPON_INTAKE LIKE "%Spayed%"), "O", "X") AS "중성화"
FROM ANIMAL_INS
ORDER BY ANIMAL_ID;
SELECT ANIMAL_ID, NAME,
CASE WHEN (SEX_UPON_INTAKE LIKE '%NEUTERED%' OR SEX_UPON_INTAKE LIKE '%SPAYED%') THEN 'O' ELSE 'X' END AS '중성화'
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
SELECT ANIMAL_ID, NAME
FROM ANIMAL_INS
WHERE ANIMAL_TYPE = "Dog" AND NAME LIKE "%EL%"
ORDER BY NAME ASC
요약 : 동물 보호소에 들어온 동물 이름 중, 이름에 “EL”이 들어가는 개의 아이디와 이름을 조회하는 SQL문을 작성해주세요.
이때 결과는 이름 순으로 조회해주세요.
단, 이름의 대소문자는 구분하지 않습니다.
특정 부분이 일치하는 데이터를 찾고싶을때는 LIKE를 이용는데, 주로 _
혹은 %
를 이용한다.
_
은 개수만큼 데이터가 있다는 의미로, __EL__
의 의미는 앞뒤에 데이터의 개수가 2개 있다는 의미이다.
%
은 글자수와 상관없이 데이터를 찾는 것을 의미하는데, %EL
은 끝자리인 EL 데이터를 찾는것이고, EL%
은 앞자리에 EL 데이터를 찾는다는 의미이다.
%EL%
은 앞뒤 상관없이 EL이 포함된 데이터를 찾는다는 것이다.
import java.util.ArrayList;
import java.util.HashMap;
class Solution {
public int[] solution(String msg) {
ArrayList<Integer> arr = new ArrayList<>();
HashMap<String, Integer> hm = new HashMap<>();
// [1] HashMap 알파벳으로 초기화
for(int i = 'A'; i <= 'Z'; i++) {
hm.put((char)i + "", i+1 - 'A');
}
for(int i = 0; i < msg.length(); i++) {
int idx = i + 1;
// [2] msg 길이만큼 반복
while(idx <= msg.length()) {
// [3] idx가 문자열 끝까지 도달하면 해당 인덱스를 결과 배열에 추가
// 초기 반복문을 빠져나오기 위해 i를 idx로 초기화
if(idx == msg.length()) {
arr.add(hm.get(msg.substring(i)));
i = idx;
break;
}
// [4] 다음 키 미리 계산(다음 키를 확인하기 위해 초기 반복문의 i보다 한칸 큰 idx 선언)
String nextKey = msg.substring(i, idx + 1);
// [5] 다음 키가 있을 경우 문자를 하나 추가하기 위해 idx 증가
if(hm.containsKey(nextKey))
idx++;
// [6] 다음 키가 없을 경우
else {
// [6-1] 결과 배열에 현재 키의 인덱스를 추가
arr.add(hm.get(msg.substring(i, idx)));
// [6-2] 현재 해쉬에 없는 다음 키를 해쉬에 추가
hm.put(nextKey, hm.size() + 1);
// [6-3] 문자의 idx-1 까지 처리했음으로 i를 idx-1로 초기화(밖에 반복문 시작시 i++ 되므로 idx-1로 초기화)
i = idx - 1;
break;
}
}
}
// [7] ArrayList를 int []로 변환
int[] answer = new int[arr.size()];
for(int i = 0; i < arr.size(); i++) {
answer[i] = arr.get(i);
}
return answer;
}
}
HashMap<문자열(키), 자연수(키에서 몇 번째 인덱스인지)>를 만들어서 구하는 문자열 처리 관련 문제였다.
문제 설명 이해하는 데 어려움이 있었고, [3] ~ [6] 부분에 대한 구현 아이디어가 떠오르지 않았다.
구현에 대한 아이디어는 yline 풀이를 참고했다.
해당 문제는 풀이에 대한 코드 해석도 어려웠기 때문에 반드시 다시 풀어보자.
메모리: 52.4 MB, 시간: 202.81 ms - Answer Code1(2023.02.20)
메모리: 56 MB, 시간: 17.91 ms - Answer Code2(2023.02.24)
class Solution {
public int solution(int n) {
boolean flag; // 소수이면 true, 아니면 false
int answer = 0;
//에라토스테네스의 법칙
for(int i = 2; i <= n; i++) {
flag = true;
for(int j = 2; j <= Math.sqrt(i); j++) {
if(i%j == 0) {
flag = false;
break;
}
}
// flag = true, 소수값이므로 +1 추가
if(flag == true) {
answer++;
}
}
return answer;
}
}
class Solution {
public int solution(int n) {
int answer = 0;
int[] arr = new int[n + 1];
for (int i = 2; i <= (int) Math.sqrt(n); ++i) {
if (arr[i] == 1) continue;
for (int j = i + i; j <= n; j += i) {
arr[j] = 1;
}
}
for (int i = 2; i < arr.length; ++i) {
if (arr[i] != 1) ++answer;
}
return answer;
}
}
첫 번째 풀이는 시간이 너무 걸리고 효율성 테스트가 너무 높게 나와서, 해당 문제점을 개선하기 위해 다시 풀었다.
두 번째 풀이의 아이디어는 밈아님의 소수찾기 풀이방법를 통해 알 수 있었다. (밈아님 감사합니다)
[1] 입력 받는 n 값이 커질 수록 반복문이 도는 횟수도 더 많아지므로, 반복문을 n번 돌리는 것이 아닌 n의 제곱근번을 돌리게 하여 반복문 실행 횟수를 줄이도록 했다.
[2] 그리고 첫 번째 풀이 방법에서 n번 반복되는 코드와 달리 두 번째 풀이 방법에는 소수의 개수를 체크하는 for문을 따로 빼냈다.