💪🏻 programmers Lv1(24.10.21 - 5문제)

programmers Lv1(24.10.21 - 5문제)

55) 카드 뭉치

• card1과 card2에 적힌 단어들로 goal 만들기. 가능하면 “Yes” 출력, 불가능하면 “No” 출력하기

  • 📌 풀이

    • 1) 향상된 for문을 이용해 goal을 word로

    • 2) idx1이 cards1의 길이보다 크고 word의 문자열과 cards1의 idx1 인덱스의 문자열이 같을 경우 인덱스 증가

    • 3) idx2가 cards2의 길이보다 크고 words의 문자열과 cards2의 idx2 인덱스의 문자열이 같을 경우 인덱스 증가

    • 4) 그 외의 경우 “No” 출력, 맞을 경우 “Yes” 출력

import java.util.*;
class Solution {
    public String solution(String[] cards1, String[] cards2, String[] goal) {
        int idx1 = 0;
        int idx2 = 0;
        
        for(String word : goal)
        {
            if(cards1.length > idx1 && word.equals(cards1[idx1]))
            {
                idx1++;
            }
            else if(cards2.length > idx2 && word.equals(cards2[idx2]))
            {
                idx2++;
            }
            else{
                return "No";
            }
        }
        return "Yes";
    }
}

---

56) 포켓몬

• 가장 많은 종류의 포켓몬을 선택하는 방법을 찾아 그때 포켓몬 종류 번호의 개수를 반환

• 📌 내 풀이

  • 1) [3, 1, 2, 3] 이 들어있으면 3 , 3은 한 종류로 보기 때문에 중복을 허용하지 않으므로 HashSet을 사용

  • 2) nums의 길이만큼 반복해서 set에 요소 저장

  • 3) nums의 길이를 2로 나누어서 num이라는 변수 생성 후, num의 길기아 set의 크기보다 작으면 num을 출력, 아니라면 set의 크기 출력

import java.util.*;
class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        int num = nums.length/2; //2
        HashSet<Integer> set = new HashSet<>();
        
        for(int i=0;i<nums.length;i++)
        {
            set.add(nums[i]);
        }
        if(num < set.size())
        {
            answer = num;
        }
        else{
            answer = set.size();
        }
        return answer;
    }
}

---

57) 2016년

• 2016년 1월 1일은 금요일이다. 2016년 a월 b일은 무슨 요일인지 구하기

• 답안 참고

import java.util.*;
class Solution {
    public String solution(int a, int b) {
        String answer = "";
        String[] day = {"FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"};
        int[] date = {31,29,31,30,31,30,31,31,30,31,30,31};
        int allDate = 0;
        for(int i=0;i<a-1;i++)
        {
            allDate += date[i];
        }
        allDate += (b-1); // 1월 1일을 기준으로 0일이 금요일로 시작
        answer = day[allDate % 7];
        return answer;
    }
}   
// a = 5, b = 24
// allDate = 31 + 29 + 31 + 30 = 121
// allDate = 121 + 23 = 144
// 144 % 7 = 4, day[4] = TUE

---

58) 기사단원의 무기

• 기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를 구하라.

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int[] cnt = new int[number+1];
        for(int i=1;i<=number;i++)
        {
           for(int j=1;j<=i;j++)
           {
               if(i%j==0)
               {
                   cnt[i]++;
               }
           }
            if(cnt[i]<=limit)
           {
               answer+=cnt[i];
           }
           else if(cnt[i]>limit)
           {
               answer+=power;
            }
        }
        return answer;
    }
}

• 테스트 케이스 27개중 2개 시간 초과 뜸.

• 숫자 i에 대해 1부터 i까지 모든 숫자를 순회하여 약수를 찾는 이 방식은 시간 복잡도가 매우 큼.

• 시간 복잡도. 이중반복문으로 : O(n^2)

class Solution {
    public int solution(int number, int limit, int power) {
        int answer = 0;
        int[] cnt = new int[number+1];
        for(int i=1;i<=number;i++)
        {
           for(int j=1;j*j<=i;j++)
           {
               if(i%j==0)
               {
                   cnt[i]++;
                   if(j!=i/j)
                   {
                       cnt[i]++;
                   }
               }
           }
            if(cnt[i]<=limit)
           {
               answer+=cnt[i];
           }
           else if(cnt[i]>limit)
           {
               answer+=power;
            }
        }
        return answer;
    }
}

• for (int j = 1; j * j <= i; j++)로 1부터 √i까지만 확인하고, 대칭되는 약수 (i / j)도 함께 카운트하여 중복 계산을 피했다.

• j!=i/j 를 하는 이유는 중복된 약수는 방지하고 그 외의 대칭되는 약수의 개수를 카운트 하기 위해서.

• 시간 복잡도가 O(n^2) -> O(n*sqrt(n))으로 줄었다.

---

59) 모의고사

• 📌 내 풀이

  • 1) num1, num2, num3 배열을 만들어 1번, 2번, 3번 수포자의 숫자 배열 저장

  • 2) 정답 배열의 길이만큼 반복문, 1, 2, 3번 수포자의 숫자와 비교해서 같을 경우 각 카운트 증가

  • 3) 제일 큰 값 maxScore에 저장

  • 4) 수포자 1, 2, 3번의 값이 maxScore일 경우 list에 요소 추가

  • 5) 리스트 요소 출력

import java.util.*;
class Solution {
    public int[] solution(int[] answers) {
        int[] answer;
        int[] num1 = {1,2,3,4,5};
        int[] num2 = {2,1,2,3,2,4,2,5};
        int[] num3 = {3,3,1,1,2,2,4,4,5,5};
        int cnt1 = 0, cnt2 = 0, cnt3 = 0;
        
        for(int i=0;i<answers.length;i++){
            if(answers[i] == num1[i%num1.length])
            {
                cnt1++;
            }
            if(answers[i] == num2[i%num2.length])
            {
                cnt2++;
            }
            if(answers[i] == num3[i%num3.length])
            {
                cnt3++;
            }
        }
       
        int maxScore = Math.max(cnt1, Math.max(cnt2,cnt3));
        ArrayList<Integer> list = new ArrayList<>();
        if(cnt1 == maxScore)
        {
            list.add(1);
        }
        if(cnt2 == maxScore)
        {
            list.add(2);
        }
        if(cnt3 == maxScore)
        {
            list.add(3);
        }
      
        answer = new int[list.size()];
        
        for(int i=0;i<list.size();i++)
        {
            answer[i] = list.get(i);
        }
        
        return answer;
    }
}