[JAVA] 알고리즘 LV.1 추가 학습 정리
학습 출처 : 프로그래머스
모든 문제가 프로그래머로써 입문단계라는게 놀라웠다
기초단계는 아직 시작도 안했다는 것..
문제도 아직 남았지만 CS지식도 학습해야하기 때문에
마무리 겸 복습을 해보자.
스킬체크
- 입력 받은 문자열을 공백을 포함하여 함께 나누고 인덱스 짝수번째, 홀수번째의 문자를 대문자, 소문자로 치환하기
받은 문자열을 문자배열에 하나씩 넣어줄 때
String[] str = s.split("");그 중에 공백을 찾아서 변수를 리셋해주고 나머지 글자가 짝수번째인 경우에는 대문자, 홀수번째인 경우에는 소문자로 바꿀 때
for(int i=0; i<str.length; i++) {
if(str[i].equals(" ")) {
idx = 0;
} else if(idx % 2 == 0) {
str[i] = str[i].toUpperCase();
idx++;
} else {
str[i] = str[i].toLowerCase();
idx++;
}
answer += str[i];
- 입력받은 숫자를 문자열로 반환하고 각 요소들을 더해서 다시 정수로 반환해주기
매개변수를 문자열로 반환할 때
public int solution(int n) {
String str = Integer.toString(n);문자열로 받은 정수들을 반복문을 통해 더하고 다시 정수값으로 결과를 반환할 때
for(int i = 0; i < str.length(); i++){
answer += Integer.parseInt(str.substring(i, i+1));
}Wrapper class가 가지고 있는 toString, parseInt, parseDouble 등 받은 값을 원하는 형태로 바꿔주는 메소드이고 자주 사용하니 사용법을 익혀두자
- 받은 자연수 값의 순서를 뒤집어서 배열로 만들기
class Solution {
public int[] solution(long n) {
long num = n;
int cnt = 0;
while(num != 0){
num /= 10;
cnt++;
}
int[] answer = new int[cnt];
num = n;
for(int i = 0; num != 0; i++){
answer[i] = (int)(num % 10);
num /= 10;
}
return answer;
}
}- num /= 10, num % 10 은 while, for 문에서 자주 등장한다.
- n = 12345일 때 answer = [5,4,3,2,1]로 바꿔주려면 각 요소를 10으로 먼저 나누고 반복문을 통해 변수 num에 대입
while(num != 0){
num /= 10;
// 12345 = 1234
// 1234 = 123
// 123 = 12
// 12 = 1
// 1 = 0 ( 0.1 )
cnt++;3. cnt를 이용하여 새로운 길이의 배열을 만든다.
4.num 변수를 다시 입력받은 값 n으로 초기화 시킨 후 10으로 나눈 나머지 값을 answer [ i ] 의 요소에 대입해주고 위에서 10을 나눈 방식으로 num에 대입해서 반복문을 실행시키면 원하는 [5,4,3,2,1] 형태의 배열을 반환할 수 있다.
num = n;
for(int i = 0; num != 0; i++){
answer[i] = (int)(num % 10);
num /= 10;
}
// 1) 12345 % 10 = 5
// 2) 1234 % 10 = 4
// 3) 123 % 10 = 3
// 4) 12 % 10 = 2
// 5) 1 % 10 = 1
다른 사람의 풀이
문자열을로 숫자를 "" 를 이용해서 바로 치환하니까 코드가 훨씬 가독성이 좋고 간소해졌다. 어쨌든 핵심은 10으로 나눈값, 10으로 나눈 나머지값이 어떻게 활용되는지를 꼭 기억해두자.
class Solution {
public int[] solution(long n) {
String a = "" + n;
int[] answer = new int[a.length()];
int cnt=0;
while(n>0) {
answer[cnt]=(int)(n%10);
n/=10;
System.out.println(n);
cnt++;
}
return answer;
}
}
- 받은 정수값을 큰수에서 작은수 순서로 리턴해주기
입력받는 매개변수 n의 요소를 뽑아내서 split을 통해 list 배열에 한 문자씩 담는다.
그리고 Arrays 클래스 sort함수를 이용하고 Collections 클래스의 reverseOrder 메소드를 이용하여 역순으로 정렬한다.
import java.util.*;
String[] list = String.valueOf(n).split("");
Arrays.sort(list, Collections.reverseOrder());StringBuilder 객체를 만들고 반복문을 통해 list에 각 요소를 추가한다.
그 후, StringBuilder객체 list에 있는 문자열을 꺼내어 parseLong 메소드를 이용하여 Long타입으로 변환해준다.
StringBuilder sb = new StringBuilder();
for(String s:list) {
sb.append(s);
}
return Long.parseLong(sb.toString());전체적인 알고리즘 풀이 순서를 기억하자(논리적 구조)
- 정수 제곱근 판별 + 응용
// Double wrapper class에 있는 intValue()로 정수형 숫자로 바꾼다.
// 바꾸기 전 숫자와 바꾼 후 숫자가 같으면 정수다.
Double sqrt = Math.sqrt(n);
if(sqrt == sqrt.intValue())
위에서 자주 등장하는 parseInt() 와 intValue()의 차이는 무엇일까?
parseInt()
static 이다, 그러므로 Integer 생성안하고 parameter만 넣어주면 메소드를 수행할 수 있다.
쉽게 말하자면 String형 객체에서 int형 값을 뽑아내는 메소드이다.
Integer 객체 생성하지 않는다
즉, Integer(Object) 라는 박스를 만들지 않고 (래퍼 클래스와 언박싱,오토박싱)
내용물(String) -> 내용물(int) 교체한다.
intValue()
static이 아니며 Integer 객체에서 int형 값을 뽑아내는 메소드이다
Integer는 (int Value와 String Value) 두 가지가 있다.
즉, Object -> int
객체란 박스에서 내용물을 꺼내야 int 라는 내용물로 옮길 수 있다.
언박싱 해줘야 한다.
Integer -> (언박싱) -> int 변환
상황에 맞는 메소드 쓰기
1.내용물 -> 내용물 형변환 Integer.parseInt();
2.객체 -> 내용물 변환 intValue();
그렇다면 다시 문제로 돌아오자
Double sqrt = Math.sqrt(n);
if(sqrt == sqrt.intValue()){
return (long)Math.pow(sqrt + 1, 2);
} else return -1;
}
}sqrt, pow는 모두 double 타입의 값을 반환하기 때문에 sqrt == squrt.intValue 를 비교해서 정수값과 실수값이 같은 경우를 비교해서 제곱근을 만들어줄 수 있는지를 확인이 필요하다.
예를 들어 121 이라는 정수를 n에 넣었다면 sqrt == 11.0을 반환해주고 squrt.intValue == 11을 반환해준다. (형변환 가능)
하지만 155 이라는 정수를 n에 넣으면 sqrt == 12.4498을 반환하고 squrt.intValue == 12를 반환할 것이다.
이하 설명은 생략하겠다. (혹시나 제가 잘 못 알고 있다면.. 댓글부탁합니다 행님,누님들)
- 제일 작은수 제거하기
배열에 가장 작은 수를 제거하고 나머지 요소를 반환해보는 작업이다. 만약에 비교할 대상이 없는 배열인 경우에는 -1을 반환해주면 된다.
[-1]을 반환하는 것은 매우 간단하다.
if(arr.length == 1){
int[] answer = {-1};
return answer;
}그렇다면 이제 새로운 대열이 필요할 것이다.{ arr[0], arr[1], arr[2], arr[3] }길이 4인 배열을 갖고 있는 배열이라면
{arr[0], arr[1], arr[2]}의 길이를 만들어야한다.
길이를 줄이고 변수 min의 값을 최소값으로 변환하여 arr[0]에 담는다.
int[] answer = new int[arr.length-1];
int min = arr[0];
for(int i=1; i<arr.length; i++){
min = Math.min(min, arr[i]);
}그리고 하나의 변수를 선언해주고 원래 4개 길이의 arr[ ] 배열의 요소들이 min의 변수가 가르키는 arr[ 0 ]의 요소와 같은지 비교하여 continue문으로 빠져나가게 해주고 값이 같지 않은 요소가 있다면 answer [ ] 배열에 인덱스를 증감하여 값을 넣어주면 된다.
int index = 0;
for(int i=0; i<arr.length; i++){
if(arr[i] == min){
continue;
}
answer[index++] = arr[i];
}
이제 왠..수학자들이 등장한다
😇
- 콜라츠 추측
1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
작은 함정으로 시작되는 문제다.
주어진 수를 받아서 짝수면 2로 홀수면 3을 곱하고 1을 더하면 모든 수를 1로 만들어 보는 문제이며 아래의 조건을 살펴보자.
- 입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.
- 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.
public int solution(int num) {
long n = num;여기엔 작은 함정이 있다.
만약 626331이라는 정수값을 아래 parameter 변수타입을 int 타입으로 받게 되면 Overflow가 되어 기대하던 값을 받지 못하게 된다.
그렇기 때문에 long 타입으로 매개변수를 받아줄 수 있는 변수를 선언해야한다.
그리고 while 반복문안에 짝수일 때와 홀수 일때의 조건식을 써주고 answer++ 증감시킨다.
answer값이 500일 때는 반복문을 빠져나와 -1을 return하게 해주면 된다.
int answer = 0;
while(n!=1){
if(n % 2 == 0){
n/=2;
}else {
n = 3*n+1;
}answer++;
if(answer == 500){
answer = -1;
break;
}
}
return answer;
- 하샤드 수인지 검사하기
정의 : 만약 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야함.
예시 : 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수
풀이 :
1. 매개변수 x 값을 저장할 수 있는 임의의 harshard 변수를 선언
2. 이전에 자리수 뒤집어서 배열에 넣었던 것 처럼 나누어 떨어지는 수를 구할 때 + while 조건문을 사용할 때 n/10, n%10을 자주 이용한다.
3. if문에서는 x의 값을 받았던 harshar 변수가 아닌 매개변수 x를 기준으로 sum의 나머지가 0이라는 조건을 만족할 때 하샤드 수임이 증명된다.
class Solution {
public boolean solution(int x) {
int sum = 0;
int harshard = x;
while(harshard >= 1){
sum += harshard % 10;
harshard /= 10;
}
if(x % sum == 0){
return true;
}else
return false;
}
}
속도보단 방향이라는 말이 있다.
하지만 때로는 방향보다 속도를 올려서
옳지 않은 방향으로 회전할 수 없도록 해야하는 경우도 있다.
나에겐 그게 지금인 것 같다. 학습은 while문처럼 😇