CODEKATA 86 ~ 90

86번 H-Index

/*
문제 분석
1. 정보
    - H-Index는 과학자의 생산성과 영향력을 나타내는 지표
    - 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 함
        - 발표한 논문 n편 중 h번 이상 인용된 논문이 h편 이상이고, 나머지 논문이 h번 이하 인용되었다면 h의 최댓갑이 과학자의 H-Index

2. 목표
    - 주어진 배열을 활용해 과학자의 H-Index를 return
3. 제약 조건
    - 1 <= 논문의 수 <= 1000
    - 0 <= 논문별 인용 횟수 <= 10000

풀이
1. 아이디어
    - 최대 인용횟수가 10000이므로
        - 길이가 10000인 배열을 만들어 i번 인용된 논문의 수를 저장한다
        - 값이 저장되면, 10000부터 0까지 아래로 인용된 논문의수를 더해 누적합을 구한다
            - 누적합을 구하는 이유는,
            - 예를 들어, 4번이상 인용된 논문은 4 ~ 10000까지의 인용된 논문의 합이기 때문이다.
            - 따라서 i번째 값은 i ~ 10000까지의 누적된 합이 들어와야 한다.
        - 누적합을 구하였다면, 우리는 최댓값을 구해야 하기 때문에, 10000부터 0까지 순회한다.
            - 이때, 인용된 논문의 수와 i 값이 같다면, 즉 h번 이상 인용된 논문이 h편 이상이라면,
            - 해당 i값을 return 해주면 된다.
*/

class Solution {
        public int solution(int[] citations) {
            int[] check = new int[10001];
            for (int cur : citations) {
                check[cur]++;
            }
            for (int i = 10000; i > 0; i--) {
                check[i - 1] += check[i];
            }
            int answer = 0;
            for (int i = 10000; i >= 0; i--) {
                if (i <= check[i]) {
                    answer = i;
                    break;
                }
            }
            return answer;
        }
    }

87번 n^2 배열 자르기

/*
문제 분석
1. 정보
    - 정수 n, left, right가 주어짐
    - 다음 과정을 거쳐 1차원 배열을 만들고자 함
        - 1. n행 n열 크기의 비어있는 2차원 배열을 제작
        - 2. 1행 1열 부터 i행 i열까지의 영역 내 모든 빈 칸을 숫자 i로 채움
        - 3. 1행 2행 n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 제작
        - 4. 새로운 1차원 배열을 arr이라 할때, arr[left], arr[left + 1], ... arr[right] 만 남기고 나머지 삭제

2. 목표
    - 만들어진 1차원 배열을 return

3. 제약 조건
    - 1 <= n <= 10^7
    - 0 <= left <= right <= n^2
    - right - left < 10^5

풀이
1. 아이디어
    - 일단 단순 구현으로는 풀 수 없을 것이라 생각함
        - n 이 최대 10^7이기 때문에, 반드시 메모리 초과 발생할 것이라 생각했음
    - 그렇다면 left, right의 숫자를 보고 어디서부터 어디까지인지 파악
        - left의 좌표 : (left / n, left % n)
        - n * n 배열에서 left의 좌표를 알았음
        - right - left 는 최대 10만이므로, for문을 사용해도 괜찮을 듯
        - (i,j)의 값은 i와 j 값중 더 큰 값 + 1
        - 즉 for문을 통해 i와 j를 업데이트 하면서 해당 값에 맞는 값을 배열에 저장 후 return 해줌
*/
class Solution {
        public int[] solution(int n, long left, long right) {
            int[] answer = new int[(int) (right - left + 1)];
            long lx = left / n;
            long ly = left % n;

            for (int i = 0; i < answer.length; i++) {
                answer[i] = (int) (Math.max(lx, ly) + 1);
                ly++;
                if (ly == n) {
                    ly = 0;
                    lx++;
                }
            }

            return answer;
        }
    }

88번 행렬의 곱셈

/*
문제 분석
1. 정보
    - 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환
2. 목표
    - 2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환
3. 제약 조건
    - 2 <= 행과 열의 길이 <= 100
    - -10 <= 원소 <= 20

풀이
1. 아이디어
    - arr1 -> a * b
    - arr2 -> b * c
    - 결과 배열 -> a * b
    - for(i : 0 ~ a)
        - for(j : 0 ~ c)
            - for(k : 0 ~ b)
                sum += arr1[i][k] * arr2[k][j]
            - answer[i][j] = sum
*/

class Solution {
        public int[][] solution(int[][] arr1, int[][] arr2) {
            int[][] answer = new int[arr1.length][arr2[0].length];

            for (int i = 0; i < arr1.length; i++) {
                for (int j = 0; j < arr2[0].length; j++) {
                    int sum = 0;
                    for (int k = 0; k < arr1[0].length; k++) {
                        sum += arr1[i][k] * arr2[k][j];
                    }
                    answer[i][j] = sum;
                }
            }
            return answer;
        }
    }

89번 할인 행사

/*
문제 분석
1. 정보
    - XYZ 마트는 일정한 금액을 지불하면 10일동안 회원 자격을 부여함
    - XYZ 마트에서는 회원을 대상으로 매일 한 가지 제품을 할인하는 행사를 함
        - 할인하는 제품은 하루에 하나만 구매 가능
    - 정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치할 경우에 맞춰서 회원가입을 하려 함
        - 예를 들어
            - 원하는 제품이 바나나 3개, 사과 2개, 쌀 2개, 돼지고기 2개, 냄비 1개이며,
            - XYZ 마트에서 14일간 회원을 대상으로 할인하는 제품이 순서대로 치킨, 사과, 사과, 바나나, 쌀, 사과, 돼지고기, 바나나, 돼지고기, 쌀, 냄비, 바나나, 사과, 바나나인 경우
            - 셋째날, 넷째날, 다섯째에 회원가입을 한다면 원하는 제품과 수량이 일치하기 때문에 셋 중 하루에 회원 가입을 하려 함

2. 목표
    - 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수를 return

3. 제약 조건
    - 1 <= 원하는 제품 개수 = 수량 <= 10
    - 10 <= 할인 제품 길이 <= 100000
    - want와 discount 원소는 모두 알파벳 소문자로 이루어짐

풀이
1. 아이디어
    - Map<String, Integer>를 만들어 want에 해당하는 물품을 저장
        - discount 배열에서 i번째 ~ i + 10번째 일수에 해당하는 물품들 중 want에 해당하는 물품이 존재한다면 해당 값++
        - 이후 i번째 요일에 회원가입을 할 경우 모든 품목을 할인 받을 수 있는지 검사
            - map배열을 돌며 개수가 일치하는지 검사후 모두 일치하면 answer++
*/

import java.util.*;
import java.util.Map.*;

class Solution {
        public int solution(String[] want, int[] number, String[] discount) {
            Map<String, Integer> wm = new HashMap<>();
            Map<String, Integer> dm = new HashMap<>();
            int answer = 0;

            for (int i = 0; i < want.length; i++) {
                wm.put(want[i], number[i]);
                dm.put(want[i], 0);
            }

            for (int i = 0; i < 10; i++) {
                if (dm.containsKey(discount[i])) {
                    dm.put(discount[i], dm.get(discount[i]) + 1);
                }
            }

            boolean flag = true;
            for (Entry<String, Integer> entry : dm.entrySet()){
                if(!wm.get(entry.getKey()).equals(entry.getValue())){
                    flag = false;
                    break;
                }
            }
            if(flag){
                answer++;
            }

            for (int i = 10; i < discount.length; i++) {
                if (dm.containsKey(discount[i - 10])) {
                    dm.put(discount[i - 10], dm.get(discount[i - 10]) - 1);
                }
                if (dm.containsKey(discount[i])) {
                    dm.put(discount[i], dm.get(discount[i]) + 1);
                }

                flag = true;
                for (Entry<String, Integer> entry : dm.entrySet()){
                    if(!wm.get(entry.getKey()).equals(entry.getValue())){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    answer++;
                }
            }
            
            return answer;
        }
    }

90번 의상

/*
문제 분석
1. 정보
    - 코니는 매일 다른 옷을 조합하여 입는 것을 좋아함
    - 예를 들어,
        - 얼굴 : 동그란 안경, 검정 선글라스
        - 상의 : 파란색 티셔츠
        - 하의 : 청바지
        - 겉옷 : 긴 코트
    - 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면
    - 다음날은 청바지를 추가로 입거나, 동그란 안경 대신 검정 선글라스를 착용해야함
        - 코니는 각 종류별 최대 1가지 의상만 착용 가능
        - 일부가 겹치더라도 다른 의상이 겹치지 않거나, 추가로 착용한 경우도 다른 방법으로 간주
        - 하루에 최소 한 개 이상은 입어야 함

2. 목표
    - 서로 다른 옷의 조합의 수를 return

3. 제약 조건
    - 1 <= 코니가 가진 의상의 수 <= 30
    - 같은 이름은 존재 X
    - 모든 원소는 문자열로 이루어짐
    - 1 <= 문자열의 길이 <= 20, 알파벳 소문자 or _로 이루어짐

풀이
1. 아이디어
    - Map<String, String>을 통해 일단 의상들을 담는다.
    - 각 종류 별로 의상의 개수가 담기게 될 것이다.
        - 여기서 각 종류 별로
            - 의상의 개수 + 1을 한 값을 결과값에 곱해준다
            - +1의 이유는 해당 의상을 입지 않았을 경우를 포함 해야 하기 때문이다.
        - 모든 값을 구한 후 - 1 한 값을 return 한다
        - -1을 하는 이유는 전체 의상을 입지 않았을 경우는 제외해야 하기 때문이다.
*/

import java.util.*;

class Solution {
        public int solution(String[][] clothes) {
            Map<String, Integer> map = new HashMap<>();
            for (String[] clothe : clothes) {
                map.put(clothe[1], map.getOrDefault(clothe[1], 0) + 1);
            }

            int answer = 1;

            for (String s : map.keySet()) {
                answer *= map.get(s) + 1;
            }
            return answer - 1;
        }
    }