일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 17087
- 23971
- 알고리즘
- 2866
- 9081
- 1342
- solved.ac
- 사용자정의필터
- 25379
- sloved.ac
- 20006
- 24511
- 자바
- 6730
- 프로그래머스
- Algorithm
- PYTHON
- programmers
- Django
- 파이썬
- 11688
- SWEA
- pccp
- sovled.ac
- java
- 백준
- 15965
- 라이브러리
- 장고
- PS
Archives
- Today
- Total
코깽이의 코딩일기
[ 프로그래머스 / JAVA / Level 2 ] 다음 큰 숫자 본문
반응형
제출한 코드
1차 제출 코드 - 정확성 70점 , 효율성 0점 ( 시간 초과 0 )
import java.util.*;
class Solution {
public int solution(int n) {
int answer = 0;
// 이진법 String으로 변환된 정수 n
String binaryN = Integer.toBinaryString(n);
int startIdx = -1;
int finIdx = -1;
// 1이 연속되는 index 찾기
for(int i = binaryN.length()-1 ; i >= 0; i --){
if(finIdx == -1 && binaryN.charAt(i) == '1'){
finIdx = 0;
startIdx = i;
}
if(finIdx == 0 && binaryN.charAt(i) == '0'){
finIdx = i;
}
}
// 다음 큰 숫자를 2진법 기준 자리 마다 int[]에 저장
int[] arr;
// 연속 되는 경우가 0번 인덱스까지인 경우
if(finIdx == 0){
arr = new int[binaryN.length()+1];
arr[0] = 1;
arr[1] = 0;
for(int i = arr.length-1; i > arr.length-1 - (startIdx-finIdx); i--){
arr[i] = 1;
}
}
// 아닌 경우
else{
arr = new int[binaryN.length()];
for(int i = 0 ; i < finIdx ; i++){
arr[i] = binaryN.charAt(i) - '0';
}
arr[finIdx] = 1;
for(int i = arr.length-1; i > arr.length-1 - (startIdx-finIdx) +1 ; i--){
arr[i] = 1;
}
}
// 정답 구하기
for(int i = 0 ; i < arr.length;i++){
if(arr[i] == 1){
answer += Math.pow(2, arr.length - (i+1));
}
}
return answer;
}
}
2차 제출 코드 - 정확성 70점 , 효율성 30점
import java.util.*;
class Solution {
public int solution(int n) {
int answer = 0;
String binaryN = Integer.toBinaryString(n);
int startIdx = -1;
int finIdx = -1;
for(int i = binaryN.length()-1 ; i >= 0; i --){
if(finIdx == -1 && binaryN.charAt(i) == '1'){
finIdx = 0;
startIdx = i;
}
if(finIdx == 0 && binaryN.charAt(i) == '0'){
finIdx = i;
}
}
if(finIdx == 0){
int size = binaryN.length();
answer += Math.pow(2, size);
for(int i = size; i > size - (startIdx-finIdx); i--){
answer += Math.pow(2, (size-i));
}
}else{
int size = binaryN.length()-1;
for(int i = 0 ; i < finIdx ; i++){
if(binaryN.charAt(i) == '1'){
answer += Math.pow(2, size-i);
}
}
answer += Math.pow(2, size-finIdx);
for(int i = size; i > size - (startIdx-finIdx) +1 ; i--){
answer += Math.pow(2, size-i);
}
}
return answer;
}
}
생각한 로직
1. 십진수로 입력받은 n을 이진수로 변환한다.
2. 뒤에서 부터 반복하면서 1이 제일 먼저 연속되는 구간을 찾는다.
3 - 1 0번 index까지 연속 되는 경우 전체 길이를 1 증가시킨다.
3 - 2 0번 index전에 종료되는 경우 길이는 그대로 가져간다.
4. ex ) 1111 -> 10111과 같이 연속되는 구간의 맨 처음 1을 1자리 증가시키고 나머지 연속된 1의 개수만큼 뒤에서부터 채운다.
5. Math.pow()를 이용해서 십진수 값을 계산한다.
틀렸던 이유
int [] arr에 저장하고 answer를 계산하는 작업이 불필요했다.
arr저장하는 로직에서 바로 연산을 진행하면 시간 초과를 해결할 수 있다.
반응형
'PS > 프로그래머스' 카테고리의 다른 글
[ 프로그래머스 / JAVA / Level 1 ] [PCCP 기출문제] 1번 / 붕대 감기 (0) | 2024.06.13 |
---|---|
[ 프로그래머스 / JAVA / Level 2 ] 점프와 순간 이동 (0) | 2024.06.08 |
[ 프로그래머스 / JAVA / Level 2 ] 짝지어 제거하기 (0) | 2024.05.30 |
[ 프로그래머스 / JAVA / Level 2 ] 숫자의 표현 (0) | 2024.05.29 |
[ 프로그래머스 / JAVA / Level 3 ] 가장 먼 노드 (0) | 2024.05.28 |