문자열 내 마음대로 정렬하기 / K번째 수 / 두 개 뽑아서 더하기 / [1차]비밀지도 / 콜라 문제

1️⃣ 문자열 내 마음대로 정렬하기

 

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다.

제한사항

• strings는 길이 1 이상, 50이하인 배열입니다.
• strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
• strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
• 모든 strings의 원소의 길이는 n보다 큽니다.
• 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

 

입출력 예

strings	n	return
["sun", "bed", "car"]	1	["car", "bed", "sun"]
["abce", "abcd", "cdx"]	2	["abcd", "abce", "cdx"]

 

 

💻 나의 풀이

import java.util.*;

class Solution {
  public String[] solution(String[] strings, int n) {
      String[] answer = {};
        answer = new String[strings.length];   // 배열 answer의 길이 = 문자열 배열 strings의 길이
        int idx = 0;  
        
        Arrays.sort(strings);   // strings를 사전순 정렬
         
        for(int i = 97; i < 123; i++) {    // 아스키코드 소문자 범위
            for(int j = 0; j < strings.length; j++) {  // strings를 순회
                if(strings[j].charAt(n) == (char)i) {   // strings의 n번째 문자가 현재 아스키코드에 해당하는지
                    answer[idx++] = strings[j];  // answer배열에 해당 문자열을 할당하고 인덱스 증가
                }
            }
        }
        return answer;
  }
}

 

확실히 단계가 넘어갈 수록 문제를 고민하고 해결하는 시간이 길~어지는거 같습니다..

마지막에 어떻게 단어 전체를 다시 정렬해서 반환할까 하는 부분에서 머리를 싸맸네요.

 

코드 풀이를 해보자면

문자열 배열 answer를 초기화시켜주고, 길이를 문자열 배열 strings의 길이와 같게 설정해줍니다.

그리고 나중에 answer의 인덱스로 사용해 문자를 차곡차곡 담기위한 idx 인덱스를 초기화해줍니다.

sort() 메소드를 사용해 string를 오름차순 정렬해줄건데요, 이제는 당연하게 알듯이 문자열을 오름차순 정렬해주면 사전순으로 정렬한 것과 같게 됩니다!

여기까지 했다면, 첫 번째 for문을 사용해 아스키코드 소문자 범위만큼 순회하도록 해줍니다. ( 97 ~ 122 )

두 번째 for문을 사용해 strings의 n번째 문자가 현재 아스키코드에 해당하는지 판별하고, 결과가 참이라면 answer배열에 해당 문자열을 할당하고 인덱스를 증가시켜 다음 자리에 또 다른 문자열을 넣어줍니다.

 

 

 

 

🔍 다른 사람의 풀이

import java.util.*;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};
        ArrayList<String> arr = new ArrayList<>();
        for (int i = 0; i < strings.length; i++) {
            arr.add("" + strings[i].charAt(n) + strings[i]);
        }
        Collections.sort(arr);
        answer = new String[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            answer[i] = arr.get(i).substring(1, arr.get(i).length());
        }
        return answer;
    }
}

 

문자열을 담을 ArrayList arr을 초기화시킵니다.

for문을 사용해 각 문자열의 n번째 문자와 전체 문자열을 연결하여 ArrayList arr에 추가합니다. => 이렇게 함으로써 n번째 문자를 기준으로 정렬할 수 있습니다.

그렇게 해서 만들어진 ArrayList arr을 Collections.sort()를 사용하여 사전순으로 정렬합니다.

그리고 arr의 크기에 맞게 배열 answer를 초기화하고, substring(1, arr.get(i).length()) 을 사용해 각 요소의 첫 번째 문자를 제외한 나머지 부분을 answer에 할당합니다.

substring(1, arr.get(i).length())는 해당 문자열의 두 번째 문자부터 끝까지의 부분 문자열을 반환합니다. 이렇게 함으로써 기준이 되었던 n번째 문자를 제외한 나머지 부분만을 새로운 문자열로 만들어 배열에 저장합니다.

 

✔ substring(1, arr.get(i).length()) 을 사용해 각 요소의 첫 번째 문자를 제외하는 이유?

ArrayList에 문자열을 추가할 때, 각 문자열의 첫 번째 문자는 기준으로 사용된 n번째 문자입니다. 이 문자는 정렬에 사용되었기 때문에, 결과적으로 정렬된 문자열을 배열에 담을 때 첫 번째 문자는 중복되게 됩니다. 따라서 배열에 할당할 때, 각 문자열의 첫 번째 문자를 제외한 나머지 부분만을 새로운 문자열로 만들어서 저장해야 합니다.

예를 들어, 두 문자열이 'abc'와 'acd'이고 n이 1이라면, ArrayList에 추가되는 문자열은 각각 'babc'와 'cacd'가 됩니다. 정렬 후에는 'babc'가 먼저 나오게 되므로, 결과 배열에는 'abc'와 'acd' 순서로 들어가게 됩니다. 이때, 각 문자열의 첫 번째 문자를 제외한 부분을 결과 배열에 저장하여 최종 반환하는 것이 필요합니다.

 

 

import java.util.*;

class Solution {
  public String[] solution(String[] strings, int n) {
      Arrays.sort(strings, new Comparator<String>(){
          @Override
          public int compare(String s1, String s2){
              if(s1.charAt(n) > s2.charAt(n)) return 1;
              else if(s1.charAt(n) == s2.charAt(n)) return s1.compareTo(s2);
              else if(s1.charAt(n) < s2.charAt(n)) return -1;
              else return 0;
          }
      });
      return strings;
  }
}

 

Comparator 인터페이스를 구현한 익명 클래스를 전달하여 정렬 기준을 제공해주는 코드 입니다.

여기서 compare 메서드는 두 문자열 s1과 s2를 비교하며, 비교 결과에 따라 정렬 순서를 결정합니다.

• 먼저 s1.charAt(n) > s2.charAt(n)이면 1을 반환하여 s1이 s2보다 크다고 판단합니다.
• s1.charAt(n) == s2.charAt(n)이면 s1.compareTo(s2)를 호출하여 두 문자열을 사전식으로 비교한 결과를 반환합니다.
• s1.charAt(n) < s2.charAt(n)이면 -1을 반환하여 s1이 s2보다 작다고 판단합니다.

굉장히 자바스럽고 이렇게 코드를 작성해도 되는구나 하고 신기했던 풀이입니다. 

 

💡 int compare(T o1, T o2);

Comparator 인터페이스의 compare 메서드는 두 객체를 비교하는 데 사용됩니다.

여기서 T는 비교하려는 객체의 유형입니다. compare 메서드는 두 개의 객체 o1과 o2를 매개변수로 받아서 비교하고, 비교 결과에 따라 세 가지 경우를 반환합니다.

0 : o1과 o2가 같다는 것을 나타냅니다.
양수(positive) : o1이 o2보다 크다는 것을 나타냅니다.
음수(negative) : o1이 o2보다 작다는 것을 나타냅니다.

 

 

---

 

2️⃣ K번째 수

 

문제 설명

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

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

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

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

 

제한사항

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

 

입출력 예

array	commands	answer
[1, 5, 2, 6, 3, 7, 4]	[[2, 5, 3], [4, 4, 1], [1, 7, 3]]	[5, 6, 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;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        // 결과를 담을 answer 배열
        int[] answer = new int[commands.length];

        // i, j, k를 담은 배열 순회
        for (int i = 0; i < commands.length; i++) {
            // i - 1번째 수부터 j직전까지 배열 추출
            int[] temp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]);
            
            Arrays.sort(temp);   // 오름차순 정렬
            answer[i] = temp[commands[i][2] - 1];    // k번째 수 answer 배열에 담기
        }

        return answer;
    }
}

 

1. for (int i = 0; i < commands.length; i++) : commands 배열을 순회하면서 각 명령에 대한 처리를 수행합니다.
2. int[] temp = Arrays.copyOfRange(array, commands[i][0] - 1, commands[i][1]) : 주어진 배열 array에서 commands[i][0]부터 commands[i][1] - 1까지의 구간을 복사하여 새로운 배열 temp를 생성합니다.  (  commands[i][0] - 1인 이유는 주어진 commands 배열에서의 시작 인덱스를 0부터 시작하는 Java 배열의 인덱스로 변환해야하기 때문입니다. )
3. Arrays.sort(temp) : 새로운 배열 temp를 오름차순으로 정렬합니다.
4. answer[i] = temp[commands[i][2] - 1] : 정렬된 배열에서 commands[i][2] - 1 위치의 원소를 추출하여 결과 배열 answer에 저장합니다.

 

 

🔍 다른 사람의 풀이

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int a = 0;
        for(int[] info : commands){
            int i = info[0];
            int j = info[1];
            int k = info[2];

            int[] buf = Arrays.copyOfRange(array,i-1,j);
            Arrays.sort(buf);
            answer[a] = buf[k-1];
            a++;
        }

        return answer;
    }
}

1. for(int[] info : commands): commands 배열을 순회하면서 각 명령에 대한 처리를 수행합니다.
2. int i = info[0];, int j = info[1];, int k = info[2]; : 현재 명령에 대한 시작 인덱스(i), 끝 인덱스(j), 추출할 위치(k)를 변수에 저장합니다.
3. int[] buf = Arrays.copyOfRange(array, i - 1, j); : 주어진 배열 array에서 i-1부터 j-1까지의 구간을 복사하여 새로운 배열 buf를 생성합니다.
4. Arrays.sort(buf); : 새로운 배열 buf를 오름차순으로 정렬합니다.
5. answer[a] = buf[k - 1]; : 정렬된 배열에서 k-1 위치의 원소를 추출하여 결과 배열 answer에 저장합니다.
6. a++; : 다음 명령을 처리하기 위해 인덱스를 증가시킵니다.

 

---

 

3️⃣ 두 개 뽑아서 더하기

 

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

 

입출력 예

numbers	result
[2, 1, 3, 4, 1]	[2, 3, 4, 5, 6, 7]
[5, 0, 2, 7]	[2, 5, 7, 9, 12]

 

입출력 예 #1

• 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3 입니다.
• 5 = 1 + 4 = 2 + 3 입니다.
• 6 = 2 + 4 입니다.
• 7 = 3 + 4 입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2 입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

 

 

❌틀린 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length * (numbers.length - 1) / 2];
        int idx = 0;
        
        for(int i=0; i<numbers.length; i++) {
            for(int j=i+1; j<numbers.length; j++) {
                int sum = numbers[i] + numbers[j];
                answer[idx++] = sum;
            }
        }
         
        Arrays.sort(answer);   // 오름차순 정렬
        
        return answer;
    }
}

 

중복된 값이 다 출력돼서 틀린 것 같습니다.

 

 

 

💻 나의 풀이

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int[] numbers) {
    	// 결과를 담을 list 선언
        List<Integer> list = new ArrayList<>();

        // 배열 numbers의 모든 두 요소의 합을 구하기 위해 2중 반복문
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
            	// 두 요소의 합이 list에 존재하지 않으면 담기
                if (!list.contains(numbers[i] + numbers[j])) {
                    list.add(numbers[i] + numbers[j]);
                }
            }
        }

        // list를 오름차순 정렬하면서 int 배열로 변환
        return list.stream().sorted().mapToInt(i -> i).toArray();
    }
}

 

이중 반복문으로 배열의 두 요소를 합하는 모든 경우의 수를 구했습니다.

주의할 점은 첫 번째 반복문의 시작 인덱스는 0, 두 번째 반복문의 시작 인덱스는 i+1 이라는 겁니다!

그리고 contais() 메소드를 통해 값의 포함 여부, 중복 여부를 판단하고

add() 메소드로 값을 넣어줍니다.

마지막으로 stream을 통해 int로의 타입변환과 오름차순 정렬을 한 번에 해준 후, toArray() 메서드를 통해 결과를 int array로 반환합니다.

 

 

 

🔍 다른 사람의 풀이

import java.util.TreeSet;
import java.util.Set;

class Solution {
    public int[] solution(int[] numbers) {
    	Set<Integer> list = new TreeSet<>();
        int size = numbers.length;
        
        for(int i=0; i<size; i++) {
        	for(int j=i+1; j<size; j++) {
            	list.add(numbers[i] + numbers[j]);
            }
        }
        
        int[] answer = list.stream().mapToInt(Number::intValue).toArray();
        
        return answer;
    }
}

 

TreeSet을 사용한 풀이입니다.

Set 자료구조는 중복된 원소를 허용하지 않으므로 중복을 방지할 수 있고, TreeSet은 내부적으로 이진 검색 트리를 사용하여 원소를 정렬된 상태로 유지합니다.

 

1. Set<Integer> list = new TreeSet<>(); : TreeSet을 생성하여 중복된 값을 방지하고, 내부적으로 오름차순으로 정렬된 상태를 유지할 수 있도록 합니다.
2. list.add(numbers[i] + numbers[j]); : 중복을 방지하기 위해 Set에 값을 추가할 때, 합을 계산하여 추가합니다.
3. int[] answer = list.stream().mapToInt(Number::intValue).toArray(); : Set을 스트림으로 변환한 후, 이를 정수형 배열로 변환합니다.

만약 HashSet을 선택했다면 sort를 하여 오름차순 정렬을 했어야 됐을텐데 TreeSet을 사용했기 때문에 sort를 사용할 필요가 없습니다!

 

 

---

 

 

4️⃣ [1차] 비밀지도

 

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

제한사항

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

 

입출력 예

매개변수	값
n	5
arr1	[9, 20, 28, 18, 11]
arr2	[30, 1, 21, 17, 28]
출력	["#####","# # #", "### #", "# ##", "#####"]

 

매개변수	값
n	6
arr1	[46, 33, 33, 22, 31, 50]
arr2	[27, 56, 19, 14, 14, 10]
출력	["######", "### #", "## ##", " #### ", " #####", "### # "]

 

 

❌틀린 코드

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i=0; i<n; i++) {   // 한 변의 길이만큼 순회
            // 2진수로 변환, 하나라도 1인 경우 1로 저장됨
            answer[i] = Integer.toBinaryString(arr1[i] | arr2[i]);   
            answer[i] = answer[i].replace('0', ' ');   // 2진수값이 0 -> 공백
            answer[i] = answer[i].replace('1', '#');   // 2진수값이 1 -> #
        }
        return answer;
    }
}

테스트2에서 틀린 코드입니다.

 

 

💻 나의 풀이

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i=0; i<n; i++) {   // 한 변의 길이만큼 순회
            // 2진수로 변환, 하나라도 1인 경우 1로 저장됨
            answer[i] = Integer.toBinaryString(arr1[i] | arr2[i]);   
            answer[i] = answer[i].replace('0', ' ');   // 2진수값이 0 -> 공백
            answer[i] = answer[i].replace('1', '#');   // 2진수값이 1 -> #
            
            // n자리 수가 될 때까지 앞에 공백을 추가
            while (answer[i].length() < n) {
                answer[i] = ' ' + answer[i];
            }
        }
        
        return answer;
    }
}

 

while (answer[i].length() < n) {
                answer[i] = ' ' + answer[i];
            }

뭐가 틀렸나 하고 보니 제가 작성한 코드는 n자리 수가 아닐 때 앞에 공백이 없이 바로 답이 나와버리는 것 같습니다.

그래서 마지막에 while문을 넣어 길이가 n자리 수가 될 때까지 앞에 공백을 추가하고, 그 후에 답을 추가해라 라는 부분을 추가작성했더니 통과되었습니다.

 

 answer[i] = Integer.toBinaryString(arr1[i] | arr2[i]);

먼저 이 문제를 풀기 위해 알아야 할 것은 이진수로 변환하는 메소드인데요. 정확히 뭐였는지는 기억 안났지만 대충 진수를 변환하는 메소드가 있었다는 것을 기억하고 있어 메소드만 구글링 해 더 쉽게 풀 수 있었습니다! (0단계 문제 중에 있었던거 같은데...)

그 다음엔, 두 지도를 합친 값을 어떻게 표현할까였는데요. 처음엔 if문으로 작성해보다가 '또는' 이라는 단어가 머릿속에 떠오르면서 비트 연산자 중 OR이 떠올랐습니다. ( 정처기 공부 때 죽어라 했던....효과가 여기서 나타나나.....)

이 두가지를 몰랐다면 꽤나 복잡한 풀이가 나왔을 것 같네요.

 

💡 Integer.toBinaryString(int i)
정수 i 값(십진수)을 이진수 문자열로 반환한다.

 

💡 Bit 연산(AND, OR) 

AND(&) 연산자
비트 단위로 AND 연산을 한다. 즉, &연산은 두 개의 비트가 모두 1일 때 1을 반환하는 AND 연산을 한다.

OR(|) 연산자
비트단위로 OR 연산을 한다. 즉, |연산은 두 개의 비트 중 하나라도 1이면 1을 반환하는 OR 연산입니다.

 

 

 

🔍 다른 사람의 풀이

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for(int i=0; i<n; i++) {   // 한 변의 길이만큼 순회
            // 2진수로 변환, 하나라도 1인 경우 1로 저장됨
            answer[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
            // 문자열을 지정된 길이로 포맷팅-> 폭이 n인 문자열 형식
            answer[i] = String.format("%" + n + "s", answer[i]);
            answer[i] = answer[i].replace('0', ' ');   // 2진수값이 0 -> 공백
            answer[i] = answer[i].replace('1', '#');   // 2진수값이 1 -> #
        }
        return answer;
    }
}

 

answer[i] = String.format("%" + n + "s", answer[i]);

String.format("%" + n + "s", answer[i])는 문자열을 지정된 길이(n)로 포맷팅하는 코드입니다.

이 코드는 answer[i]의 문자열을 오른쪽 정렬된 형태로 만들어줍니다. 여기서 사용된 형식 지정자인 %" + n + "s"는 폭(width)을 동적으로 지정할 수 있도록 해줍니다.

% : 형식 지정자의 시작

 

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = new String[n];
      String temp;

      for(int i = 0 ; i < n ; i++){
          temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
          temp = temp.substring(temp.length() - n);
          temp = temp.replaceAll("1", "#");
          temp = temp.replaceAll("0", " ");
          answer[i] = temp;
      }

      return answer;
  }
}

 

format() 메소드를 사용해 처음부터 길이를 16으로 지정한 후에 substring()으로 자르는 방식입니다.

이게 더 빠르다고 하네요!

 

 

---

 

 

5️⃣ 콜라 문제

 

문제 설명

오래전 유행했던 콜라 문제가 있습니다. 콜라 문제의 지문은 다음과 같습니다.

정답은 아무에게도 말하지 마세요.

콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가?

단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다.

문제를 풀던 상빈이는 콜라 문제의 완벽한 해답을 찾았습니다. 상빈이가 푼 방법은 아래 그림과 같습니다. 우선 콜라 빈 병 20병을 가져가서 10병을 받습니다. 받은 10병을 모두 마신 뒤, 가져가서 5병을 받습니다. 5병 중 4병을 모두 마신 뒤 가져가서 2병을 받고, 또 2병을 모두 마신 뒤 가져가서 1병을 받습니다. 받은 1병과 5병을 받았을 때 남은 1병을 모두 마신 뒤 가져가면 1병을 또 받을 수 있습니다. 이 경우 상빈이는 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받을 수 있습니다.

문제를 열심히 풀던 상빈이는 일반화된 콜라 문제를 생각했습니다. 이 문제는 빈 병 a개를 가져다주면 콜라 b병을 주는 마트가 있을 때, 빈 병 n개를 가져다주면 몇 병을 받을 수 있는지 계산하는 문제입니다. 기존 콜라 문제와 마찬가지로, 보유 중인 빈 병이 a개 미만이면, 추가적으로 빈 병을 받을 순 없습니다. 상빈이는 열심히 고심했지만, 일반화된 콜라 문제의 답을 찾을 수 없었습니다. 상빈이를 도와, 일반화된 콜라 문제를 해결하는 프로그램을 만들어 주세요.

콜라를 받기 위해 마트에 주어야 하는 병 수 a, 빈 병 a개를 가져다 주면 마트가 주는 콜라 병 수 b, 상빈이가 가지고 있는 빈 병의 개수 n이 매개변수로 주어집니다. 상빈이가 받을 수 있는 콜라의 병 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 1 ≤ b < a ≤ n ≤ 1,000,000
• 정답은 항상 int 범위를 넘지 않게 주어집니다.

입출력 예

a	b	n	result
2	1	20	19
3	1	20	9

 

 

💻 나의 풀이

class Solution {
    public int solution(int a, int b, int n) {
        int answer = 0;
        int coke = n;
        
        while(coke >= a) {
            answer += (coke / a) * b;   // a개당 b개를 줌 => a로 나눈 몫 * b개
            coke = coke / a * b + coke % a;  // 나머지 병수가 있으므로 a로 나눈 나머지를 더해준다.
        }
        
        return answer;
    }
}

 

괜히 길이에 쫄았던 문제 😂

0단계에서 비슷한 류의 피자 문제들을 떠올리며 풀었습니다.

먼저 상빈이가 가진 빈 병의 개수는 n이고, 콜라 빈 병 a개 당 b개를 주는거니까 

상빈이가 받을 수 있는 개수는 총 n을 a로 나눈 몫에 b를 곱한 값 입니다.

 

그 후에 다시 상빈이가 가진 빈 병의 개수를 업데이트 해주어야 하는데요, 가진 빈 병의 개수 n은 방금 구한 n / a * b 값에, 나머지 병수가 있는 경우도 있을테니 ( 예를 들어, 빈 병 4개 중 3개를 가져가 1병의 콜라를 받았을 경우엔 받은 1병 + (4-3)한 1병 = 총 2병이 남은 개수가 된다. ) n을 a로 나눈 몫이 아닌 나머지를 더해주면 됩니다.

 

 

 

🔍 다른 사람의 풀이

class Solution {
    public int solution(int a, int b, int n) {
        return (n > b ? n - b : 0) / (a - b) * b;
    }
}

 

그냥 이렇게 끝내버릴 수도 있네요..!!!