LeetCode Minimum Penalty for a Shop [JAVA] - 23년 8월 30일

2일 정도 고민을 했는데, 비슷하게 근접은 했으나 정확하게 답을 맞추진 못했다. 정답 참고 후 혼자서 다시 풀어 봤다.

class Solution {
    //닫는 시간에 따라 계산 값이 다르다.
    //닫기 전에는 Y 로,닫는 순간부터는 쭉 N 으로 친다.
    //O(N) 방법으로 탐색하는 방법이 있을 것 같다.
    public int bestClosingTime(String customers) {
        //처음에 한바퀴 돌면서 총 Y가 몇개인지 세어본다
        int count = 0;
        for (int i = 0; i < customers.length(); i++) {
            if (customers.charAt(i) == 'Y') {
                count++;
            }
        }

        //0번째시간에 문을 닫는다면, 총 Y의 개수가 전체 패널티이다.
        //0번째 인덱스를 생각하기 보다는, 0번째 인덱스 앞이 0번째때 문 닫는 시간이라고 생각하면 편하다. (아래와 같이)
        // 0 1 2 3 4
        //  Y Y N Y
        int closingTime = 0;
        int minPenalty = count;
        int penalty = count;

        //처음부터 닫는 시간을 한시간씩 미루면서 최소 값을 찾는다.
        for (int timeIdx = 1; timeIdx <= customers.length(); timeIdx++) {
            if (customers.charAt(timeIdx - 1) == 'Y') {
                penalty--;
            } else {
                penalty++;
            }

            if (minPenalty > penalty) {
                minPenalty = penalty;
                closingTime = timeIdx;
            }
        }

        return closingTime;

    }
}

위의 코드를 조금만 다시 생각해보면, 처음에 굳이 한번 전체 탐색할 필요 없이 0번째 시간을 기준 점수로 잡고, 최고점을 가지는 시간을 return 해도 된다.

class Solution {
    public int bestClosingTime(String customers) {
        int closingTime = 0;
        int maxScore = 0;
        int curScore = 0;

        //처음부터 닫는 시간을 한시간씩 미루면서 최대 값을 찾는다.
        for (int timeIdx = 1; timeIdx <= customers.length(); timeIdx++) {
            if (customers.charAt(timeIdx - 1) == 'Y') {
                curScore++;
            } else {
                curScore--;
            }

            if (maxScore < curScore) {
                maxScore = curScore;
                closingTime = timeIdx;
            }
        }

        return closingTime;

    }
}