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

Lv. 2 다리를 지나는 트럭 - 성공

방법이 떠오르지 않아서 다리와 트럭 객체를 만들어서 해결해보려했다.

하지만 ConcurrentModificationException 에러가 발생하였다. Map.remove()과정에서 발생하였을 것이다.

1. map의 Key로 활용한 트럭객체의 값이 변경되는 mutable한 객체이기때문에 문제가 발생하는 것 같다.

-> 아무 객체나 Map의 Key값으로 쓰면 안 되겠다. 값이 변하는 객체X

2. 두번째 이유는 반복문이 도는 도중에 컬렉션값을 변경하였기때문에 발생하는 것 같다.

 

https://imasoftwareengineer.tistory.com/85

자바 Collection Iterator - ConcurrentModificationException

내풀이(1)

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

//트럭이 다리를 건너는데 걸리는 시간을 알아내야함.
//1초에 1length만큼 가는건가?


class Solution {
    int N = 0;
    int arrivingTime = 0;
        
    
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;

        //트럭 번호 1~N번까지
       
        N = truck_weights.length;
        arrivingTime = bridge_length+1;
        
        Bridge bridge = new Bridge(bridge_length, weight, truck_weights);
        
        //트럭이 모두 지나갈 때 까지
        bridge.timeUp();
        while(bridge.truckMap.size() > 0){
            bridge.timeUp();
        }
        
        answer = bridge.nowCount;
        
        return answer;
    }
    //다리 객체
    class Bridge{
    int length;
    int maxWeight;
    int nowWeight;//지금 다리 무게
    //출발 타자 트럭 번호
    int truckNumber = 0;
    int nowCount = 0;
    int[] inputTruck;
    Map <Truck, Integer> truckMap = new HashMap<Truck, Integer>();
    
    public Bridge(int length, int weight, int[] input){
        this.length = length;
        this.maxWeight = weight;
        this.nowWeight = 0;
        this.inputTruck = input;
    }
    //트럭 도착.
    public void truckDrop(Truck truck){
        if(truckMap.isEmpty()) return;
        truckMap.remove(truck);
        nowWeight = nowWeight - truck.weight;
    }
    //트럭 다리 출발.
    public boolean truckStart(Truck truck){
        //하중이 괜찮다면 트럭 출발.
        if(nowWeight + truck.weight <= maxWeight){
            truckMap.put(truck, 1);
            nowWeight = nowWeight + truck.weight;
            return true;
        }else{
            //아니라면 대기
            return false;
        }
    }
    public void timeUp(){
        
        //모든 트럭 운전. => 주행시간 증가.
        for(Truck tr : truckMap.keySet()){
            tr.driving();
            //다리에 올라간시간 +1 -> 하차.
            if(tr.driveTime >= arrivingTime) {
                truckDrop(tr);
            }
        }
        boolean isStart = false;
        if(truckNumber < inputTruck.length) {
            isStart = truckStart(new Truck(inputTruck[truckNumber]));
        }
         
        if(isStart){
            truckNumber++;
        }
        nowCount++;
        
    }
    
        
    
    
}

    class Truck{
        int weight;
        int driveTime;
    
    public Truck(int weight){
        this.weight = weight;
        driveTime = 0;
    }
    public void driving(){
        driveTime = driveTime+1;
    }
    
}



}

고친풀이(2) :

아래와 같이 트럭을 드롭시키면서 초당 나가는 트럭은 한대이므로 Map이 변경되어도 바로 반복문이 끝나므로 위 에러는 발생하지 않게됨.

사실 좋은 방법은 아니라고 생각하지만 개인적으로 의미가 있는 풀이라고 생각함.

이문제 구현 방법은 실제로 코딩테스트에서 빠른방법이 떠오르지 않을 때 최후의 보루로 사용해볼만하다는 것을 알려줌.

조금 구현할 게 많아보이지만 열심히 객체 하나하나 구현하면 문제를 풀 수있다는 자신감을 심어주는 문제.

빠른 방법은 아래 코드를 참고... 역시 훨씬 빠른 방법이 있었습니다

https://minhamina.tistory.com/241

[프로그래머스 - Java] 다리를 지나는 트럭

 

 

 

 

 

Lv. 2 카펫 - 성공

 

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        
        int y = yellow;
        boolean ending = false;
        for(int i = 1; i <= y ; i++){
            
            if(y%i == 0){
                int a = i;
                int b = y/i;
                if((a*2) + (b*2) +4 == brown ){
                   
                    answer[0] =  Math.max(a+2, b+2);;
                    answer[1] =  Math.min(a+2, b+2);;
                    return answer;
                }
            }
            
        }
        return answer;
    }
}

 

 

내풀이(1) : 정확도 81%

class Solution {
    StringBuilder sb = new StringBuilder();
    
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        ArrayList<Long> arr = new ArrayList<Long>();
        for(int i = 0 ; i < answer.length; i++){
            answer[i] = findFx(numbers[i]);
        }
        
        
        
        return answer;
    }
    
    public char[] toBinary(long a){
        long num = a;
        ArrayList<Long> list = new ArrayList<Long>();
        while(num > 0){
            list.add(num % 2);
            num = num/2;
        }
        for(int i = list.size()-1; i>=0 ; i--){
            sb.append(list.get(i));
        }
        String str = sb.toString();
        
        char[] result = str.toCharArray();
        sb.setLength(0); //초기화 꼭 해주기 (실수 주의)
        return result;
    }
    
    public long findFx(long x){
        char[] nowNumber = toBinary(x);
        long y = x;
    
        int dif = 0;
        while(true){
            dif = 0;
            y++;
            char[] newNumber = toBinary(y);
            int nowLength = nowNumber.length; //3
            int newLength = newNumber.length; //4
            int distance = newLength - nowLength;
            dif = distance;
            
            for(int i = nowNumber.length-1; i >=0; i--){
                if(nowNumber[i] != newNumber[i+distance]){
                    dif++;
                }
            }
            
            if(dif <=2){
                return y;
            }else{
                dif = 0;
            }
        }
    }
    
    
}

 

차이가 넘어가면 스킵하도록 코드 추가. 유의미한 변화는 없는 것 같다...

 

고치기전

고친후

 

참고한 풀이

// 프로그래머스 2개 이하로 다른 비트 문제
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] % 2 == 0) {
                answer[i] = numbers[i] + 1;

            } else {
                StringBuilder temp = new StringBuilder();
                String binaryString = Long.toBinaryString(numbers[i]);
                if (!binaryString.contains("0")) {
                    // 맨 앞을 10으로
                    temp.append("10");

                    // 나머지 자리수를 모두 1로
                    temp.append(binaryString.substring(1).replace("0", "1"));

                } else {
                    int lastIndex = binaryString.lastIndexOf("0");
                    int firstOneIndex = binaryString.indexOf("1", lastIndex);
                    // 마지막 0을 1로 수정
                    temp.append(binaryString, 0, lastIndex).append("1");

                    // 마지막 0 다음 1을 0으로 수정
                    temp.append("0");

                    // 그 다음 비트열
                    temp.append(binaryString.substring(firstOneIndex + 1));
                }
                answer[i] = Long.parseLong(temp.toString(), 2);
            }
        }
        return answer;
    }
}

https://wellbell.tistory.com/202

프로그래머스 - 2개 이하로 다른 비트 문제 (자바)

 

Lv. 2 삼각 달팽이 - 실패

풀이(1) : 정확도 33%

안쪽삼각형을 채우는 것부터 갑자기 달팽이 채우기를 적용 안 하는 실수.

//1행 1열
//2행 2열
//3행 3열 ...
class Solution {
    
    public ArrayList<Integer>[] pyramid;
    public int[] solution(int n) {
        
        
        int nowNum = 0;
        pyramid = new ArrayList[n];
        for(int i = 0; i < n ; i++){
            nowNum++;
            pyramid[i] = new ArrayList<Integer>();
            pyramid[i].add(i+1); // 1,2,3,4...추가. 삼각형 왼쪽채우기.
            
        }
        System.out.println(nowNum);
        //삼각형 아랫부분 채우기
        for(int i = 1 ; i <n ; i++){
            nowNum++;
            pyramid[n-1].add(nowNum);
           
        }
        System.out.println(nowNum);
        //삼각형 오른쪽 채우기
        for(int i = n-2; i > 0 ; i--){
            nowNum++;
            pyramid[i].add(nowNum);
            
        }
        System.out.println(nowNum);
        //삼각형 안쪽 채우기(세번째 라인가운데 부터)
        for(int i = 2; i < n-1 ; i++){
            for(int j = 1 ; j <= i-1; j++){
                nowNum++;
                pyramid[i].add(j,nowNum);
                
            }
        }
        System.out.println(nowNum);
        
        int[] answer = new int[nowNum];
        ArrayList<Integer> arr = new ArrayList<Integer>();
        
        for(int i = 0; i < n ; i++){
            for(int j = 0; j <pyramid[i].size(); j++ ){
                arr.add(pyramid[i].get(j));
            }
        }
        
        for(int i = 0; i< arr.size(); i++){
            answer[i] = arr.get(i);
        }
        
        return answer;
    }
}

참고한 풀이

 

// 프로그래머스 삼각 달팽이 문제
class Solution {
    public int[] solution(int n) {
        int max = n * (n + 1) / 2;
        int[][] matrix = new int[n][n];
        int[] answer = new int[max];

        // 시작 지점 초기화
        int x = 0, y = 0;
        int value = 1;
        matrix[0][0] = 1;

        while (value < max) {
            // 왼쪽 - 위에서 아래로
            while (x + 1 < n && matrix[x + 1][y] == 0) {
                matrix[++x][y] = ++value;
            }

            // 아래 - 왼쪽에서 오른쪽으로
            while (y + 1 < n && matrix[x][y + 1] == 0) {
                matrix[x][++y] = ++value;
            }

            // 오른쪽 아래에서 대각선 위로
            while (y - 1 > 0 && x - 1 > 0 && matrix[x - 1][y - 1] == 0) {
                matrix[--x][--y] = ++value;
            }
        }
        int idx = 0;
        for(int i = 0; i < matrix.length; i++) {
            for (int j = 0; j <= i; j++) {
                answer[idx] = matrix[i][j];
                idx++;
            }
        }
        return answer;
    }
}

https://minhamina.tistory.com/58

[프로그래머스 - Java] 삼각 달팽이(월간 코드 챌린지 시즌1)

https://wellbell.tistory.com/201

프로그래머스 - 삼각 달팽이 문제 (자바)

 

Lv. 2 영어 끝말잇기 - 성공

복습할 내용 : CharAt() (x) -> charAt() (O)

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        
        Map<String, Integer> map = new HashMap<String, Integer>();
        char pre = ' ';
        char now = ' ';
        int problemIndex = 0;
        
        
        for(int i = 0 ; i < words.length; i++){
            String str = words[i];
            //중복 체크
            if(map.containsKey(str)){
                problemIndex = i;
                break;
            }else{
                 map.put(str, 1);
            }
            now = str.charAt(0);
            
            //앞 뒤 말이 이어지는지 체크
            if(i > 0 && now != pre){
                problemIndex = i;
                break;
            }else{
                pre = str.charAt(str.length()-1);
            }
        }
        if(problemIndex == 0 ){
            answer[0] = 0;
            answer[1] = 0;
            return answer;
        }
        int person = problemIndex % n +1;
        int numbering = problemIndex/n +1;

        answer[0] = person;
        answer[1] = numbering;

        return answer;
    }
}