[99클럽 코테 스터디] 3일차

오늘의 학습 키워드

• 구현
• 이분탐색

문제 - 비기너

크기가 작은 부분 문자열

풀이

class Solution {
    public int solution(String s) {
        int answer = 0;

        String[] strArr = s.split("");

        int idx = 0;
        while(idx < s.length()) {
            String x = strArr[idx];
            int count1 = 0;
            int count2 = 0;

            for(int i = idx; i < strArr.length; i++) {
                if(strArr[i].equals(x)) count1++;
                else count2++;
                idx++;

                if(count1 == count2) {
                    answer++;
                    break;
                }

                // 남아 있는 배열 처리
                if(count1 != count2 && i == strArr.length - 1) {
                    answer++;
                }
            }
        }

        return answer;
    }
}

• 주어진 문제를 따라 그대로 구현했습니다.

문제 - 미들러

경로 찾기

풀이

import java.util.*;

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

        Arrays.sort(times);

        long left = 0;                                    // 가장 적게 걸리는 경우
        long right = (long) times[times.length - 1] * n;  // 가장 오래 걸리는 경우

        while (left <= right) {
            long mid = (left + right) / 2;
            long tmp = 0;

            for (int time : times) {
                tmp += mid / time;  // 각 심사관이 주어진 mid 시간 내에 처리할 수 있는 사람 수를 합산
            }

            if (tmp >= n) {
                answer = mid;     
                right = mid - 1;  
            } else {
                left = mid + 1;
            }
        }

        return answer;
    }
}

• 제한 사항의 숫자가 10자리가 넘었기 때문에 탐색의 범위를 좁혀야겠다고 생각했습니다.
• 처음 풀이 때, 테스트 케이스를 통과해서 답을 제출했지만, 시간 초과의 테스트 케이스가 있었습니다.
• 탐색 범위를 더 좁혀주어야겠다고 생각했지만, 탐색의 범위를 좁히는 코드를 구현하기 어려웠습니다.