항해 99 - 2023.02.01 TIL

항해99를 시작하니 시간이 훌쩍훌쩍 지나가는 것 같다.

시작일이 1월 8일이였는데, 어느덧 2월의 첫 날이다.

 

오늘도 어제에 이어서 알고리즘 문제 풀이를 진행했다.

 

---

체육복

문제 설명

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

 

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

 

제한 사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

 

입출력 예

 

 

import java.util.HashSet;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;

        HashSet<Integer> resSet = new HashSet<>();
        HashSet<Integer> loSet = new HashSet<>();

        for(int i: reserve) {
            resSet.add(i);
        }

        for(int i: lost) {
            if(resSet.contains(i)) {
                resSet.remove(i);
            }
            else {
                loSet.add(i);
            }
        }

        for(int i: resSet) {
            if(loSet.contains(i-1)) {
                loSet.remove(i - 1);
            }
            else if(loSet.contains(i+1)) {
                loSet.remove(i + 1);
            }
        }

        answer = n - loSet.size();

        return answer;
    }
}

처음은 ArrayList로 풀이를 진행했었는데, 효율성 검증에 계속 통과하지 못했다. 구글링 해보니 HashSet을 사용해서 중첩 for문을 사용하지 않고도 구현한 풀이가 있어 분석해보았다.

기본적인 코드로만 구현이 되어있어서 이해하기 어렵지는 않았던 것 같다. 다중 for문이 많아질 때 다른 컬렉션으로도 생각하는 습관을 길러야겠다.

 

---

폰켓몬

문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

 

입출력 예

 

import java.util.ArrayList;

class Solution {
    public int solution(int[] nums) {
        int num = nums.length/2;

        ArrayList<Integer> list = new ArrayList();
        for(int i : nums){
           if(!(list.contains(i))){
               list.add(i);
           }
        }
        if(list.size() < num){
            return list.size();
        }else{
            return num;
        }
    }
}

문제는 복잡했는데 깊게 생각해보니 별거 없었던 문제다. 주어진 포켓몬의 N / 2 가 가질 수 있는 최대 종류의 포켓몬이기 때문에 그 이하의 경우의 수만 구해주면 된다. 배열에 있는 모든 종류의 숫자를 담아주고, 그 숫자가 N/2보다 작을 경우만 그 수를 반환하도록 했다.

 

---

비밀지도 [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을 만족한다.

 

출력 형식

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

 

입출력 예

 

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] strArr = new String[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            strArr[i] = String.format("%0"+n+"d",Long.parseLong(Long.toBinaryString(arr1[i] | arr2[i]))); //값이 5자리 미면이면 0으로 표시. 비트 연산자 or 사용
            // 2,6번 테스트 케이스 통과되지 않아 수정 테스트 케이스의 표현범위가 많아 에러난듯..
            strArr[i] = strArr[i].replace('0',' ');
            strArr[i] = strArr[i].replace('1','#');
        }
        return strArr;
    }
}

10진수를 2진수로 변환하는 함수와 String.format 함수, 비트 연산자가 핵심인 문제이다.

배열에 있는 숫자들을 2진법으로 변환하여 또는 | 비트 연산자를 사용해서 합쳐? 주었다.

 

그냥 변환하면 앞에 0숫자가 붙지않는 2진법 숫자로 변환되는데, String,format 함수로 N자리까지 0이 표기되도록 설정했다.

 

---

키패드 누르기

문제설명

스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다.

이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다.
맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다.

1. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다.
2. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다.
3. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다.
4. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.
   4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다.

순서대로 누를 번호가 담긴 배열 numbers, 왼손잡이인지 오른손잡이인 지를 나타내는 문자열 hand가 매개변수로 주어질 때, 각 번호를 누른 엄지손가락이 왼손인 지 오른손인 지를 나타내는 연속된 문자열 형태로 return 하도록 solution 함수를 완성해주세요.

 

제한 사항

• numbers 배열의 크기는 1 이상 1,000 이하입니다.
• numbers 배열 원소의 값은 0 이상 9 이하인 정수입니다.
• hand는 "left" 또는 "right" 입니다.
• "left"는 왼손잡이, "right"는 오른손잡이를 의미합니다.
• 왼손 엄지손가락을 사용한 경우는 L, 오른손 엄지손가락을 사용한 경우는 R을 순서대로 이어붙여 문자열 형태로 return 해주세요.

 

입출력 예

 

 

class Solution {
    public String solution(int[] numbers, String hand) {
        String answer = "";
        int left = 10; // 맨 아랫줄 10 11 12로
        int right = 12;
        for(int i : numbers){
            if(i == 1 || i == 4 || i == 7){
                answer += "L";
                left = i;

            }else if(i == 3 || i == 6 || i == 9){
                answer += "R";
                right = i;
            }else{
                if(i == 0 ){ i += 11;}
                int leftDis = Math.abs(i-left)/3 + Math.abs(i-left)%3;
                int rightDis = Math.abs(i-right)/3 + Math.abs(i-right)%3; //현재 수와 현재 손가락 위치를 계산해서 거리를 구함.

                if(leftDis < rightDis){
                    answer += "L";
                    left = i;
                }else if(leftDis > rightDis){
                    answer += "R";
                    right = i;
                }else{
                    if(hand.equals("left")){
                        answer += "L";
                        left = i;
                    }else {
                        answer += "R";
                        right = i;
                    }
                }
            }

        }
        return answer;
    }
}

계속 붙잡고 있어도 이동할 칸의 거리를 어떻게 구해야할지 몰라서 구글링했다..

현재 누르려는 숫자에서 이전 숫자에서를 뺀 절대값을 3으로 나누고, 다시 같은과정으로 뺀 절대을 3으로 나눈 나머지를 더해서 거리를 구했다. 키패드가 3개씩 이루어져 있으니, 위아래로 이동하는 값을 3이라고 보고, 좌우로 이동하는 값을 1로 가정하여 계산한 식인 듯 하다.

거리 계산외에는 조건문으로 처리하면 되어서 간단하게 풀 수 있었다..

 

---

느낀 점

뒤로 갈수록 문제의 난이도가 높아지고, 문제 설명도 길어져서 이해하는데 시간이 많이 걸렸던 것 같다.

처음 문제를 보고 풀린 문제가 많지 않고, 막상 결과가 나와도 효율성에서 실패가 나와서 내 풀이방법에 대한 믿음이 사라진 것 같다.. 기술 매니저님께 고충을 털어놓으니, 알고리즘을 처음 접하는 단계에 이 문제들을 다 풀 수 있다는게 말이 안되는 거라고 위로를 해주셔서 조금은 회복할 수 있었다.

모르는 문제가 나오더라도, 구글링을 통해서 코드를 분석하고 사고력을 기르는 식으로 쭉 이어나갈 생각이다.

하루에 한 문제는 계속 풀어보면서 감을 잃지 않도록 유지해야겠다.

 

그리디 알고리즘?? 에 대해서 알게 되었는데 가장 간단한 알고리즘이라고 한다. 이진 탐색과 비슷한 원리인 것 같다. 알고리즘은 접하면 접할수록 공부해야할 범위가 더 많아지는 것 같다..