프로그래머스 알고리즘 문제 풀이 - 카카오 2022 - 1,2,3번 문제풀이

zio도미닉·2022년 1월 29일
0
post-thumbnail

1. 신고 결과 받기

배운점

  • Map에 value ArrayList or HashSet을 넣는 방법
HashMap<String, HashSet<String>>hashmap=new HashMap<>();
for (int i=0;i<arr.length;i++) {
    String key=arr[0];
    String value=arr[1];
    HashSet<String>tempSet=new HashSet<>();
    if (hashmap.containsKey(key)) {
    	tempSet=hashmap.get(key);
        tempSet.add(value);
    }else {
    	tempSet.add(value);
    }
    hashmap.put(key,tempSet);
}

코드 설명

  • 어려웠던 점 -> 동일 유저가 신고했을때 1명으로 처리 ex) mary -> frod, mary ->frod신고했으면 mary ->frod (1)임
  • 이 부분은 동일 신고 유저를 없애기 위해 value를 HashSet으로 설정하였음
    그리고 이 hashMap에서 정지당한 유저 (stop_map)을 뽑음 -> map이기 때문에 신고한 동일 유저가 나오지 않는 점을 이용

코드

package programmers.kakao2022;

import java.util.*;
// 어려웠던 점 -> 동일 유저가 신고했을때 1명으로 처리 ex) mary -> frod, mary ->frod신고했으면 mary ->frod (1)임
// 이 부분은 동일 신고 유저를 없애기 위해 value를 HashSet으로 설정하였음
// 그리고 이 hashMap에서 정지당한 유저 (stop_map)을 뽑음 -> map이기 때문에 신고한 동일 유저가 나오지 않는 점을 이용
public class 신고결과받기 {

    public int[] solution(String[] id_list, String[] report, int k) {

        HashMap<String, HashSet<String>> hashmap=new HashMap<>();
        for (int i=0;i<report.length;i++) {

            String key=report[i].split(" ")[0];
            String value=report[i].split(" ")[1];

            HashSet<String>hashset=new HashSet<>();
            if (hashmap.containsKey(key)) {
                hashset=hashmap.get(key);
                hashset.add(value);
            }
            else {
                hashset.add(value);
            }
            hashmap.put(key,hashset);
        }

        // 신고당한 map -> value가 k번이상이면 정지
        // hashmap에서 신고당한 유저 리스트 뽑기
        HashMap<String, Integer> stop_map=new HashMap<>();
        for (String str:hashmap.keySet()) {
            String key=str;
            HashSet<String>hashset =hashmap.get(key);
            for (String hash:hashset) {
                stop_map.put(hash,stop_map.getOrDefault(hash,0)+1);
            }

        }
        // id_list의 값을 확인 -> hashmap에서의 value 확인 -> stop_map을 뒤짐 -
        int[] answer = new int[id_list.length];

        for (int i=0;i<id_list.length;i++) {
            String key=id_list[i];
            int value=0;
            if (hashmap.containsKey(key)) {
                HashSet<String> hashset=hashmap.get(key);
                for (String str:hashset) {
                    int v=stop_map.get(str);
                    if (v>=k) value++;
                }
            }

            answer[i]=value;
        }

        return answer;
    }
}

2. k진수에서 소수 개수 구하기

알게 된점

  • 10진법에서 k진법으로 변환
        // k진법으로 변환
        StringBuilder sb=new StringBuilder();
        while (n/k!=0) {
            int div=n%k;
            n=n/k;
            // System.out.println("div:"+div+"n:"+n);
            sb.append(div);
            
            // 마지막꺼 꼭 넣어주기
            if (n/k==0) {
                sb.append(n);
            }
        }
        // 넣어주고 반대로 저장했기 때문에 reverse 해주기
        sb.reverse();
  • k진법에서 10진법으로 변환 (이건 사용하지 않음) Integer.parseInt("str",k)를 이용
	2진수 -> 10진수 int : Integer.parseInt("1000",k);

1. 런타임 발생 에러 (1,11번 케이스)

  • 이유는 value를 변경하였을때 제한된 int를 넘어서기 때문에 런타임 에러 발생
  • 따라서 Long temp=Long.parseLong(value); 로 변경 필요

2. 1번케이스 시간초과 발생

  • 이유는 엄청 긴 수일 경우 제곱근까지만 하면되는데 끝까지 검색을 하기 때문에 시간 초과 발생
  • 제곱근 범위까지만 검사 (이때 주의할점은 i가 =limit일때임)
  • int limit=(int) Math.sqrt(temp);
    for (int i=2;i<=limit;i++)
import java.util.*;
class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        
        // int k=211020101011;
        // String ss="211020101011";
        // String str[]=ss.split("0");
        // System.out.println(Arrays.toString(str));
        
        // k진법으로 변환
        StringBuilder sb=new StringBuilder();
        while (n/k!=0) {
            int div=n%k;
            n=n/k;
            // System.out.println("div:"+div+"n:"+n);
            sb.append(div);
            
            // 마지막꺼 꼭 넣어주기
            if (n/k==0) {
                sb.append(n);
            }
        }
        // 넣어주고 반대로 저장했기 때문에 reverse 해주기
        sb.reverse();
        String temp[]=sb.toString().split("0"); //0을 기준으로 나누기
        // System.out.println(Arrays.toString(temp));
        
        // 소수인지 찾기
        // String sr="00010";
        // System.out.println(isPrime(sr,2));
        for (String str:temp) {
            if (!str.equals("")) { // 중간에 ""가 나올수 있기 때문에 ""는 제거하기
                if (isPrime(str)) answer++;
            }
        }
        
        return answer;
    }
    
    
    public boolean isPrime(String value) {
        // k 진법 -> 10 진법으로 변경하기
        // int temp=Integer.parseInt(value); 
        Long temp=Long.parseLong(value);
        // System.out.println("temp:"+temp);
        boolean check=true;
        if (temp<2) return false;
        // 2부터 자기 자신 전까지 나누었을때 나누어떨어지면 소수가 아님, 
        // temp의 범위를 제곱근까지만 설정
        // int limit = (int) Math.sqrt(temp);
        for (int i=2;i<temp;i++) {
            if (temp%i==0) return false;
        }
        
        return true;
    }
}

3. 주차 요금 계산

배운 점

  • map의 key를 기준으로 정렬
  • 소수점을 구할때는 분모를 double로 나눈다.
    - 10/4 -> 2.5를 원함, 하지만 4가 나옴
    - 10/(double)4로 해줘야 함.

풀이

  1. 차량번호를 기준으로 입차와 출차 기록을 한다.
    • hashmap
  2. 구한 map에서 만약 입차기록이 출차 기록보다 많다면 마지막 출차기록(23:59)을 추가하고 출차-입차로 구한 값을 map에 기록한다.
    • resultmap
  3. 주어진 계산 식대로 구한다.
    • resmap

package programmers.kakao2022;

import java.util.*;

public class 주차요금계산 {
    public int[] solution(int[] fees, String[] records) {

        HashMap<String, ArrayList<String>> hashmap = new HashMap<>();

        for (String record : records) {
            String time = record.split(" ")[0];
            String number = record.split(" ")[1];
            String state = record.split(" ")[2];
            int num = changeTime(time);
            boolean check = true;

            ArrayList<String> templist = new ArrayList<>();
            String temp = state + "-" + time;

            if (hashmap.containsKey(number)) {
                templist = hashmap.get(number);
                templist.add(temp);
            } else {
                templist.add(temp);
            }
            hashmap.put(number, templist);
        }

        // System.out.println(hashmap.toString());

        HashMap<String, Integer> resultmap = new HashMap<>();
        for (String key : hashmap.keySet()) {
            // int value=hashmap.get(key);
            ArrayList<String> arrlist = hashmap.get(key);
            ArrayList<Integer> inlist = new ArrayList<>();
            ArrayList<Integer> outlist = new ArrayList<>();

            for (String str : arrlist) {
                String strArr = str.split("-")[1];
                if (str.startsWith("IN")) {
                    inlist.add(changeTime(strArr));
                } else {
                    outlist.add(changeTime(strArr));
                }
            }
            // inlist가 더 많다면 outlist에 출차 추가하기
            if (inlist.size() > outlist.size()) {
                outlist.add(changeTime("23:59"));
            }

            int value = 0;
            for (int i = 0; i < inlist.size(); i++) {
                value += outlist.get(i) - inlist.get(i); //출차-입차하고 값 누적하기
            }
            resultmap.put(key, value); // 누적된 값 map에 기록
        }
        // System.out.println(resultmap.toString());
        HashMap<Integer, Integer> resmap = new HashMap<>();
        int[] answer = new int[resultmap.size()];
        for (String key : resultmap.keySet()) {
            int value = resultmap.get(key);
            int money = fees[1];
            if (value > fees[0]) {
                // int temp=(int) Math.ceil((value-fees[0])/fees[2]); // 소수점 안나옴 -> double로 나눠야 함
                int temp = (int) Math.ceil((value - fees[0]) / (double) fees[2]);
                // double temp=(value-fees[0])/(double)fees[2];
                // System.out.println("temp"+temp);
                money += (temp * fees[3]);
                // System.out.println("money"+money);
            }
            resmap.put(Integer.parseInt(key), money);
        }
        // 차량번호 기준으로 정렬 -> map의 key를 기준으로 정렬
        ArrayList<Integer> arraylist = new ArrayList<>(resmap.keySet()); // key를 list에 다 넣는다.!
        Collections.sort(arraylist, (o1, o2) -> (o1.compareTo(o2)));
        // System.out.println(arraylist.toString());
        for (int i = 0; i < arraylist.size(); i++) {
            answer[i] = resmap.get(arraylist.get(i));
        }


        return answer;
    }

    // 시간을 분으로 변경
    public int changeTime(String value) {
        String hour = value.split(":")[0];
        String min = value.split(":")[1];

        int res = Integer.parseInt(hour) * 60 + Integer.parseInt(min);
        return res;
    }

}
profile
BackEnd Developer

0개의 댓글