프로그래머스LV2_3

다음 큰 숫자

접근 과정

1. n의 2진수 1의 개수를 카운트
2. answer를 1씩 늘려가면 2진수 1의 개수가 n과 같으면 break하고 반환

시행착오

• 시행착오 없이 해결
  

해결 코드

• 접근 과정대로 구현하여 해결
• 뭔가 비효율적인거 같아 2진법 1의 개수를 빠르게 세는 방법이 없는지 찾아보았는데 자바 함수 중에 1의 개수를 반환하는 함수가 있어서 개선해보았다.
  

    class Solution {
        public int solution(int n) {
            int answer = n + 1;
            String binary = Integer.toBinaryString(n);
            int cnt = binary.length() - binary.replace("1", "").length();
            while(true){
                String b = Integer.toBinaryString(answer);
                int c = b.length() - b.replace("1", "").length();
                if(c == cnt) break;
                answer++;
            }
            return answer;
        }
    }
    
    // 개선
    class Solution {
        public int solution(int n) {
            int targetCount = Integer.bitCount(n);
            int answer = n + 1;
            while(true) {
                if(Integer.bitCount(answer) == targetCount) {
                    break;
                }
                answer++;
            }
            return answer;
        }
    }

시간복잡도

짝지어 제거하기

접근 과정

1. 문자열 처음부터 전체를 순회하면서 이전에 넣은 문자와 현재 문자가 같은지 체크
2. 같으면 제거
3. 다르면 추가
4. 순회한 결과의 길이가 0이면 1 아니라면 0을 반환하여 해결

시행착오

• 처음에 연속하는 2개의 문자를 빈 문자로 대체하는 식으로 해결했다가 시간 초과가 나서 다른 방법을 찾았다.
  

    // 시간복잡도(O(n^2))
    class Solution {
        public int solution(String s) {
            while (true) {
                String newStr = s.replaceAll("(.)\\1", "");
                if (newStr.equals(s)) break;
                s = newStr;
            }
            return s.length() == 0 ? 1 : 0;
        }
    }

해결 코드

• 시행착오를 겪고 접근 과정대로 구현하여 해결
  

    class Solution
    {
        public int solution(String s)
        {
            StringBuilder sb = new StringBuilder();
            for(char c : s.toCharArray()){
                int len = sb.length();
                if(len > 0 && sb.charAt(len - 1) == c){
                    sb.deleteCharAt(len - 1);
                }
                else{
                    sb.append(c);
                }
            }
            return sb.length() == 0? 1 : 0;
        }
    }

시간복잡도

피보나치 수

접근 과정

1. fib(n) = fib(n - 1) + fib(n - 2)라는 정확한 수학 규칙이 있어 dp 방법을 선택
2. dp[0]과 dp[1]을 0과 1로 초기화
3. 2부터 n까지를 돌면서 dp[i]를 계산함
4. dp[n-1] + dp[n-2]가 int형을 넘을 수 있으므로 % 연산을 수행

시행착오

• 시행착오 없이 해결
  

해결 코드

• 접근 과정대로 구현하여 해결
  

    class Solution {
        public int solution(int n) {
            int MOD = 1234567;
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for(int i = 2; i <= n; i++){
                dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
            }
            return dp[n];
        }
    }

시간복잡도