Programo90 코딩 기록저장소

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

나의 풀이

 처음 접근을 고민해볼 때 큐에서 가장 먼저 나올 값(배열에서 최대값)과 내 목표값의 거리 관계를 고민해 보았는데, 우선순위가 1~9이고 대기목록도 100개까지 이기 때문에 사실상 경우의 수가 너무 많았다. 결국 큐에서 가장 앞에 있는 값과 큐 안에서 최대값을 검색해 최대값일 때만 출력하기로 하고 코드를 작성 아래 코드로 테스트는 통과했다.

 또 이번에 풀이는 Java의 객체를 이용해보고 싶었어서 좀 억지로? Doc이라는 class를 만들고 객체로 값을 비교하였다. 결과적으론 코드가 너무 길어지고 정작 로직은 단순하면서 효율은 떨어지는 코드가 되고 말았다..

 다른 접근법으로는 목표가 위치한 지점을 계속 갱신하면서 큐 젤 앞에 값은 최대값일 때만 꺼내기로 하고 코드를 작성.

 이 풀이는 다른 사람들의 풀이를 보고 참고하였는데, 이 접근법으로 코드 구상을 고민하면서 비슷하게는 작성 하였다가 완성은 다른 사람의 코드에서 힌트를 얻고 완성해서 공부가 되긴 했지만 아쉬운 풀이.

수정 코드2

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        Queue<Integer> que = new LinkedList<Integer>();
        for(int i=0; i< priorities.length; i++) {
            que.offer(priorities[i]);
        }
        
        Arrays.sort(priorities);
        int leng = priorities.length - 1;
        int answer = 0;
        
        while(!que.isEmpty()) {
            Integer temp = que.poll();
            if(temp == priorities[leng-answer]) {
                answer++;
                location--;
                if(location<0) {
                    break;
                }
            } else {
                que.offer(temp);
                location--;
                if(location<0) {
                    location = que.size()-1;
                }
                
            }
        }
               
        return answer;
    }
    
    
}

 코드1

import java.util.*;

class Solution {
    
    class Doc implements Comparable<Doc> {
        String docName;
        int prio;
        
        public Doc(String docName, int prio) {
            super();
            this.docName = docName;
            this.prio = prio;
        }
        
        @Override
        public int compareTo(Doc target) {
            if(this.prio>target.prio) {
                return -1;
            } else if(this.prio<target.prio) {
                return 1;
            } else {
                return 0;
            }
        }
    }
    
    
    public int solution(int[] priorities, int location) {
        int answer = 0;
        int val = priorities[location];
        
        LinkedList<Doc> que = new LinkedList<Doc>();
        for(int i = 0; i<priorities.length; i++) {
            if(i==location) {
                que.offer(new Doc("target",priorities[i]));
            } else {
                que.offer(new Doc("other",priorities[i]));
            }
        }
        
        Doc temp;
        int max;
        int tempVal;
        while(true) {
            temp = que.poll();
            ListIterator<Doc> it = que.listIterator();
            max = 0;
            
            while(it.hasNext()) {
                tempVal = it.next().prio;
                if(max<tempVal) {
                    max = tempVal;
                }
            }
            
            if(temp.prio<max) {
                que.offer(temp);
            } else {
                answer++;
                if("target".equals(temp.docName)) {
                    break;
                }
            }
        }
        
        
        return answer;
    }
    
    
}

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다.
※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다.

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간다리를 지난 트럭다리를 건너는 트럭대기 트럭

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 조건

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

나의 풀이

 일단 큐에 트럭무게를 더하고, 큐를 한칸씩 진행시킨다(poll, offer를 한다) 라는 접근으로 시작. 문제는 다리가 견딜 수 있는 무게를 넘느냐 마느냐 였는데 매번 다리 위에 무게를 재고, 다음 트럭을 올려도 될지 말지를 결정하였다.

결과적으론 코드1(아래쪽 코드)로 문제풀이는 성공 했지만 리뷰하며 생각해보니 효율이 별로다 싶었다. 특히 Iterator를 이용해 매번 다리 위 무게를 측정하였는데 사실 이게 필요 없었다. totalWeight에 현재 다리 위 무게를 저장해 놓고 매번 poll하는 무게는 빼고, 다음 트럭을 올려도 될지만 체크하면 되었다. 리뷰 후 개선한 코드가 코드2(위쪽코드) 이다.

코드2 (수정 코드)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> que = new LinkedList<Integer>();
        for(int i=0; i<bridge_length; i++) {
            que.offer(0);
        }
        
        int count = 0;
        int totalWeight = 0;
        int i=0;
        
        while(!que.isEmpty()) {
            totalWeight -= que.poll();
            if(i<truck_weights.length) {
                if(totalWeight+truck_weights[i]<=weight) {
                    que.offer(truck_weights[i]);
                    totalWeight += truck_weights[i];
                    i++;
                } else {
                    que.offer(0);
                }
            }
            count++;
        }

        return count;
    }
}

코드1 (기존 코드)

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<Integer> que = new ArrayDeque<Integer>();
        for(int i=0; i<bridge_length; i++) {
            que.offer(0);
        }
        
        int count = 0;
        int totalWeight;
        for(int i=0; i<truck_weights.length; i++) {
            while(true) {
                totalWeight = 0;
                Iterator<Integer> it = que.iterator();
                while(it.hasNext()) {
                    totalWeight += it.next();
                }
                
                if((totalWeight+truck_weights[i]-que.peek())<=weight) {
                    count++;
                    que.poll();
                    que.offer(truck_weights[i]);
                    break;
                } else {
                    count++;
                    que.poll();
                    que.offer(0);
                }
            }
        }
        
        for(int i=0; i<que.size(); i++) {
            count++;
        }

        return count;
    }
}

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

나의 풀이

 먼저 생성자와 분해합의 관계성을 고민해보았는데, 생성자에서 분해합으로의 규칙성은 보이는데 분해합에서 생성자로의 규칙성은 잘 보이지가 않는다... 결과적으로 반복문을 사용해 주어진 값부터 시작해 1까지 분해합을 구해보면서 주어진 값과 구한 분해합이 일치할때 현재 찻수를 저장하는 방식으로 해결. 끝까지 분해합이 구해지지 않으면 0을 리턴하게 처리하였다.

 다른 사람들의 풀이법을 여러개 찾아보았는데도 깔끔한 규칙성이 보이는 풀이가 없어서 아쉬운 문제ㅠ

풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int num = Integer.parseInt(br.readLine());
        int result = 0;
        int temp, tempResult;
        for(int i=num; i>0; i--) {
            temp = tempResult = i;
            while(temp!=0) {
                tempResult += temp%10;
                temp /= 10;
            }
            if(tempResult==num) {
                result = i;
            }
        }
        
        bw.write(result+"\n");
        
        bw.flush();
    }
}

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

나의풀이

카드 중 3장의 카드 합이 M을 넘지 않으면서 가장 가까운값 이므로, 먼저 max를 0으로 초기화 시키고, 카드 3장을 더할때마다 그 합이 이전 max값보다 크면서도 M을 넘지 않는지 검사했다. 만약 M과 일치하는 값이 나오면 반복문을 빠져나오고, 끝까지 실행해도 일치하는 값이 없으면 M보다 작으면서도 가장 큰 값인 max를 리턴했다. 의외로 간단했던 문제인데 다른 사람 풀이를 봐도 접근법은 다 같아보였다.

풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int result = drawThreeCard(arr, N, M);
        bw.write(result+"\n");
        bw.flush();
    }
    
    static int drawThreeCard(int[] arr, int N, int M) {
        int result = 0;
        int max = 0;
        for(int i=0; i<N-2; i++) {
            for(int j=i+1; j<N-1; j++) {
                for(int k=j+1; k<N; k++) {
                    result = arr[i] + arr[j] + arr[k];
                    if(result==M) {
                        max = result;
                        return max;
                    }
                    else if(result>max && result<=M) {
                        max = result;
                    }
                }
            }
        }
        return max;
    }
}

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

나의 풀이

 먼저 기본 방침으로 progresses 배열에 speeds 배열 한 번씩 더하길 반복한다. 그러다 더하기를 반복하면서 매번 값이 100이 넘지 않는 progresses의 최소 인덱스를 체크한다. 만약 최소 인덱스가 변할경우 배포가 된것으로 간주하고, (변경된 최소인덱스 - 이전 최소인덱스) 만큼을 배포된 기능의 수로 저장했다.  만약 progresses 배열에 모든 값들이 100을 넘을 경우 함수를 종료했다.

 기본적인 기능은 위와 같이 구성하면서 어떻게 하면 반복을 최소해 효율을 놓을 수 있을지 고민했다.

 progresses 배열에서 100이 넘지 않는 최소 인덱스가 변경될 경우, progresses 배열에 speeds 값을 더하는 작업의 반복문과, 최소 100이하 인덱스를 찾는 반복문의 시작 위치를 변경했다. 결과적으로 반복횟수를 최소화 한 것.

 변경 가능한 부분으로는 각 배포마다 배포되는 기능의 수를 temp라는 임시 배열에 저장해놓고, 배포한 횟수를 count 변수에 저장해놓았다가 마지막에 temp 배열을 잘라서 리턴하였는데, 이를 ArrayList에 저장해놓았다가 list에 저장된 값들을 새롭게 배열을 만들어서 리턴해줄수도 있다. 결과적으로는 배열을 새롭게 만들고, 값을 카피해 넣어준다는 점은 비슷할 듯. 대신 temp배열의 불필요한 부분만큼 메모리는 절약될 것.

 아쉬운 점으로는 남은 진척도를 기준으로 생각해보지 못한것... (시간 = 거리/속도) 의 개념을 (작업일수 = 남은진척도/진행속도) 와 같이 접근하는게 더 간단했을 것이라 생각이 들고, 이런 방식으로 접근하면 최소 반복문을 1회만으로도 해결이 가능했을 것이다.

작성 코드

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int num = 0;
        int count = 0;
        int length = progresses.length;
        int[] temp = new int[length];
        
        while(true) {
            for(int i=num; i<length; i++) {
                progresses[i] += speeds[i];
            }
            
            for(int j=num; j<length; j++) {
                if(progresses[j]<100) {
                    if(j!=num){
                        temp[count++] = j-num;
                        num = j;
                    }
                    break;
                }
                if(j==length-1) {
                    temp[count++] = j-num+1;
                    num = length;
                }
            }
            
            if(num==length) {
                break;
            }
        }        
        
        return Arrays.copyOf(temp,count);
    }
}

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

나의 풀이

 처음 문제를 풀 때는 prices 배열에서 값을 꺼낼때 마다 이전 값들과 비교해보고 (현재값>=이전값) && (이전값이 더 적은 값이 나온적이 없는경우) 조건일 때 answer[이전값 Index] 값을 1씩 증가시키면 되겠다 생각하고 문제풀이를 시작.

 하지만 코드를 작성하고 보니, prices 배열에서 값을 하나씩 꺼낼때마다 이전 모든 값들을 스캔해야 했다. 결과적으론 실행 자체는 되었지만 효용성 테스트를 전부 통과 실패...

 해결점은 미래의 모든 값들이 prices 배열에 저장되어 있으니, 현재 값을 이전 값들과 비교해보는 것이 아니라 미래의 모든 값과 비교해 더 작은 값이 나오는 순간까지의 시간을 answer[현재값 Index]에 저장하는 점이었다. 그리고 만약 끝까지 비교해도 더 작은 값이 나오지 않는다면, 현재지점에서 배열이 끝나는 지점까지의 시간을 저장한다.

 아래는 수정 후 테스트 통과 코드

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i =0; i<prices.length; i++) {
            for(int j=i+1; j<prices.length; j++) {
                if(prices[j]<prices[i]) {
                    answer[i] = j-i;
                    break;
                }
            }
            if(answer[i]==0) {
                answer[i] = prices.length -i -1;
        }
          }
        return answer;
    }
}

Java에서 배열 생성시 초기화 값

참조변수 배열 - Null 로 초기화

byte / short / int / long  배열  -  0 으로 초기화

float / double 배열  -  0.0 으로 초기화

boolean 배열    -    false로 초기화

char 배열    -    null ('\u0000) 으로 초기화