프린터

문제설명

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

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

문제에 나온 예와 같습니다.

예제 #2

6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

문제 풀이

class Document{

    public int index;
    public int priority;

    public Document(int index, int priority) {
        this.index = index;
        this.priority = priority;
    }
}


public class Printer {
    public int solution(int[] priorities, int location) {

        int answer = 0;
        LinkedList<Document> queue = new LinkedList<>();
        // 결과 값을 가지고 있는 Queue 타입의 객체 
        LinkedList<Document> result = new LinkedList<>();

        for (int i = 0; i < priorities.length; i++) {
            queue.add(new Document(i, priorities[i]));
        }

        while(!queue.isEmpty()) {
            Document firstDoc = queue.poll();
            if (isMaximum(firstDoc, queue)) {
                result.add(firstDoc);
            } else {
                queue.add(firstDoc);
            }
        }

        // 정렬된 우선순위 값을 기준으로
        int order = 0;

        for (Document tempDoc : result){
            int value = tempDoc.index;
            if(location == value){
                answer = order + 1;
            }
            order++;
        }
        return answer;
    }

    public boolean isMaximum(Document firstDoc, LinkedList<Document> queue){

        if(queue.size() == 0){
            return  true;
        }

        for (Document temp : queue){
            if(firstDoc.priority < temp.priority){
               return false;
            }
        }
        return true;
    }
}

처음 이 문제를 보았을때 생각보다 쉬운거 같았는데... 막상 코드를 짜보니 자꾸 테스트케이스 실패가 났다... 이 알고리즘은 큐나 스택을 써야될거 같다고 위에 대놓고 명시를 해서 큐를 썼고 그 중에서 가장 많이 쓰인다는 LinkedList 큐를 사용하여 풀기로 하였다. 풀이 과정에서 우선 순위 값이 높은 순서대로 결과 Queue에 넣을 수는 있었지만 location에 해당하는 값이 우선 순위 기준으로 몇번째 인덱스에 있는지 찾는데 상당히 애를 먹었다. 그러다가.. 현재 내가 푸는 언어가 자바라는 것을 뒤늦게 깨닫고... 객체를 이용해서 인덱스와 우선 순위 값을 같이 관리하도록 Document 객체를 큐로 관리하도록 코드를 작성하였다. 이렇게 구현하니 직관적이면서 인덱스를 관리하는게 확실히 편해졌습니다. 프로그래머스에서 빡고수분들이 작성한 것을 보고는.. 도저희 저렇게 코드를 작성할 자신이 없었기 때문에 오래 걸리고 지저분하더라도 전 이게 더 직관적이라고 생각합니다.

산술식에서 올바른 괄호인지 판단하기

문제

계산기 프로그램에서 소괄호(), 중괄호{}, 대괄호[] 세 종류의 괄호를 사용하며, 괄호의 포함관계는 소괄호 < 중괄호 < 대괄호 순서입니다. 이 순서는 반드시 지켜져야 합니다. 예: [ { ( ) } ]
입력된 산술식에 괄호가 옳게 구성되었는지 확인하는 solution 함수를 완성해 주세요.

• 입력되는 산술식은 검증하지 않습니다.
• if 구문 등 비교문은 10개 이하만 사용하시오.

( switch case문에서 case갯수, 3항 연산자 등 if로 계산할 수 있는 비교 구문)

• 추가 제약조건은 아래와 같습니다.
  • 여는(왼쪽) 괄호는 닫는(오른쪽) 괄호 앞에 와야 하며, 항상 쌍을 이뤄야 한다.
  • 포함 관계에 따라 다수의 다른 괄호를 포함 할 수 있다. 예. [ { ( ) ( ) } { } ]
  • 동일한 레벨의 괄호는 스스로를 포함할 수 없다. 예. { { } } 불가

입출력 예

import java.util.Stack;

public class StackExample {


    private static int getBrace(char c){
        if(c == '{') {
            return c - 40;
        } else {
            return c;
        }
    }


    public boolean solution(String input) {

        boolean result = true;

        Stack<Character> str = new Stack<>();

        int first = 0;
        int remain = 0;

        for (char c : input.toCharArray()) {

            if ((int) c > 41 && c <= 57) continue;

            // [ = 91, { = 123 , ( = 40
            if (c == '[' || c == '{' || c == '(') {
                if (str.size() == 0) {
                    first = getBrace(c);
                } else {
                  remain = getBrace(c);

                    if (first <= remain) {
                        result = false;
                        break;
                    }
                }

                first = getBrace(c);
                str.push(c);

            } else {

                if (str.size() < 1) {
                    result = false;
                    break;
                }

                if (c == ']' && str.pop() != '[') {
                    result = false;
                    break;
                }

                if (c == '}' && str.pop() != '{') {
                    result = false;
                    break;
                }

                if (c == ')' && str.pop() != '(') {
                    result = false;
                    break;
                }

            }

        }

        if (str.size() != 0) {
            result = false;
        }

        return result;
    }


    public static void main(String[] args) {

        StackExample stack = new StackExample();

        System.out.println(stack.solution("3+[(5+1)-1]"));
        System.out.println(stack.solution("3+([5+1])"));
        System.out.println(stack.solution("3+{(5+1}"));
        System.out.println(stack.solution("3+[{(5+1)-1}+3]"));
        System.out.println(stack.solution("3+[{{5+1}-1}+3]"));
    }
}

괄호의 포함관계와 동일한 괄호는 서로를 포함할 수 없는 조건을 판단하기 위해서 저는 자료구조 중에서 stack을 사용해서 풀었습니다.
해당 문자열을 각각 char 타입으로 변환 후에 산술식(0 ~ 9, +, -, *, /)은 아스키 코드 표에서 42 ~ 57에 포함되기 때문에 continue를 이용하여 걸렀습니다.
그리고 {(중괄호)의 경우에는 [(대괄호) 보다 우선순위가 낮지만 아스키 코드 테이블에서는 값이 더 크기 때문에 ((소괄호)가 아스키 코드 값으로 40이기 때문에 이 값을 기준으로
우선 순위의 값을 구해서 올바른 괄호인지 판단하도록 코드를 작성하였습니다.

예산에 맞는 물건 구매

문제설명

두 가지 물품을 구매할 수 있도록 예산을 배정받았습니다, 첫 번째 물품의 가격은 a원, 두 번째 물품의 가격은 b원 입니다. 각 물품은 여러 개 구매할 수 있으며, 구매하지 않아도 괜찮습니다.
물품을 구매하는 여러 가지 방법 중, 예산을 남기지 않고 물품을 구매하는 방법의 수를 구하려 합니다. 예를 들어 예산이 23000원이고, 첫 번째 물품의 가격 a = 3000원, 두 번째 물품의 가격 b = 5000원인 경우, 예산에 딱 맞게 물건을 구매하는 방법은 다음과 같이 두 가지 방법이 있습니다.

1. 첫 번째 물품을 1개(3000원), 두 번째 물품을 4개(20000원) 구매합니다.
2. 첫 번째 물품을 6개(18000원), 두 번째 물품을 1개(5000원) 구매합니다.
   위 두 가지 방법 외에 예산을 남기지 않고 물품을 구매할 수 있는 방법은 없습니다.
   첫 번째 물품의 가격 a, 두 번째 물품의 가격 b, 예산 budget이 매개변수로 주어질 때, 예산을 남기지 않고 물품을 구매하는 방법의 가짓수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• a는 1 이상 10,000 이하의 자연수입니다.
• b는 1 이상 10,000 이하의 자연수입니다.
• budget은 1 이상 1,000,000 이하의 자연수입니다.

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

public int solution(int a, int b, int budget){

  // 3000 , 5000, 23000
  int answer = 0;


  for (int i = 0; i*a < budget; i++) {
    for (int j = 0; j*b < budget; j++) {
      if((budget-(i*a+j*b))==0)
        answer++;
     }
   }

  return answer;
}

해당 문제의 출력결과는 예산(budget)이랑 구매 품목(a,b)의 개수가 정확하게 맞아 떨어지도록 구할 수 있는 경우의 수츨 출력하는게 목적입니다.
구매 물품 a,b는 budget(예산)을 넘지 못합니다. 이를 이용해서 이중 for문을 이용해서 순차적으로 경우의 수를 따져가며 값을 구하도록 코드를 작성하였습니다.

숫자 n의 각 자리수로 분열 가능한 횟수 구하기

어떤 숫자 n을 각 자리의 숫자로 나누었을 때, 나누어떨어지면 그 숫자로 분열 가능하다고 합니다.
예를 들어 2232이라는 숫자는 2와 3 두 개의 숫자로 구성되어 있습니다. 또한, 2232는 2로도 나누어떨어지고, 3으로도 나누어 떨어집니다. 따라서 분열 가능한 횟수는 2입니다.

2232의 예에서와같이 2가 여러 번 나오더라도 분열 가능한 횟수를 셀 때는 2 한 번, 3 한 번으로 세며 중복해서 나오는 숫자 2는 고려하지 않습니다.
숫자 n이 매개변수로 주어질 때, n이 분열 가능한 횟수를 return 하도록 solution 함수를 완성하세요.
[※ 숫자는 0으로 나눌 수 없음을 유의하세요.]
제한사항

• n은 1015 이하의 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

문제의 예제와 같습니다.
입출력 예 #2

1234의 경우 다음과 같습니다.

• 1234는 1로 나누어떨어짐
• 1234는 2로 나누어떨어짐
• 1234는 3으로 나누어떨어지지 않음
• 1234는 4로 나누어떨어지지 않음
  따라서 분열 가능한 횟수는 2이므로 2를 return 합니다.

import java.util.HashSet;

public class FindDivisibleNumber {

    public int solution(long n) {

        int answer = 0;
        // 각 자리수에 해당 하는 값을 중복없이 저장하기 위한 HashSet 객체 생성
        HashSet<Integer> hashSet = new HashSet<>();
        String number = String.valueOf(n);

        getDistinctNumber(n, hashSet, number);

        hashSet.forEach(s -> System.out.println(s));

        for (int val : hashSet){
            if(n % val == 0) {
                answer++;
            }
        }

        return answer;
    }

    private void getDistinctNumber(long n, HashSet<Integer> hashSet, String number) {

        for (int i = 0; i < number.length(); i++) {
            int remain = 0;

            // 각 자리수 추출
            remain = (int) n % 10;
            hashSet.add((int) remain);
            n = n / 10;
        }
    }


    public static void main(String[] args) {

        FindDivisibleNumber divideN = new FindDivisibleNumber();
        int n = 2322;

        System.out.println(divideN.solution(n));

    }
}

각각의 자리수를 중복없이 추출하기 위해 List 타입을 사용하여 contains() 메소드를 이용하여 중복이 되지 않는 각 자리수를 추출하려 했지만,
HashSet 객체를 이용하는것이 더 적절하다고 판단하여 사용하였습니다.

체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.

• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.

• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.

• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

• 예제 #1

  1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

• 예제 #2

  3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

import java.util.HashSet;

public class GymClothes {

    public int solution(int n, int[] lost, int[] reserve){

        // 현재 참석자 수
        int participant = n - lost.length;

        HashSet<Integer> hashSet = new HashSet<>();

        for (int index : reserve){
            hashSet.add(index);
        }


        for(int i =0; i< lost.length; i++){

            if(hashSet.contains(lost[i])){

                participant++;
                hashSet.remove(lost[i]);
                lost[i] = -1;
            }

        }


        for (int i = 0; i < lost.length; i++) {

            if(hashSet.contains(lost[i] - 1)){
                participant++;
                hashSet.remove(lost[i] - 1);

            }else if(hashSet.contains(lost[i] + 1)){
                participant++;
                hashSet.remove(lost[i] +1);

            }
        }

        return participant;
    }


    public static void main(String[] args) {

        GymClothes gymClothes
                = new GymClothes();


        int n = 3;
        int[] lost = {3};
        int[] reserve = {1};

        System.out.println(gymClothes.solution(n, lost, reserve));

    }
}

체육복 문제는 사실 제한사항 중에 맨 마지막에 있는 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
이 부분에 대해서 고려를 해야합니다. lost[] 배열가 reserve[] 배열에서 겹치는 번호가 존재하면 해당 번호는 lost[] 배열의 다른 번호에게 체육복을 빌려줄 수 없기 때문에 컬렉션 타입의 객체의 remove() 메소드를 활용하여 reserve[] 배열의 요소 값을 가지고 있는 HashSet 객체에서 lost[] 배열의 요소 값이 포함되어있으면 중복으로 처리하여 각각의 중복되는 요소의 값들을 제거하였습니다.

K번째수

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.

[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

import java.util.Arrays;

public class FindNumberOrderBy {


    public int[] solution(int[] array, int[][] commands) {

        int[] result = new int[commands.length];

        for (int i = 0; i < commands.length; i++) {
            // to 부터 from 전까지 문자열을 발췌
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            result[i] = temp[commands[i][2]-1];
        }
        return result;
    }

    public static void main(String[] args) {

        int[] array = {1, 5, 2, 6, 3, 7, 4};
        int[][] commands = {{2, 5, 3}, {4, 4, 1}, {1, 7, 3}};

        FindNumberOrderBy findNumberOrderBy = new FindNumberOrderBy();

        int[] result = findNumberOrderBy.solution(array, commands);

        for (int value : result)
            System.out.print(value + " ");

    }
}

단순하게 이 문제는 Arrays.copyOfRange()를 알고 있다면 훨씬 간결하게 풀수 있는 문제입니다. 처음에는 array를 문자열 타입의 배열로 solution() 메소드의 아규먼트로 넘기려다가 정수형 타입의 배열에서 특정 길이만큼 자를 수 있는 util 클래스를 찾다가 이런 유용한 메소드가 있다는 것을 알게 되었습니다.