[Java] 프로그래머스로 다시 공부하는 자바일기 (프로그래머스 레벨2)

 

---

# 문자열 압축

 * test input case 가 최소일 때와 최대일 때를 항상 고려하자!

  - 작성한 코드가 최소일 경우에 동일하게 돌아가는 것인가를 항상 체크하자!

  - 작성한 코드가 최대일 경우에 메모리 문제를 일으키지 않는지 항상 생각하자!

 * 코딩테스트는 결과물을 만드는 것이 아니다. 리턴값만 맞으면 된다.

   - 불필요한 값을 저장하지말자! 모든 것을 로그로 남기는 게 목적이 아니다!

   - 임시저장을 위한 용도라면, List 객체보단 Stack 객체를 사용하자.

 * 프로그래머스에서 제공하는 스켈톤코드의 answer 를 항상 다시 초기화하자!

   - 뼈대코드를 건들지 말라는 법은 없다. 

 

 1. Long to Int 

  - int num = Long.valueOf(Long_Value).intValue();

 

import java.util.*;

class Solution {
        public static long cut(String str, int base){
        long val =0;
        String result = "";
        List<String> list = new ArrayList<>();
//        int str_size = str.length;

        for(int i=0; i<str.length(); i+=base){
            String temp ="";
//            for(int j=0; j<base; j++){
//                if(i+j>=str.length) break;
//                temp+=str[i+j];
//            }
            if(i+base > str.length()){
                temp = str.substring(i,str.length());
            }else{
                temp = str.substring(i,i+base);
            }

            if(list.size() == 0){
                list.add(temp); continue;
            }
            String voca = list.get(list.size()-1);
            if(voca.length()>base){
                int cnt = Integer.parseInt(voca.substring(0,voca.length()-base));
                String originVoca = voca.substring(voca.length()-base,voca.length());

                if(originVoca.equals(temp)){
                    cnt++;
                    list.set(list.size()-1,cnt+originVoca);
                    continue;
                }else{
                    list.add(temp);
                    //memory control
                    list.remove(voca);
                    val+=voca.length();
                }
            }else{
                if(voca.equals(temp)){
                    list.set(list.size()-1,2+temp);
                    continue;
                }else{
                    list.add(temp);
                    //memory control
                    list.remove(voca);
                    val+=voca.length();
                }
            }


        }//end for

//        for(String word : list){
//            val+= word.length();
//            result += word;
//        }

        val+=list.get(0).length();
        return val;
    }

    public static int solution(String s) {
        int answer = 0;
        // fucking 1 char...
        if(s.length() == 1) return 1;
        // # memory... cut input String[] to String
//        String[] str = s.split("");
        // List<Integer> score = new ArrayList<>();
        long bestScore = 100_000_000;
        for(int i=1; i<=s.length()/2;i++){
            long newScore = cut(s,i);
            if(bestScore> newScore){
                bestScore=newScore;
            }
            // score.add(cut(str,i));
        }

        // Collections.sort(score);
        // answer = score.get(0);

        answer= Long.valueOf(bestScore).intValue();

        return answer;
    }
}

---

# 더 맵게

 1. PriorityQueue<>()

   - MinHeap : PriorityQueue<>();

   - MaxHeap : PriorityQueue<>(Collections.reverseOrder());

   - add(), peak(), poll(), contains(), remove()

import java.util.*;
class Solution {
    public static int cook(PriorityQueue<Integer> dishes, int K){
        int cnt = 0;
        int firstDish = dishes.peek();
        while(firstDish <= K){
            if(dishes.size()==1) return -1;
            
            int newDish = dishes.poll()+(dishes.poll()*2);
            cnt++;
            dishes.add(newDish);
            
            firstDish = dishes.peek();
        }
       	return cnt;
    }
    
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int dish : scoville) minHeap.add(dish);
        
        answer = cook(minHeap, K);
        
        return answer;
    }
}

 

---

# 기능개발

 1. Double to int (내림)

   - (int) 로 형변환

   - Double_number.intValue();

   - Double.valueOf(Double_number).intvalue();

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int cnt=0;
        List<Integer> ANSWER = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        
        for(int i=0; i<speeds.length; i++){
            int leftDays = (int)Math.ceil((double)(100-progresses[i]) / speeds[i]) ;
            queue.add(leftDays);
        }
        
        cnt=1;
        int sth = queue.poll();
        while(!queue.isEmpty()){
            if(sth >= queue.peek()){
                queue.poll(); cnt++;
            }else{
                ANSWER.add(cnt);
                sth= queue.poll();
                cnt=1;
            }
        }
        ANSWER.add(cnt);
        
        cnt=0;
        int[] answer = new int[ANSWER.size()]; 
        for(Integer ans : ANSWER ){
            answer[cnt++]=ans;
        }
        return answer;
    }
}

---

# 멀쩡한 사각형

 * int 형 간의 덧셈 또는 곱셈결과는 long이 나올 수 있다.

 1. 사각형기준 잘린 삼각형의 갯수

   - 가로+세로-(가로세로의 최대공약수)

   - 삼각형하나에서만 사용가능한 정사각형의 갯수는 2로 나누어주어야한다. 

 

import java.util.*;
class Solution {
    public static int gcd(int a, int b){
        int remain = a%b; // a should be larger
        if(remain == 0) return b;
        return gcd(b, remain);
    }
    
    public long solution(int w, int h) {
        long answer = (long)w*(long)h;
        long cutted = (long)w+h-gcd(Math.max(w,h),Math.min(w,h));
        answer= (answer - cutted);
        
        return answer;
    }
}

---

# 단체 사진찍기

 1. DFS (순열 nPn)

 2. 프로그래머스 채점기준 (전역변수 사용 주의점)

  * 예제 테스트케이스는 각 케이스마다 프로그램을 재부팅하여 실행하지만, 실제 테스트케이스는 재부팅하지않고 solution 함수를 계속 재사용 할 수도 있다. (매우 중요)

   => 이럴때 전역변수를 선언과 동시에 초기화하고 solution에서 초기화없이 사용할 때 오답이 리턴된다.

        (이거 찾느라... 코드도 더러워지고.. 마음도 더러워지고... 시간도 찢어지고... 너덜너덜....) 

 

import java.util.*;

class Solution {
    public static int cnt=0; // 문제의 답을 여기서 초기화하고 solution 에서 다시 초기화하지않을시 오답
    public static boolean[] used;
    public static int friends[];
    public static String[] metaData;
    public static String[] allTheFrineds = "ACFJMNRT".split("");
    public static Map<String,Integer> map = new HashMap<>(); // map 또한 solution에서 매번 새로 초기화 해줘야한다.
    public static int[] position = new int[8];

	// 성능개선을 꽤한다면, dfs의 for문을 check 안으로 집어넣는게 매번 지역변수를 할당하는거보다 빠를 것이다.
    public static boolean check(int n){
        String[] data = metaData[n].split("");
        int neededDistance = Integer.parseInt(data[4]);
        int distance = Math.abs(position[map.get(data[0])]-position[map.get(data[2])])-1;
        String op = data[3];
        
        if(op.equals("=")){
            if(neededDistance != distance) return false;

        }else if(op.equals(">")){
            if(neededDistance >= distance) return false;
        }else{ // <
            if(neededDistance <= distance) return false;
        }

        return true;
    }

    public static void dfs(int thisSpace, int totalSpace, int n){
        if(thisSpace == totalSpace){
            for(int k=0; k<n; k++){
                if(!check(k)){
                    return;
                }
            }
            cnt++;
        }
        for(int i=0; i<totalSpace; i++){
            if(!used[i]){// i번 친구 사용했니?
                used[i]=true;
                friends[thisSpace]=i; // 'i' friends will be used from(0 to 7) within fixed space
                position[i]= thisSpace;
                dfs(thisSpace+1,totalSpace,n);// thisSpace is heading from 0 to 7
                used[i]=false;
            }
        }
    }

    public static int solution(int n, String[] data){
        int numOfFriends = 8;
        used= new boolean[numOfFriends];
        friends = new int[numOfFriends];
        cnt=0; // 초기화 안하면 이전의 solution으로 인한 cnt 값이 남아있다.
        map=new HashMap<>(); // 이거 초기화 안하면 solution 실행시마다 map 이 늘어난다. 
        for(int i=0; i<numOfFriends; i++) map.put(allTheFrineds[i],i);


        //no matter with shallowCopy here
        metaData=data;

        dfs(0,numOfFriends,n);


        return cnt;
    }
}

---

# 소수 찾기

 1. DFS (순열의 합 n,m 이 0~n,m까지)

 2. Arrays.toString(String[] arr) 

   - 디버그 스타일 ( [ "elem1", "elem2" , ... "elemN" ] )

 3. string = String.join("", String[] arr)   - Java 8  이상

   - arr의 각 elem 을 구분점없이 다 붙여줌

 4. StringBuilder

   - for문으로 builder.append(String s) 후, builder.toString()

import java.util.*;
class Solution {
    static String[] nums;
    static boolean[] visited;
    static String[] selectedNum;
    static int answer;
    static Set<Integer> set ;
    public static boolean isPrime(int n){
        if(n==0||n==1) return false;
        for(int i=2; i<n;i++){
            if(n%i==0) return false;
        }

        return true;
    }
    public static void check(int len){
        for(boolean c : visited){
            if(c==true){
                String str = String.join("", selectedNum);
                if(str=="") return;
                int givenNum = Integer.parseInt(str);
                if(isPrime(givenNum)){
                    set.add(givenNum);
                }
            }
        }

    }
    static int test=0;

    public static void howMany(int vertex, int len){
        test++;
        check(len);

        for(int i=0; i<len; i++){
            if(!visited[i]){
                visited[i]=true; //i is used?
                selectedNum[vertex]=nums[i]; // num i selected in space vertex;
                howMany(vertex+1,len);
                visited[i]=false;
                selectedNum[vertex]="";
            }
        }
    }


    public static int solution(String input) {
        answer = 0;
        nums = input.split("");
        int len = nums.length;
        visited= new boolean[len];
        selectedNum = new String[len];
        for(int i=0; i<len; i++){
            selectedNum[i]="";
        }
        set = new HashSet<>();
        
        howMany(0,len);

        answer= set.size();
        return answer;
    }
}

---

# 카펫

 1. 소인수분해 (Factorization)

 2. 조합 (Combination) 

   - Set 에 그냥 모든 조합 경우의 수를 중복되지않게 때려넣었는데, 사실상 절반만 필요해서 이 부분을 개선하면 성능이 개선될 것이다.

 3. Set 자료구조는 순서도 없고, get 메서드도 없다.

 4. 삼항연산자 쓸 시간에 max, min 이 있다는 것을 기억하자.

import java.util.*;
class Solution {
    
    static boolean[] visited;
    static int cnt;
    
    static List<Integer> list;
    static Set<Integer> set;
    
    public static List<Integer> Factorization(int num){
        List<Integer> list = new ArrayList<>();
        for(int i=2;i<=num;i++){
            while(num%i==0){
                num/=i;
                list.add(i);
            }
        }
        return list;
    }
    
    public static void add(int size){
        int num=1;
        for(int i=0;i<size;i++){
            if(visited[i] == true){
                num*=list.get(i);
            }
        }
        set.add(num);
    }
    
    public static void comb(int start, int r, int size){
        if(r==0){
            add(size);
            return;
        }else{
            for(int i=start; i<size; i++){
                visited[i]=true;
                comb(i+1,r-1,size);
                visited[i]=false;
            }
        }
    }
    
    public static boolean isCarpet(int w, int h, int brown, int yellow){

        int expected_brown = (2*w)+(2*h)-4;
        if(brown == expected_brown) return true;

        return false;
    }
    
    public static int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int wh = brown + yellow;
        list = Factorization(wh);
        visited = new boolean[list.size()];
        nums = new int[list.size()];
        set= new HashSet<>();
        for(int r=1; r<list.size();r++){
            comb(0,r,list.size());
        }
        System.out.println("# Set : "+ set);

        set.forEach((item)-> {
            int w = (wh/item) > item ? wh/item : item;
            int h = Math.min(wh/item, item);
            if(isCarpet(w,h,brown,yellow)){
                answer[0] =w;
                answer[1]= h;
            }
        });

        return answer;
    }
}