[Algorithm] 6월 18일 알고리즘 연습(프로그래머스 LEVEL2) - 에이젠

 

 

Lv. 2 올바른 괄호 - 성공

//스택 이용
class Solution {
    boolean solution(String s) {
        boolean answer = true;

        char[] arr = s.toCharArray(); // [ (,),(,)]
        
        Stack<Character> stack = new Stack<Character>();
        for(char ch : arr){
            if(ch == ')' && !stack.isEmpty() && stack.peek() == '('){
                stack.pop();
                continue;
            }
            stack.push(ch);
        }
        
        if(stack.isEmpty()){
            answer = true;
        }else{
            answer = false;
        }
        return answer;
    }
}

 

 

Lv. 2 다음 큰 숫자 - 실패

내풀이 (1) : 정확도 65%, 효율성 테스트에서 걸림.

2진법 -> 10진법 전환방법 : Integer.parseInt("1010",2); 사용, 그밖의 방법은...?

import java.io.*;
import java.util.*;

class Solution {
    
    StringBuilder sb = new StringBuilder();
    public int solution(int n) {
        int answer = 0;
        
        String inputBinary = Integer.toBinaryString(n);
        //뒤에서 연속되는 1이 제일 먼저 끝나는 부분 찾기.
        char pre = '0'; 
        int headerIndex = 0;
        int movingNum = 0;
        //헤더 찾기
        for(int i = inputBinary.length() - 1; i >=0 ; i--){
            char ch = inputBinary.charAt(i);
            if(ch == '0' && pre == '1'){
                headerIndex = i+1;
                break;
            }else if(i == 0){
                headerIndex = 0; //맨 앞인경우
                break;
            }else if(ch == '1' && pre == '1'){
                movingNum++;
            }
            pre = ch;
        }
        //header가 맨 앞일때
        String ss = "";
        if(headerIndex == 0){
            ss = "10";
            ss = ss + inputBinary.substring(1);
        }else{
            //header가 중간에 있을때 
            ss = inputBinary.substring(0,headerIndex-1);
            ss = ss + "10";// 헤더 1 이동.
            sb.append(inputBinary.substring(headerIndex+1));
            ss = ss + sb.reverse().toString(); 
        }
        
        answer = Integer.parseInt(ss,2);
        
        return answer;
    }
    
    public String toBinary(int num){
        String s = "";
        while(num > 0){
            int rest = num % 2;
            s = s + rest;
            num = num/2;
        }
        String result = "";
        for(int i = s.length()-1; i >= 0 ; i-- ){
            result = result + s.charAt(i);
        }
        return result;
    }
    
   
}

 

참고한 풀이

class Solution {
    public int solution(int n) {
        
        int answer = 0;
        // 1. n을 2진수 변환.
        String str = Integer.toBinaryString(n);
        // 2. n의 1인 비트의 수를 저장하는 변수.
        int cnt =0;
        // 3. 1인 비트의 수를 카운팅.
        for(int i = 0;i<str.length();i++){
            if(str.charAt(i) == '1') cnt++;
        }
        // 4. n+1부터 반복.
        for(int i =n+1;i<1000000;i++){
            // 5. 위 과정을 반복.
            String temp = Integer.toBinaryString(i);
            int temp_cnt = 0;
            for(int j =0;j<temp.length();j++){
                if(temp.charAt(j) == '1') temp_cnt++;
            }
            // 6. 1인 비트의 수가 일치하면 해당 수를 담아 반복문 종료.
            if(temp_cnt == cnt) {
                answer = i;
                break;
            }
        }
        
        return answer;
    }
}

 

https://fbtmdwhd33.tistory.com/240

[프로그래머스,Level 2] 다음 큰 숫자 (JAVA 구현)

 

 

Lv. 2 땅따먹기 - 실패

참고한 풀이 

https://ilmiodiario.tistory.com/88

[프로그래머스] level2. 땅따먹기 (자바 JAVA)

Lv. 2 멀리 뛰기 - 성공

내풀이(1) : 정확도 37.5% (시간초과)

-> 다시 계산하지 않도록 배열에 정보를 저장하면서 할까?

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int n) {
        long answer = 0;
        answer = rec_func(n) % 1234567;
        return answer;
    }
    
    public int rec_func(int k){
        if(k == 1) return 1;
        else if(k == 2) return 2;
        return rec_func(k-2) + rec_func(k-1);
    }
    
}

내풀이(2) : 정확도 31%, 시간초과가 아님... 어떤 문제일까?

-> 각각의 값을 1234567로 나누어주지 않고 마지막에 나눈 것이 원인.

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int n) {
        long answer = 0;
        //answer = rec_func(n) % 1234567;
        long[] arr = new long[n+1]; //[1~n]
        arr[1] = 1;
        arr[2] = 2;
        if(n == 1){
            return 1;
        }else if(n ==2){
            return 2;
        }
        for(int i = 3; i <= n ; i++){
            arr[i] = arr[i-2] + arr[i-1];
        }
        answer = arr[n] % 1234567;
        return answer;
    }
    
}

내풀이(3) : 정확도93.8%, 테스트케이스 1번이 통과가 안 됨(런타임 에러)

-> 메모리 때문에 막힌다는 말을 들음.

import java.io.*;
import java.util.*;

class Solution {
    public long solution(int n) {
        
        long answer = 0;
        long[] arr = new long[n+1]; //[1~n]
        
        arr[1] = 1;
        arr[2] = 2;
        
        if(n == 1){
            return 1;
        }else if(n ==2){
            return 2;
        }
        
        for(int i = 3; i <= n ; i++){
            arr[i] = (arr[i-2] + arr[i-1]) % 1234567;
        }
        
        answer = arr[n];
        return answer;
    }
    
}

내풀이(4)

class Solution {
  public long solution(int n) {
      long answer = 1;
      long a=1,b=2;
      if(n==1) return 1;
      if(n==2) return 2;
      // long dp[] = new long[n+1];
      // dp[1]=1;
      // dp[2]=2;

      for(int i=3; i<=n; i++){
          // dp[i] = (dp[i-2] + dp[i-1])%1234567;
          answer=(a+b)%1234567;
          a=b;
          b=answer;
      }
      // answer=dp[n]%1234567;

      return answer;
  }
}

 

Lv. 2 숫자의 표현 - 성공

내 풀이 : 투포인터 사용

//투포인터를 이용
//left, right
//n이상이 될때까지 right++.
//같다면 count ++
//크다면 left++
class Solution {
    public int solution(int n) {
        int answer = 0;
        int count = 0;
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 1;
        }
        int left= 1 ;
        int right = 2 ;
        int number = 0;
        number =  left + right;
        while(left < n){
            
            if(number < n){
                right++;
                number = number + right;
            }else if(number > n){
                number = number - left;
                left++;
            }else if(number == n){
                count++;
                right++;
                number = number + right;
            }
        }
        if(left == n){
            count++;
        }
        answer = count;
        return answer;
    }
}

 

더 좋아보이는 풀이

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution {       public int solution(int n) {           int answer = 0;                      for(int i=1; i<=n; i++) {               int sum = 0;               for(int j=i; j<=n; j++) {                   sum += j;                                      if(sum==n) {                       answer++;                       break;                   } else if(sum>n) {                       break;                   }               }           }                 return answer;       }     }

https://ju-nam2.tistory.com/50

[Java][프로그래머스][Level 2] 숫자의 표현

Lv. 2 줄 서는 방법 - 실패

내풀이(1) : 테스트케이스는 다 통과했지만 효율성 테스트를 통과하지 못함.

import java.util.*;
class Solution {
    int N ;
    int count;
    long K;
    int[] arr = {};
    boolean[] selected = {};
    int[] answer = {};
    public int[] solution(int n, long k) {
        //int[] answer = new int[n];
        
        N = n;
        K = k;
        arr = new int[n];
        selected = new boolean[n+1];
        answer = new int[N];
        answer = rec_func(1);
        
        return answer;
    }
    //f번째 사람 정하기
    public int[] rec_func(int f){
        
        if(f == N + 1 ){ //모든 사람을 정했다면
            count++;
            if(count == K){
                //k번째 방법이라면
                for(int i = 0; i < N; i++){
                    answer[i] = arr[i];
                }
            }  
        }
        else{
            for(int cand = 1; cand <= N; cand++){
                if(selected[cand] == false){
                    selected[cand] = true;
                    arr[f-1] = cand;
                    rec_func(f+1);
                }else{
                    continue;
                }
                selected[cand] = false;
                arr[f-1] = 0;
            }
        }
        return answer;
    }
}

 

Lv. 2 최댓값과 최솟값 - 성공

import java.util.*;

class Solution {
    public String solution(String s) {
        String answer = "";
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        String[] arr = s.split(" ");
        
        for(String ss : arr){
            int num = Integer.parseInt(ss);
            min = Math.min(num, min);
            max = Math.max(num, max);    
        }
        answer = min + " " + max;
        
        return answer;
    }
}

 

Lv. 2 최솟값 만들기 - 성공

내 풀이

import java.io.*;
import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;

        //각각 배열 정렬
        int[] a = A;
        Arrays.sort(a);
        int[] b = B;
         Arrays.sort(b);
        for(int i = 0 ; i < A.length; i++){
            answer = answer + a[i] * b[A.length -1 - i];
        }

        return answer;
    }
}