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

 

 

가장큰수 - 실패

내풀이(1) : 일부 테스트케이스만 통과하고 나머지는 런타임 오류. - 아마도 자료형 범위를 초과했기 때문이라 예상.

// 정수를 이어 붙여 만들 수 있는 가장 큰 수
//정수 N개 중 N개를 뽑아서 중복을 허용하지 않고 순서가 있게 배열.
class Solution {
    int N = 0;
    boolean[] used = {};
    int[] selected = {};
    int[] nums = {};
    //생성된 숫자들 배열마지막에 정렬 필요
    ArrayList<Long> list = new ArrayList<Long>();
    
    public String solution(int[] numbers) {
        String answer = "";
        used = new boolean[numbers.length + 1];
        nums = numbers;
        N = numbers.length;
        selected = new int[numbers.length + 1];
        rec_func(1);
        Collections.sort(list);
        answer = "" + list.get(list.size()-1);
        return answer;
    }
    //K번째 수를 결정.
    public void rec_func(int k){
        //다골랐을 경우
        if(k == N+1){
            String numbering = "";
            for(int a : selected){
                if(a == -1) continue;
                numbering = numbering + a;
            }
           
            list.add( Long.parseLong(numbering));
            
            
            return;
        }else{//아직 다 못고른 경우
            for(int cand = 0; cand < N ; cand++){
                if(used[cand] == false){
                    used[cand] = true;
                    selected[k] = nums[cand];
                    rec_func(k+1);
                    
                }else{
                    continue;
                }
                selected[k] = -1;
                used[cand] = false;
            }
            
        }
    }
}

 

참고한 풀이

import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
        //문자열 리턴을 해줄 스트링배열 생성
        String[] str = new String[numbers.length];
        
        //int배열 String배열로 변환
        for(int i = 0; i < numbers.length; i++){
            str[i] = String.valueOf(numbers[i]);
        }     
        
        //내림차순 정렬
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b+a).compareTo(a+b);
                //오름차순 정렬 (o1+o2).compareTo(o1+o2);
            }
        });
        
        //0값이 중복일경우 ex){0,0,0}
        //답이 000이 나오면 안되므로 첫번째값이 0이면 0을 리턴
        if (str[0].equals("0")) return "0";
        
        //0이 아니면 문자열을 더해준다.
        for(String s: str) answer += s;
 
        return answer;
    }
}

https://ivory-room.tistory.com/43

[프로그래머스 Lv.2] 가장 큰 수 java

 

Lv. 2 소수 찾기 - 성공

복습할내용 : 소수 관련 문제 

https://eigen.tistory.com/30

[Algorithm] 5월29일 알고리즘 연습

 

완전탐색을 통해 소수들을 찾음.

소수 예외처리에서 실수한 것을 찾느라 오래걸림.

N개중 M개를 선택. 중복x, 순서O 방법 

class Solution {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    String[] selected = {};
    boolean[] used = {};
    int N = 0;
    String[] nums = {};
    
    
    public int solution(String numbers) {
        int answer = 0;
        N = numbers.length();
        String[] temp = numbers.split("");
        nums = new String[temp.length+1]; //1~N까지의 숫자들, 0제외
        used = new boolean[temp.length+1];//1~N번째까지의 사용여부 , 0제외
        selected = new String[N+1]; //고른 숫자들 1~N번째까지
        
        for(int i = 0; i < numbers.length(); i++){
            nums[i+1] = temp[i];
        }
        for(int i = 1; i <= numbers.length(); i++){
            rec_func(1, i);
        }
        
        answer = map.size();
        
        return answer;
    }
    //numbering개 중에 k번째 수를 결정. 
    public void rec_func(int k, int numbering){
        //numbering번째까지 모두 정해졌다면 
        if(k == numbering+1 ){
            //소수 판별해야함.
            String st = "";
            for(int i = 1; i < k; i++){
                st = st + selected[i];
            }
            int result = Integer.parseInt(st);
            boolean isSosu = true;
            int divider = 2;
            if(result == 1){
                isSosu = false;
                return;
            } 
            if(result == 0){
                    isSosu = false;
                    return;
                } 
            
            while(divider < result){
                if(result % divider == 0){
                    isSosu = false;
                    if(result == 2) isSosu = true;
                    divider++;
                    break;
                }
               divider++;
            }
            if(isSosu){
                 map.put(result, 1);
                return;
            }
            
            //아직 k번째 수를 정해야한다면
        }else{
            //중복 불가. 순서는 구분하는 경우를 혼동
            //지금 구현한 방법은 중복불가. 순서 구분X
            for(int cand = 1; cand <= N ; cand++){
                // selected[k] = nums[cand];
                // rec_func(k+1, numbering);
                if(used[cand] == false){
                    used[cand] = true; //이제 선택 불가.
                    selected[k] = nums[cand];
                    rec_func(k + 1, numbering); //k번째 선택 후 다음 수 선택.
                }else{
                    continue;
                }
                used[cand] = false;
                
            }
            
        }
    }
}

Lv. 2 조이스틱 - 실패

 

내풀이(1) : BBBBBAAAAAAAAAD와 같은 뒤로 돌아가서 푸는 것이 더 빠른 경우.

정답률 44%

class Solution {
    int N = 0;
    int index = 0;
    public int solution(String name) {
        int answer = 0;
        N = name.length();
        
        char[] arr = name.toCharArray();
        
        int pointer = 0;
        int nextIndex = 0;
        while(nextIndex < name.length()){
            if(arr[nextIndex] ==  'A' ){
                nextIndex++;
                continue;
            }
            //마지막 인덱스 도달 전엔 계속
            if(nextIndex == 0){
                answer = answer + upDown(arr[nextIndex]);
                nextIndex++;
        
                
            }else{
                //이동 
                answer = answer + rightLeft(pointer, nextIndex);
                pointer++;
                answer = answer + upDown(arr[nextIndex]);
                nextIndex++;
            }
        }
        
        return answer;
    }
    
    public int upDown(char ch){
        if(ch == 'A') return 0;
        int A = ch - 'A' ;
        int Z = 'Z' - ch +1 ;
        int moving = Math.min(A,Z);
        return moving;
    }
    public int rightLeft(int pointer,int next){
        int right = next - pointer;
        int left = N - next;
        int moving = Math.min(right, left);
        
        return moving;
    }
  
}

이동하고나서 포인터를 그 인덱스로 이동하는 것이아닌 1만 증가시키는 치명적인 실수...

위 코드는 BBBAAAAAAAADDDDD 인경우 뒤로 돌아서 맨 뒤의 D부터 처리하는 것이 아닌 처음 나오는 D부터 처리하기때문에 비효율 발생.

 

조이스틱이 좌우로 움직이는 거리는 결국 최소 문자열개수 +a

a는 왼쪽으로 가는경우.

 

참고한 풀이

public int solution(String name) {
  int answer = 0;
  int len = name.length();

  // 제일 짧은 좌, 우 이동은 그냥 맨 오른쪽으로 이동할 때
  int min = len - 1;

  for (int i = 0; i < len; i++) {
    // 조이스틱 상, 하 이동
    char c = name.charAt(i);
    int mov = (c - 'A' < 'Z' - c + 1) ? (c - 'A') : ('Z' - c + 1);
    answer += mov;

    // 조이스틱 좌, 우 이동
    int nextIndex = i + 1;
    // 다음 단어가 A이고, 단어가 끝나기 전까지 nextIndex 증가
    while (nextIndex < len && name.charAt(nextIndex) == 'A')
      nextIndex++;

    min = Math.min(min, (i * 2) + len - nextIndex);
  }

  answer += min;

  return answer;
}

 

 

https://hellodavid.tistory.com/4

[프로그래머스] 탐욕법 - 조이스틱 (Java)