Week01 TEST

☑️ To-do

• Week01 테스트 복기
• 자바 코딩테스트 대비 스터디 진행
  • 숫자 블록
  • 주차 요금 계산
• Week02 문제 풀이
  • 10828 / 10773 / 9012 / 17608 / 18258 / 2164

 

 

 

---

Week01 TEST

<시간 분배>

• 문제 1 : 10분
  • 단순한 완전 탐색 문제.
  • 입력으로 주어진 숫자의 나머지 연산과 몫 연산을 반복적으로 수행.

 

• 문제 2 : 10분
  • 모든 경우의 수를 고려해야하는 완전 탐색 문제.
  • combinations 모듈을 사용해서 모든 조합의 경우 도출

 

• 문제 3 : 10분
  • dp 로 접근.
  • 입력 데이터의 개수가 12밖에 되지 않아, 애초에 dp 테이블 전체를 만들어주는 방향으로 구현

 

🙁 Worst : 문제 자체를 꼼꼼히 안읽어서 조건을 캐치하지 못한 경우가 있었다.
-> 난이도에 비해 시간을 많이 소요함

 

 

---

Java-Algorithm 01

🧾 Our study rules

- 2문제 라이브 코딩 진행
- 문제당 30분
- 플랫폼 : 프로그래머스
- 유형 및 문제 확정 : 당일 날
- 시간 : 목요일 저녁 이후

우선 4주 진행하고 그 다음은 문제 풀이 체킹 또는 계속 진행할 지 추후 확정!

 

 

 

1. 숫자 블록 (⭐️ Retry)

• https://school.programmers.co.kr/learn/courses/30/lessons/12923
• 문제 풀이 소요 시간 : 40분

 

🏃‍♂️ Try 1

class Solution {
    public long[] solution(long begin, long end) {
        long[] answer = new long[(int)(end - begin + 1)];

        for (int i = 1; i < answer.length; i++) {
            answer[i] = 1;
        }

        for (long i = 2; i < end + 1; i++) {
            for (long j = begin; j < end + 1; j++) {
                if (j / i != 1 && j % i == 0) {
                    answer[(int)(j - begin)] = i;
                }
            }
        }

        return answer;
    }
}

• 정확성 : tc 08 ❌
• 효율성 : all ❌

 

• 문제 조건

- begin, end 는 1 이상 1,000,000,000이하의 자연수 이고, begin는 항상 end보다 작습니다.
- end - begin 의 값은 항상 10,000을 넘지 않습니다.

 

• 접근 방법
  • 반복문 시작 숫자를 2부터 시작해서 end값 이하까지 돌리면서 배열내에 숫자를 채워주는 방식으로 구현
  • 그리고 문제에서 제시된 조건에서 배열의 범위가 10,000으로 한정되어 있으므로 answer 배열의 크기를 end - begin으로 제한함

 

• 놓친 부분
  • 문제에서 제시된 예시 테스트 케이스의 첫 원소 값이 무조건 0이므로 무조건 0이 들어가게끔 해줬다.
    -> begin = 1 일 때만 가능한 결과.
  • 문제 조건 : "그렙시는 길이가 1,000,000,000인 도로에 1번 블록부터 시작하여 10,000,000번 블록까지 위의 규칙으로 모두 놓았습니다."
    -> 만약 end가 10,000,000 이상이라면 end를 임의로 10,000,000 로 제한함

 

🏃‍♂️ Try 2

class Solution {
        public long[] solution(long begin, long end) {
        long[] answer = new long[(int)(end - begin + 1)];

        if (end > 10000000) end = 10000000;
        for (long i = begin; i < end + 1; i++) {
            long flag = 1;
            for (long j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    flag = i / j;
                    break;
                }
            }
            answer[(int) (i - begin)] = flag;
        }
        if (begin == 1) answer[0] = 0;

        return answer;
    }

}

 

• 숫자 범위가 한 없이 크므로 모든 int 를 long 으로 바꿔줌
• 원소 삽입 규칙 : 자신을 제외한 최대 약수를 삽입해준다.
  • 이때, 시간 복잡도를 줄이기 위해 제곱근까지만 반복문을 돌렸다.
  • 제곱근까지만 할 경우 중복 연산을 줄일 수 있다.
  • Ex 4. (1, 4), (2, 2), (4, 1) : 여기서 결국 (1, 4) 와 (4, 1) 은 동일하기 때문

 

💬 효율성 테스트 케이스의 최대 실행 속도가 0.07ms 인데도 실패가 뜬다.
    -> 어마어마하게 극악인 듯

 

 

---

2. 주차 요금 계산

• https://school.programmers.co.kr/learn/courses/30/lessons/92341
• 문제 풀이 소요 시간 : 20분

 

🏃‍♂️ Try 1

• tc ❌
• 입차 부분, String -> Integer 시간 변환 부분은 구현 완료
• But, 당일 출차되지 않은 차 확인 및 지불해야하는 주차 요금 구하는 로직 구현 실패

 

🎉 Success

import java.util.*;

// fees = {기본 시간, 기본 요금, 단위 시간, 단위 요금}
// 입차 o 출차 x 일 때는 "23:59" 출차 적용

class Solution {
    public ArrayList<Integer> solution(int[] fees, String[] records) {
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer,Integer> inTime = new HashMap<>(); // 입차 arr
        HashMap<Integer,Integer> outTime = new HashMap<>(); // 전체 이용 시간 arr

        for (int i = 0; i < records.length; i++) {
            String r[] = records[i].split(" ");
            String time = r[0];
            Integer carNum = Integer.parseInt(r[1]);;
            String inOut = r[2];

            if (inOut.equals("IN")) { // 입차 처리
                inTime.put(carNum, parseTime(time));
            } else { // 출차 처리
                if (!outTime.containsKey(carNum)) { // 첫 출차
                    outTime.put(carNum, parseTime(time) - inTime.get(carNum));
                } else {
                    outTime.put(carNum, outTime.get(carNum) + (parseTime(time) - inTime.get(carNum)));
                }
                inTime.remove(carNum); // 당일 출차했으면 입차 차량 배열에서 제거
            }
        }

          // 당일 출차 못한 차량에 일괄적으로 "23:59" 출차 적용
        Object[] iKeys = inTime.keySet().toArray();
        Integer[] inTimeKeys = Arrays.copyOf(iKeys, iKeys.length, Integer[].class);

        for (int i = 0; i < inTimeKeys.length; i++){
            if (!outTime.containsKey(inTimeKeys[i])) {
                outTime.put(inTimeKeys[i], parseTime("23:59") - inTime.get(inTimeKeys[i]));
            } else {
                outTime.put(inTimeKeys[i], outTime.get(inTimeKeys[i]) + (parseTime("23:59") - inTime.get(inTimeKeys[i])));
            }
        }

        // 주차 요금 적용
        Object[] oKeys = outTime.keySet().toArray();
        Integer[] outTimeKeys = Arrays.copyOf(oKeys, oKeys.length, Integer[].class);

        Arrays.sort(outTimeKeys);

        for (int i = 0; i < outTimeKeys.length; i++){
            int totalTime = outTime.get(outTimeKeys[i]);
            if (totalTime > fees[0]) {
                int div = (totalTime - fees[0]) / fees[2];
                if ((totalTime - fees[0]) % fees[2] > 0) {
                    div += 1;
                }
                answer.add(fees[1] + fees[3] * div);
            } else {
                answer.add(fees[1]);
            }
        }

        return answer;
    }

    // 시를 분으로 변환하기 (String -> Integer)
    int parseTime(String time) {
        String[] t = time.split(":");
        int rst = Integer.parseInt(t[1]);
        rst += Integer.parseInt(t[0]) * 60;
        return rst;
    }

}

• inTime (HashMap) : 차량 입차시 (차 번호 : 입차 시간) 삽입
• outTime (HashMap) : 차량 출차시, (차 번호 : 출차 - 입차 시간) 삽입
• 당일 출차 못한 차량에 대해 inTime 에서 키값을 뽑아와, 일괄적으로 "23:59" 출차 적용해줌

 

💡hashMap에서 key값들을 뽑아올 때의 기본적인 리턴 값이 Object타입이므로 이를 다시 Integer로 바꿔주는 과정을 수행한다.
-> hashMap에서 value를 뽑아올 때의 key값 타입이 Integer 이기 때문.

Object[] iKeys = inTime.keySet().toArray();
Integer[] inTimeKeys = Arrays.copyOf(iKeys, iKeys.length, Integer[].class);

 

 

---

🔗 Reference

• How to convert object array to string array in Java - Stack Overflow
• (https://stackoverflow.com/questions/1018750/how-to-convert-object-array-to-string-array-in-java)