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

 

 

Lv. 2 기능개발 - 성공

처음에 한 실수 -> 첫번째 기능보다 배포까지 남은 기간이 짧기만하면 모두 배포될 기능 개수에 추가시켜버리는 실수.

level2부터는 이런 실수를 자주하게 될 것으로 예상. -> 중간에 기능을 이해하면서 코드를 침착하게 고쳐나가는 습관들이기 연습.

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

class Solution {
    //개발은 순서에 상관없음.
    //배포는 앞에꺼 먼저 배포
    //progresses => 작업진도 [93, 30, 55]
    //speeds     => 개발 속도 [1, 30, 5]
    //배포마다 몇개의 기능이 배포되는지 return
    
    //남은 일수 : int
    //앞에꺼가 배포될때까지 기다림.
    //첫번째 작업의 남은 일수 & 남은 일수보다 짧게 남은 작업들 -> 함께 배포.
    public int[] solution(int[] progresses, int[] speeds) {
       
        //각각 배포까지 남은 날짜.
        int[] restDay = new int[progresses.length];
        ArrayList<Integer> arr = new ArrayList<Integer>();
        int deploy = 1 ;
        //각 기능마다 남은 날짜를 계산. O(n)
        for(int i = 0 ; i < progresses.length; i++){
            if((100 - progresses[i]) % speeds[i] > 0 ){
                restDay[i] = ((100 - progresses[i]) / speeds[i]) + 1; 
            }else{
                restDay[i] = (100 - progresses[i]) / speeds[i];     
            }
        }
        
        //첫번째 기능이 배포할때까지 걸리는시간 (7일)
        //나머지 기능 중에 첫 기능 배포되는 시간보다 짧은 기능들 찾기 (restDay <7)
        //첫번째 배포때 위 기능들 개수포함 개수 출력. & 배포된 기능들 리스트 제거(진도 100%)
        //배포 후 걸린시간 빼줌(진도 올려줌++) or (남은 시간 업데이트).
        //배포 안 된 기능 중 맨 처음 기능이 배포까지 걸리는 시간.
        for(int i = 0 ; i < progresses.length; i++){
            if(restDay[i] == 0) continue; //남은 날짜 0인 경우 패스 
            for(int j = i+1 ; j < progresses.length ; j++){
                if(restDay[i] >= restDay[j] &&
                   restDay[j] != 0 && deploy ==j-i) { //배포 기간이 짧다면
                    
                    deploy++; //출력 개수++
                  
                    // 배포될 추후 기능들 남은기간 0 업데이트  
                    restDay[j] = 0;
                }
            }
            //출력
            
            arr.add(deploy);
            //출력 개수 초기화
            deploy = 1 ;
           //배포될 첫 기능 남은 기간 0 업데이트
            restDay[i] = 0;
        }
        
         int[] answer = new int[arr.size()];
     
        for(int i = 0 ; i < arr.size(); i++){
            answer[i] = arr.get(i);
        }
        
        
        
        
        return answer;
    }
}

 

 

Lv. 2 더 맵게 - 성공 

복습할 내용 :

 

Array 데이터 추가.

add(int index, Object) : ArrayList의 index에 데이터를 추가

Array 데이터 변경.

set(int index, Object)

 

Array 데이터 삭제.

remove(int index) : ArrayList의 index에 해당하는 값을 삭제

우선순위 큐

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

// 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueueLowest.poll();

// 첫번째 값 제거 비어있다면 예외 발생
priorityQueueLowest.remove(); 

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 null을 반환
priorityQueueLowest.peek();

// 첫번째 값을 반환만 하고 제거 하지는 않는다.
// 큐가 비어있다면 예외 발생
priorityQueueLowest.element();

// 초기화
priorityQueueLowest.clear();

size() 메서드를 사용하면 Priority Queue의 개수를 구할 수 있습니다

부스트캠프 코테에서는 구현문제가 나올 확률이 높은 것 같고... 

라이브러리 사용이 감점이 될 수 있다는 후기를 본적이 있습니다.

우선순위큐를 직접 구현해서 사용하는 순간이 오지않을까... 하는 생각이 드네요. 다음에 한번 정리해봐야겠습니다.

 

내풀이 과정(1)

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

//모든 스코빌 지수를 k이상으로 만들어야함.
//스코빌지수보다 낮은 가장 낮은 2개 A,B 합치기(A < B, A가 제일 낮음)
//  => 정렬을 이용하면 A,B쉽게 찾을 수 있음.
//모든 음식이 k이상될때까지 반복해서 섞음. 횟수++;
//결과 : 전체 섞은 횟수를 출력.

//음식이 섞여 항목이 줄어듬. 스코빌 배열 -> ArrayList사용.
//모든 음식의 스코빌지수가 1이면?? 가능한가.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        //각 음식의 스코빌 지수를 Array에 담음.
        //단 스코빌 지수 미만인 음식만 추가.
        for(int sc : scoville){
            if(sc < k){
                list.add(sc);
            }
        }
        //오름차 정렬(리스트) [A,B, ...]
        Collections.sort(list);
        //합치기
        int mix = list.get(0) + list.get(1)*2;
        list.set(0, mix); //값 변경
        list.remove(1); //둘중 하나 삭제
        //다시 배열할때 시간복잡도 증가... 우선순위 큐를 써야하려나?
        
        
        return answer;
    }
}

문득 음식을 합칠때마다  다시 정렬한다는 과정이 너무 비효율적이라는 생각이 들었습니다.

우선순위큐를 사용하는 것이 좋겠다고 판단하여 다시 고쳤습니다.

 

풀이과정(2)

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

//모든 스코빌 지수를 k이상으로 만들어야함.
//스코빌지수보다 낮은 가장 낮은 2개 A,B 합치기(A < B, A가 제일 낮음)
//  => 정렬을 이용하면 A,B쉽게 찾을 수 있음.
//모든 음식이 k이상될때까지 반복해서 섞음. 횟수++;
//결과 : 전체 섞은 횟수를 출력.

//음식이 섞여 항목이 줄어듬. 스코빌 배열 -> ArrayList사용.
//모든 음식의 스코빌지수가 1이면?? 가능한가.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int count = 0;
        //ArrayList<Integer> list = new ArrayList<Integer>();
        PriorityQueue<Integer> list = new PriorityQueue<Integer>();
        //각 음식의 스코빌 지수를 Array에 담음.
        //단 스코빌 지수 미만인 음식만 추가.
        for(int sc : scoville){
            if(sc < K){
                list.add(sc);
            }
        }
        //오름차 정렬(리스트) [A,B, ...]
        // Collections.sort(list);
        //합치기
        while(list.size() >1){
            int A = list.poll();
            int B = list.poll();
            int mix = A + B*2;
            count++;
            if( mix < K){
                list.add(mix);
            }
            if(list.size() == 1 && list.peek() < K ){
                //실패 한 경우 
                return -1;
            }
        }
        if(list.size() ==1 && list.peek() > K ){
                //실패 한 경우 
                count++;
        }

        answer = count;
        
        return answer;
    }
}

정확도 81%가 나오는 상황에서 문제점을 찾아보았습니다.

 

내 풀이 (3) - 합쳐지자마자 우선순위큐에서 제외시켜버린 것이 원인.

k보다 크더라도 다른 작은 수와 합치기 가능한 경우의 수를 간과했었음.

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

//모든 스코빌 지수를 k이상으로 만들어야함.
//스코빌지수보다 낮은 가장 낮은 2개 A,B 합치기(A < B, A가 제일 낮음)
//  => 정렬을 이용하면 A,B쉽게 찾을 수 있음.
//모든 음식이 k이상될때까지 반복해서 섞음. 횟수++;
//결과 : 전체 섞은 횟수를 출력.

//음식이 섞여 항목이 줄어듬. 스코빌 배열 -> ArrayList사용.
//모든 음식의 스코빌지수가 1이면?? 가능한가.

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        int count = 0;
        //ArrayList<Integer> list = new ArrayList<Integer>();
        PriorityQueue<Integer> list = new PriorityQueue<Integer>();
        //각 음식의 스코빌 지수를 Array에 담음.
        //단 스코빌 지수 미만인 음식만 추가.
        for(int sc : scoville){
            // if(sc < K){
                list.add(sc);
            // }
        }
        //오름차 정렬(리스트) [A,B, ...]
        // Collections.sort(list);
        //합치기
        while(list.size() > 1 && list.peek() < K){
            int A = list.poll();
            int B = list.poll();
            int mix = A + B*2;
            count++;
            //모든 음식의 스코빌 지수가 k이 될 때까지
            // if( mix < K){
                list.add(mix);
            // }
            if(list.size() == 1 && list.peek() < K ){
                //실패 한 경우 
                return -1;
            }
        }
//         if(list.size() == 1 && list.peek() > K ){
                
//                 count++;
//         }
        //처음부터 전부 다 k이상일때 = 문제 없음.
        //h가 비어있지 않은 경우를 예외로 안 넣으면 최소값 빠지자마자 남은 값이 K를 넘어서


       
        answer = count;
        
        return answer;
    }
}

 

 

Lv. 2 타겟 넘버 - 성공

 

처음 읽었을때 (+,-)중에 골라서 각각 숫자 사이에 배열하는 경우의수를 나열하면 되므로

2개 부호중 중복이 가능하도록 배열 개수만큼 선택하여 배열하는 완전탐색을 이용하면 될 것 같다고 생각. 

카테고리에 BFS/DFS로 되어있는 것 같아서 조금 의아했음.

 

생각했던대로 완전탐색을 이용해 풀 수 있었음.

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

//1+1+1+1+1+ = 타겟넘버
//numbers배열의 숫자들을 적절히 이용해 타겟넘버를 만드는 경우의 수
// 출력 : 타겟넘버 만드는 경우의수 return

class Solution {
    int[] arr = {};
    int targetNumber = 0;
    
    //N개중에 M개를 고르기
    int N = 2; // [+, -] [1,0]으로 매핑
    int[] sign = {1,0};
    int M = 0; 
    
    int count = 0;
    int nowPoint = 0;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        arr = numbers;
        targetNumber = target;
        M = numbers.length;
        rec_func(1);
        answer = count;
        
        return answer;
    }
    
    //k번째 부호를 결정.
    public void rec_func(int k){
        int recoverUnit = 0;
        //M개를 모두 골랐다면
        if(k == M+1){
            if(nowPoint == targetNumber) count++;
        }else{
            //k번째 부호 선택해서 연산
            for(int temp = 0 ; temp < 2; temp++){
                if(temp == 0){
                    nowPoint = nowPoint+arr[k-1];
                    recoverUnit = +arr[k-1];
                }
                if(temp == 1){ 
                    nowPoint = nowPoint-arr[k-1];
                    recoverUnit = -arr[k-1];
                }
                //부호 골랐으면 다음 부호 고르기.
                rec_func(k+1);
                //끝난 후 초기화.
                nowPoint = nowPoint - recoverUnit;
            }
            
        }
    }
    
    
}

 

 

Lv. 2 짝지어 제거하기 - 실패

복습할 내용 : Stack 사용법

 

내 풀이(1) - 메모리 초과하여 다시 생각. 재귀 호출을 하지 않고 포인터를 초기화하는 방향으로 고쳐보는 방안을 물색.

import java.util.*;
import java.io.*;
//출력   : 짝지어 제거하기 과정 성공 여부 1 or 0
//소문자 문자열
//같은 알파벳이 2개 붙어있는 거 Search
//2개를 제거
//앞뒤로 문자열을 이어붙임(제거하면서 생긴 파편을 붙인다는 말)
//순회하면서 이전 index의 문자와 같은 경우 (연속, 같은 문자 두개) 제거.
//ArrayList사용

// ArrayList에서 제거하게되면 뒷부분의 String의 인덱스가 모두 바뀌게 됨.(반복문의 어려움.)
// 문자열을 제거하면서 생기는 두개의 파편을 substring()을 이용.
//charAt()
class Solution
{
    
    String front = "";
    String back = "";
    boolean isReal = false; //중복이 있는가?
    int ans = -1;
    
    public int solution(String s)
    {
        int answer = -1;
        
        rec_func(s);
        

        answer = ans;
        return answer;
    }
    
    public String rec_func(String s){
        char prev = ' ';
        for(int i = 0 ; i < s.length(); i++){
            char sc = s.charAt(i);
            if(sc == prev){
                if(i == s.length()-1){// 맨 끝 인덱스인경우.
                    //연속된 문자열의 경우 앞과 뒤 문자열 분해
                front = s.substring(0,i-1); //맨끝의 두 문자 빼고
                back = "";
            
                rec_func(front);
                }else{
                    //연속된 문자열의 경우 앞과 뒤 문자열 분해
                front = s.substring(0,i-1); //i-1, i번째의 문자빼고 뽑기
                back = s.substring(i+1);
                }
                String resultS = front+back;
                if(resultS.length() == 0){
                    ans = 1;
                    return "";
                }
                rec_func(resultS);
                 ;
            }
            prev = s.charAt(i);
        }
        //반복이 끝나버릴때까지 중복을 못찾는 경우
        ans = 0;
        return s;
       
    }
}

 

내풀이(2) - 모든 테스트 케이스는 통과했지만 효율성 테스트를 통과하지못함.

class Solution
{
    int index = 0 ;
    String front = "";
    String back = "";
    boolean isReal = false; //중복이 있는가?
    int ans = -1;
    
    public int solution(String s)
    {
        int answer = -1;
        
        char prev = ' ';
        while(index < s.length() && ans == -1){
            char sc = s.charAt(index);
            if(sc == prev){
                if(index == s.length()-1){// 맨 끝 인덱스인경우.
                    //연속된 문자열의 경우 앞과 뒤 문자열 분해
                    front = s.substring(0,index-1); //맨끝의 두 문자 빼고
                    back = "";
                }else{
                    //연속된 문자열의 경우 앞과 뒤 문자열 분해
                    front = s.substring(0,index-1); //i-1, i번째의 문자빼고 뽑기
                    back = s.substring(index+1);
                }
                s = front+back;
                
                if(s.length() == 0){
                    ans = 1;
                    break; //끝내
                }
                index = 0;
                prev = ' ';
                continue; // 다시 처음부터
                
            }
            prev = s.charAt(index);
            index++;
        }
        if(index == s.length()){
            ans = 0;
        }
    

        answer = ans;
        return answer;
    }
}

 

참고한 풀이 : 이문제는 스택으로 간단히 구현할 수 있었습니다... 허탈하지만 많이 배워갑니다.

import java.util.Stack;
 
public class Solution {
    public static int solution(String s) {
        Stack<character> stack = new Stack<>();
         
        for(char c : s.toCharArray()) 
          if(!stack.isEmpty() && stack.peek() == c) stack.pop();
          else stack.push(c);
         
        return stack.isEmpty() ? 1 : 0;
    }
}

https://lkhlkh23.tistory.com/148

[프로그래머스, 자바] 짝지어 제거하기 - 스택