문제분석
나에겐 어렵다.. Level3? 3.5 정도 문제 아닌가..?
문제 이해부터 조금 난해한데, 요약하자면 1을 11011 , 0을 00000으로 치환하여 n만큼 반복시킨다.
그렇게 반복시킨 문자열에서 스타트 l에서 끝지점 r까지 1의 갯수를 세주면 된다.
First Try:
처음엔 그냥 쉽네 하고 하라는데로 진행을했다.
n만큼 1과 0을 치환한뒤, 그 문자열을 가져와서 스타트 l에서 끝지점 r까지 갯수를 세준것이다.
-> 당연히 효율성에러
Level2 에서 효율성 에러를 본게 참 오랜만이다.
n이 20까지 가기때문에 5^20 까지간다. int 범위를 넘어갈정도니, 당연히 안된다.
Secont Try:
**점화식, 재귀 작성하기 **
첫번째 접근이 안된다면, 값을 추적해야한다.
작전 : 0~ 끝 지점 - 0~ 스타트지점 구하기
규칙을 살펴보면, 1 하나가 11011을 생성한다. 즉 , n이 증가할때마다, 1은 1을 4개씩 생성이된다.
EX) n이 2번 진행되면, 문자열은 5^2개, 1의 숫자는 4^2개 생성된다.
하지만 , 숫자가 0일경우는 생성이 되지않는다. 이럴경우도 빼줘야한다.
이제부터, 값을 역추절 할것이다. 예를들어, 추적할 값이 17이라고 가정하자.
추적할 값이 17이면, 17은 25(5^2)보다 작은수다. 그렇다면 5^1로 나눠줍니다.
몫은 3, 나머지는 2가 나옵니다.
앞에서 1의 숫자가 4^n개만큼 생성이 됨을 알았으니, 총 1의갯수는 3* 4^1 입니다.
하지만 몫이 3이상이면, 다시 4^1개를 빼줘야합니다. 이유는 0이 끼어있기 때문입니다.
그 후, 나머지를 다시 재귀를 해줍니다.
전체풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
import java.util.*;
class Solution {
public int solution(int n, long l, long r) {
int answer = 0;
double a=getCount(r)-getCount(l-1);
answer=(int)a;
return answer;
}
public long getCount(long num){
int[] fk = new int[]{0,1,2,2,3,4};
if(num<=5){
return fk[(int)num];
}
int level=1;
while(num>Math.pow(5,level+1)){
level++;
}
long box = num/(long)(Math.pow(5,level));
long remain = num%(long)(Math.pow(5,level));
long count=box*(long)Math.pow(4,level);
if(box>=3){
count-=Math.pow(4,level);
}
if(box==2){
return count;
}
else {
return count+getCount((long)remain);
}
}
}
|
cs |
사실 혼자 힘으로 풀진 못한 문제다.
항상 이런 새로운 점화식을 찾아내, 재귀로 구현하는부분은 조금 약한것 같다.
조금 더 길러야하는 생각이 많이 드는 문제다.
'알고리즘 > 프로그래머스 Level2' 카테고리의 다른 글
[프로그래머스,Java] Level2: 이모티콘 할인행사 (0) | 2023.01.11 |
---|---|
[프로그래머스,Java] Level2: 택배 배달과 수거하기 (0) | 2023.01.07 |
[프로그래머스, Java] Level2: 마법의 엘리베이터 (0) | 2022.12.30 |
[프로그래머스 ,Java] Level2: 테이블 해시 함수 (0) | 2022.12.22 |
[프로그래머스, Java] Level2: 디펜스 게임 (1) | 2022.12.10 |