문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

문제 풀이 일단 모든 숫자의 조합을 만들어야했고, 소수인지 확인하는 과정도 필요한 문제였다. 여기서 모든 숫자 조합을 만든 newNumbers메서드에서는 재귀함수를 사용하여 현재만들어진 조합과 아직 사용하지 않는 숫자, 조합을 저장할 hashSet을 사용하였다. 아직 사용하지 않은 숫자를 이용하여 반복하여 숫자조합을 만드는 메서드이고, isPrime메서드는 소수인지 판단하는 메서드로 소수를 판별하는 조건문들로 해결할 수 있었다. 또한 숫자 조합들 중에 중복이 있을 수 있어 HashSet에 저장하여 최종 소수 판별 후 소수가 맞다면 카운트를 증가시켜 소수의 갯수를 반환하도록 하였다.

코드

public int solution(String numbers) {
    // 중복 제거를 위해 hashset에 저장
    HashSet<Integer> set = new HashSet<>();
    newNumbers("", numbers, set);

    int count = 0;
    for (int n : set) {
      if (isPrime(n)) {
        count++;
      }
    }
    return count;
  }

  // 모든 숫자 조합 만들기
  private static void newNumbers(String current, String remaining, HashSet<Integer> set) {
    if (!current.isEmpty()) {
      set.add(Integer.valueOf(current));
    }
    for (int i = 0; i < remaining.length(); i++) {
      newNumbers(current + remaining.charAt(i), remaining.substring(0, i) + remaining.substring(i + 1), set);
    }
  }
  // 소수인지 확인
  private static boolean isPrime(int n) {
    if (n <= 1) {
      return false;
    }
    if (n == 2) {
      return true;
    }
    if (n % 2 == 0) {
      return false;
    }
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

문제 풀이

1. 수포자들의 방식인 배열을 정의

2. 수포자들의 답과 정답이 일치하는지 확인 작업

3. 정답 점수가 많은 수포자를 반환

4. 정답 점수 받은 사람이 여렷이면 반환하는 배열을 오름차운으로 정렬 처음에 문제를 보고 생각한 문제 풀이 순서이다. 풀이를 해본데로 문제를 풀어보았는데 정답이 일치하는 확인하는 작업에서 패턴의 길이를 넘어서는 일이 발생했어서 i % 패턴의 길이로 설정했다. 최대 점수를 찾고, 그 최대 점수를 받은 수포자를 찾아 배열로 반환하도록 하였다.

   코드

   public int[] solution(int[] answers) {
    int[] first = {1, 2, 3, 4, 5};
    int[] second = {2, 1, 2, 3, 2, 4, 2, 5};
    int[] third = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    int[] count = new int[3];
   
    for (int i = 0; i < answers.length; i++) {
      if (answers[i] == first[i % first.length]) {
        count[0]++;
      }
      if (answers[i] == second[i % second.length]) {
        count[1]++;
      }
      if (answers[i] == third[i % third.length]) {
        count[2]++;
      }
    }
    int max = Math.max(count[0], Math.max(count[1], count[2]));
   
    List<Integer> answer = new ArrayList<>();
    for (int i = 0; i < count.length; i++) {
      if (count[i] == max) {
        answer.add(i + 1);
      }
    }
    return answer.stream().mapToInt(i -> i).toArray();
   }

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로 길이를 나타냅니다.
  • h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

문제 풀이 이차원 배열에서 각각 의미하는게 다르기 때문에 두 값 중에 최대와 최소를 찾는 방식으로 문제를 풀었다.

코드

  public int solution(int[][] sizes) {
    int maxW = 0;
    int maxH = 0;

    for (int[] s : sizes) {
      int width = Math.max(s[0], s[1]);
      int height = Math.min(s[0], s[1]);

      if (width > maxW) {
        maxW = width;
      }
      if (height > maxH) {
        maxH = height;
      }
    }
    return maxW * maxH;
  }

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

문제 풀이 힙 자료구조를 사용한 문제로 PriorityQueue를 이용하여 최소 힙으로 문제를 해결하였다. 최솟값을 찾아야되는 최적의 경로를 탐색하였다. 음식을 섞어 스코빌 지수를 만드는 작업에서 일단 스코빌 지수가 가장 낮은 음식이 두개 이상은 있어야 함으로 음식이 한개 초과일 때와 힙의 최솟값이 K이상일 때까지 새로운 스코빌 지수를 계산하고, 힙에 새로운 스코빌 지수를 추가하고, 카운트를 세는 작업을 반복해주었다. 여기서 힙의 최소가 K보다 작으면 문제가 원하는 모든 음식의 스포빌 지수가 K이상인 것을 해결할 수 없음으로 -1을 반환해주는 것으로 하였다.

코드

   public int solution(int[] scoville, int K) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();

    for (int s : scoville) {
      heap.add(s);
    }

    int count = 0;
    while (heap.size() > 1 && heap.peek() < K) {
      int first = heap.poll();
      int second = heap.poll();
      int newSco = first + (second * 2);
      heap.add(newSco);
      count++;
    }
    if (heap.peek() < K) {
      return -1;
    }
    return count;
  }

문제 설명

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

제한 사항

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

문제 풀이 해당 문제를 보고 이해하는 것이 힘들어 다른 분이 해석해주신 문제를 보고 풀었다. https://school.programmers.co.kr/questions/20326?question=20326 현재 인덱스를 기준으로 현재 인덱스와 다음 인덱스 별로 확인하여 가격이 떨어지지 않았으면 그 시간이 몇초인지를 계산하는 문제로 만약 다음 인덱스가 가격이 떨어졌고, 그 다음 인덱스에서는 올랐다면 현재에서 다음까지로 가는 1초만 주가가 유지했던 것으로 인지하여 문제를 풀었다.

코드

 public int[] solution(int[] prices) {
    int[] answer = new int[prices.length];
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i < prices.length; i++) {
      while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
        int index = stack.pop();
        answer[index] = i - index;
      }
      stack.push(i);
    }

    while (!stack.isEmpty()) {
      int index = stack.pop();
      answer[index] = prices.length - index - 1;
    }
    return answer;
  }

문제 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

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

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

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

제한 사항

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

문제 풀이 큐를 이용하여 다리 위에 있는 트럭들을 계산했다. 초가 카운트 되고, 트럭들을 출발시키고, 다리에서 나갈 트럭을 계산한다. 대기 트럭 중 첫번째 트럭을 다리 위로 올릴 수 있는지 무게를 확인하고 가능 하면 옮긴다. 이 과정을 bridge가 빌때까지 반복한다.

코드

  public int solution(int bridge_length, int weight, int[] truck_weights) {
    int time = 0;
    int totalWeight = 0;
    Queue<Integer> bridge = new LinkedList<>();

    for (int i = 0; i < bridge_length; i++) {
      bridge.add(0);
    }

    int index = 0;

    while (!bridge.isEmpty()) {
      time++;
      totalWeight -= bridge.poll();

      if (index < truck_weights.length) {
        if (totalWeight + truck_weights[index] <= weight) {
          bridge.add(truck_weights[index]);
          totalWeight += truck_weights[index];
          index++;
        } else {
          bridge.add(0);
        }
      }
    }
    return time;
  }

문제 설명

운영체제의 역할 중 하나는 컴퓨터 시스템의 자원을 효율적으로 관리하는 것입니다. 이 문제에서는 운영체제가 다음 규칙에 따라 프로세스를 관리할 경우 특정 프로세스가 몇 번째로 실행되는지 알아내면 됩니다.

1. 실행 대기 큐(Queue)에서 대기중인 프로세스 하나를 꺼냅니다.
2. 큐에 대기중인 프로세스 중 우선순위가 더 높은 프로세스가 있다면 방금 꺼낸 프로세스를 다시 큐에 넣습니다.
3. 만약 그런 프로세스가 없다면 방금 꺼낸 프로세스를 실행합니다.
  3.1 한 번 실행한 프로세스는 다시 큐에 넣지 않고 그대로 종료됩니다.
예를 들어 프로세스 4개 [A, B, C, D]가 순서대로 실행 대기 큐에 들어있고, 우선순위가 [2, 1, 3, 2]라면 [C, D, A, B] 순으로 실행하게 됩니다.

현재 실행 대기 큐(Queue)에 있는 프로세스의 중요도가 순서대로 담긴 배열 priorities와, 몇 번째로 실행되는지 알고싶은 프로세스의 위치를 알려주는 location이 매개변수로 주어질 때, 해당 프로세스가 몇 번째로 실행되는지 return 하도록 solution 함수를 작성해주세요.

제한 사항

• priorities의 길이는 1 이상 100 이하입니다.
  • priorities의 원소는 1 이상 9 이하의 정수입니다.
  • priorities의 원소는 우선순위를 나타내며 숫자가 클 수록 우선순위가 높습니다.
• location은 0 이상 (대기 큐에 있는 프로세스 수 - 1) 이하의 값을 가집니다.
  • priorities의 가장 앞에 있으면 0, 두 번째에 있으면 1 … 과 같이 표현합니다.

문제 풀이 문제에서 주어진 프로세스의 순서대로 문제 풀이를 해보았다. 우선 큐를 만들고 그 큐에 프로세스의 우선순위와 위치를 저장한 상태에서 첫번째 프로세스를 꺼내서 큐에서 더 높은 우선순위를 확인한다. 여기서 더 높은 우선순위가 있으면 결과적으로 current[0]인 값보다 우선순위가 뒤임으로 큐에 다시 저장하고, 없으면 order를 기록합니다. curreunt[1]인 프로세스 위치와 location이 같은지 확인하고 같으면 order를 반환합니다. 이 과정을 큐가 비어있을 때까지 반복해주면 됩니다.

코드

public int solution(int[] priorities, int location) {
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < priorities.length; i++) {
      queue.add(new int[]{priorities[i], i});
    }

    int order = 0;
    while (!queue.isEmpty()) {
      int[] current = queue.poll();
      boolean higher = false;

      for (int[] process : queue) {
        if (process[0] > current[0]) {
          higher = true;
          break;
        }
      }
      if (higher) {
        queue.add(current);
      } else {
        order++;
        if (current[1] == location) {
          return order;
        }
      }
    }
    return -1;
  }

문제 설명

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

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

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

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.

• 작업 진도는 100 미만의 자연수입니다.

• 작업 속도는 100 이하의 자연수입니다.

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

  문제 풀이 큐를 사용하는 방식으로 문제를 풀었다. 먼저 문제에서 풀어야하는 것은 첫번째 각 기능을 몇일안에 배포할 수 있는지, 두번째 배포할 때 몇개의 기능을 배포해야되는지 크게 두가지의 문제풀이를 가지고 이렇게 풀이를 해보았다. 기능이 완성되는 일수를 계산해서 큐에 저장하고, 일단 큐의 첫번째 값을 배포 완료 시점으로 설정하여 완료시점보다 작거나 같은 기능들을 묶어 같이 배포하도록 하였다. 묶음으로 된 기능의 갯수를 리스트에 저장하여 반환할 때 배열로 변환하여 반환해주었다.

  코드

  public int[] solution(int[] progresses, int[] speeds) {
    List<Integer> result = new ArrayList<>();
  
    Queue<Integer> daysQ = new LinkedList<>();
    for (int i = 0; i < progresses.length; i++) {
      int days = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]);
      daysQ.add(days);
    }
  
    while (!daysQ.isEmpty()) {
      int currentDay = daysQ.poll();
      int count = 1;
  
      while (!daysQ.isEmpty() && daysQ.peek() <= currentDay) {
        daysQ.poll();
        count++;
      }
      result.add(count);
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.

• arr의 원소는 100 이하인 자연수입니다.

  문제 풀이 전에 구해본 적있는 최소공배수를 구하는 방식을 사용하여 구하였다. 일단 두 수의 최대공약수, 최소공배수를 구하고 n개의 수의 최소공배수를 구하기 위해 첫번째 값을 초기화해주고, 배열을 순회하여 최소공배수를 구하는 방식으로 문제를 풀었다.

  코드

  public int solution(int[] arr) {
    int lcmV = arr[0];
  
    for (int i = 1; i < arr.length; i++) {
      lcmV = lcd(lcmV, arr[i]);
    }
    return lcmV;
  }
  
  private int gcd(int a, int b) {
    while (b != 0) {
      int temp = b;
      b = a % b;
      a = temp;
    }
    return a;
  }
  
  private int lcd(int a, int b) {
    return (a * b) / gcd(a, b);
  }

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

문제 풀이 피보나치 수열과 비슷한 점화식으로 효진이는 1칸, 2칸을 뛸 수 있으니까 n칸까지 가는 방법은 n-1칸에서 1칸을 뛰는 방법과 n-2칸에서 2칸 뛰는 방법이 있다. 이렇게 n칸까지 가는 방법은 2가지가 나오는데 이것을 사용하기 위해서 dp배열을 초기화해주고, for문을 순회하여 n까지의 도달하는 방법이 몇가지인지 찾을 수 있다.

코드

public long solution(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
      dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
    return dp[n];
  }

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

문제 풀이 해당 문제는 탐욕법 방식을 사용하여 풀었다. 먼저 문제를 해결하기 위해 정렬을 해주고, 최선의 선택을 하기 위해 풀이로 가장 가벼운 사람과 가장 무거운 사람을 한 보트에 태우는 것으로 보트를 최선의 방식으로 활용하는 방법이었다. 이어서 함께 태울 수 있으면 포인터를 왼쪽에서는 +, 오른쪽에서는 -로 이동을 한다. 여기서 둘다 태울 수 없다면 보트를 활용하는 방법으로 가장 무거운 사람을 혼자 태워 보내는 방식을 사용하여 최선의 방식을 선택한다. 이렇게 탐욕법의 방식을 사용하여 문제 풀이를 할 수 있다.

코드

 public int solution(int[] people, int limit) {
    Arrays.sort(people);
    int answer = 0;
    int left = 0;
    int right = people.length - 1;

    while (left <= right) {
      if (people[left] + people[right] <= limit) {
        left++;
        right--;
      } else {
        right--;
      }
      answer++;
    }
    return answer;
  }

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

문제 풀이 sum = brown + yellow 이고, sum = 가로 * 세로도 된다. 이를 생각한다면

・ brown = 가로 * 세로 - yellow
・ yellow = (가로 - 2) * (세로 - 2) 

가 될 것이다. 먼저 가로, 세로가 정수인 것을 확인하기 위해 가로가 sum의 약수임을 확인했다. 가로가 정수가 맞다면 세로를 구하고, yellow 타일 갯수가 맞는지 확인하여 제한 사항에 맞춰 answer 값을 반환했다.

코드

 public int[] solution(int brown, int yellow) {
    int[] answer = new int[2];
    int sum = brown + yellow;

    for (int i = 1; i <= sum; i++) {
      if (sum % i == 0) {
        int h = sum / i;
        if ((i - 2) * (h - 2) == yellow) {
          answer[0] = Math.max(i, h);
          answer[1] = Math.min(i, h);
        }
      }
    }
    return answer;
  }

문제 설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한 사항

• 문자열의 길이 : 1,000,000이하의 자연수
• 문자열은 모두 소문자로 이루어져 있습니다.

문제 풀이 짝이 지어진다면 제거를 하라는 문제를 읽고, 제거를 하려면 스택을 써야하나라는 생각이 들었다. 그래서 스택을 사용하면 문제를 풀었다. 먼저 스택이 비어있지 않거나 스택의 맨위의 글자와 c가 같은지 확인하고 같으면 제거하고, 아니면 푸쉬한다. 이를 반복하여 마지막에 스택이 비어있다면 1을 반환하고 아니면 0을 반환한다.

코드

 public 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);
      }
    }
    if (stack.isEmpty()) {
      return 1;
    } else return 0;
  }

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

문제 풀이 피보나치 수열에 대해서 생각을 해보면 n이 0, 1일때는 그냥 그 값이 바로 나온다. 그래서 n이 2이상이어야 한다. 그것을 생각하고, a, b를 0, 1로 초기화하고 for문을 사용하여 순회를 한다. 순회를 하면서 처음에는mod로 나누어 주지않아 오버플로우가 발생했었다. 오버플로우를 방지하기위해 나머지를 출력하고, a, b의 값을 갱신하여 최종 값 b를 반환하였다.

코드

 public int solution(int n) {
    int answer = 0;
    int a = 0;
    int b = 1;
    int mod = 1234567;

    if (n <= 1) {
      return n;
    }
    for (int i = 2; i <= n; i++) {
      answer = (a + b) % mod;
      a = b;
      b = answer;
    }
    return b;
  }

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

제한 사항

• n은 1,000,000 이하의 자연수 입니다.

문제 풀이 2진수에 관련된 메서드를 찾다가 2진수에서 1의 갯수를 찾는 메서드가 있다는 것을 알게 되었고, 그 메서드인 Integer.bitCount()를 사용하여 문제를 풀었다. 먼저 n의 다음 큰 숫자 n+1와 n을 진수한 값을 초기화하였고, n 다음으로 큰 숫자부터 2진수의 1의 갯수를 count와 비교하여 만족할 때까지 answer 값을 늘려가며 가장 작은 수를 찾았다.

코드

 public int solution(int n) {
    int answer = n + 1;
    int count = Integer.bitCount(n);

    while (Integer.bitCount(answer) != count) {
      answer++;
    }
    return answer;
  }

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한 사항

• n은 10,000 이하의 자연수 입니다.

문제 풀이 for문은 두번 순회하여 문제를 해결하는 방식으로 풀 수 있었다. 첫번째 for는 정수 1부터 n까지 값들로 값의 시작점을 설정하고, 두번째 for는 i 부터 n까지 숫자들의 합을 계산한다. 순회하면서 계산된 sum이 n과 같다면 n으로 표현하는 방법의 수 answer를 올리고, 멈추게 된다. 거기에 sum이 n보다 클 경우에는 셀 필요가 없으므로 멈추게 하였다.

코드

public int solution(int n) {
    int answer = 0;
    for (int i = 1; i <= n; i++) {
      int sum = 0;
      for (int j = i; j <= n; j++) {
        sum += j;
        if (sum == n) {
          answer++;
          break;
        } else if (sum > n) {
          break;
        }
      }
    }
    return answer;
  }

문제 설명

문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요.

제한 사항

• 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다.
• 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다.

문제 풀이 "JadenCase 문자열 만들기" 문제와 비슷한 문제로 배열로 만든 단어들을 순회하여 해당 단어의 알파벳의 인덱스가 짝수인지 홀수 인지 확인하여 대문자, 소문자로 변환한다. 그리고 중요한 것은 공백을 만드는 것인데 마지막 단어 전까지 단어가 끝날 때마다 공백을 넣었다. 전에 풀었던 문제와 비슷한 계열이어서 매일매일 코테를 푸는 효과가 나타나는 것 같아 기분이 좋았다. 이제 문제를 보고서 어떤 흐름으로 문제를 풀어야할지 감이 잡히는거 같다.

코드

public String solution(String s) {
    StringBuilder sb = new StringBuilder();
    String[] words = s.split(" ", -1);

    for (int i = 0; i < words.length ; i++) {
      String word = words[i];
      for (int j = 0; j < word.length(); j++) {
        char c = word.charAt(j);
        if (j % 2 == 0) {
          sb.append(Character.toUpperCase(c));
        } else {
          sb.append(Character.toLowerCase(c));
        }
      }
      if (i < words.length - 1) {
        sb.append(" ");
      }
    }
    return sb.toString();
  }

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

문제 풀이

1. 10진법을 문자열 3진법으로 만들기
2. 3진법을 뒤집기
3. 뒤집은 3진법을 10진법으로 만들기 이 순으로 문제를 풀었습니다.

코드

 public int solution(int n) {
    String ten = Integer.toString(n, 3);
    String revere = new StringBuilder(ten).reverse().toString();
    int answer = Integer.parseInt(revere, 3);
    return answer;
  }

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한 사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

문제 풀이 이 문제에서의 조건은 부서가 신청한 금액을 정확히 지원을 해줘야한다는 것으로 만약 지금까지 지원한 금액과 다음 지원할 부서의 신청금의 합이 예산을 넘어가면 다음 지원할 부서는 지원을 못해주는 것으로 조건문을 넣어서 문제를 풀었습니다. 순회를 하면 조건문을 만족시키면 멈추고, 조건문이 충족되지 않았다면 다시 순회하면서 지원금을 계산하고 몇개의 부서를 지원했는지 계산을 하였습니다.

코드

 public int solution(int[] d, int budget) {
    int answer = 0;
    int count = 0;

    Arrays.sort(d);
    for (int i = 0; i < d.length; i++) {
      if (answer + d[i] > budget) {
        break;
      }
      answer += d[i];
      count++;
    }
    return count;
  }

문제 설명

0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

1. x의 모든 0을 제거합니다.
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.

예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한 사항

• s의 길이는 1 이상 150,000 이하입니다.
• s에는 '1'이 최소 하나 이상 포함되어 있습니다.

문제 풀이 s가 1이 될 동안 반복문을 수행하여 이진변환 횟수와 지워진 0의 갯수를 구하였다. 지워진 0의 갯수는 s 길이에서 0을 제거한 후의 s의 길이를 빼서 구해주었다. Integer.toBinaryString()를 사용하여 이진 변환을 해주고, 변환한 횟수 카운트를 늘려주었다.

코드

 public int[] solution(String s) {
    int count = 0;
    int removeCount = 0;

    while (!s.equals("1")) {
      int length = s.length();
      s = s.replace("0", "");
      int newLength = s.length();

      removeCount += length - newLength;

      s = Integer.toBinaryString(newLength);
      count++;
    }
    return new int[]{count, removeCount};
  }