딱봐도 복잡해보이는 문제이다.
하지만 단계를 생각해서 로직을 작성하면 어렵지 않다. 일단 이진 변환 횟수(Count)와 제거된 0의 갯수(remove)를 구해야한다.
로직의 순서는
1. 기존 문자열의 길이를 구한다.
2. 0을 제거한다 (replace)
3. 변경된 문자열의 길이를 구한다 (그러면 제거된 0의갯수를 알수있게된다)
4. 제거된 0의 갯수를 합산한다.
5. 변경된 문자열의 길이를 2진수로 변환한다.
6. 이진 변환 횟수 (Count)를 증가 시킨다.
class Solution {
public int[] solution(String s) {
int remove = 0;
int count = 0;
while(s.length()>1) {
int beforeremove = s.length();
s=s.replace("0","");
int afterremove = s.length();
remove+=beforeremove-afterremove;
s=Integer.toBinaryString(afterremove);
count++;
}
return new int[]{count,remove};
}
}와 같은 로직을 작성하면된다.
특이사항으로는 0을 ""으로 대체하면 list의 remove와 비슷하게 작동한다.
Integer.toBinaryString(afterremove)로 10진수를 2진수 문자열로 변경할 수 있다.
전에도 해결했던 피보나치 문제의 더 쉬운 버전입니다.
class Solution {
public int solution(int n) {
int answer = 0;
int f0 = 0;
int f1 = 1;
int f2 = 1;
for(int i=1; i<n; i++) {
f2 = (f0+f1)%1234567;
f0 = f1;
f1 = f2;
}
return (int)f2;
}
}간단합니다.
제일 어지러웠던 문제입니다. 어떤식으로 풀어야할지 감이안잡혔는데요
그냥 n이라는 수를 받았을때 2중포문으로 해결하되 빠르게 탈출하는식으로 횟수를 적당히 조절했습니다.
class Solution {
public int solution(int n) {
int answer = 0;
for(int i=1; i<=n; i++) {
if(isSum(n,i)) {
answer++;
}
}
return answer;
}
boolean isSum(int n,int i) {
//n이 i부터 연속된수의 합으로 가능한가를 찾는 함수
int sum=0;
for(int a=i; a<=n; a++) {
sum+=a;
//i부터 n까지 합을 구해본다.
if(n==sum) {
//만약 n==sum인경우 예 n이 6이고 i가 1일때 1,2,3 의 합으로 6을 만들수있음
//이런경우에는 true를 리턴하고 break;
return true;
}
if(sum>n) {
//만약 합이 n을넘어가면 의미가없으니 탈출
return false;
}
}
return false;
}
}n을 입력받고 n부터 i까지의 포문을 돌리되 isSum에서도 포문을 돌린다.
다만 n==sum 예) 6=1+2+3 과 같은 경우에는 빠르게 true를 반환하여 break하고
n<sum 예) 6=3+4 와 같은경우에는 답을 구할 수 없으니 빠르게 break한다.
그렇게 되면 2중포문으로 해결해도 시간복잡도가 커지지 않게된다.