[LeetCode - 1375] Number of Times Binary String Is Prefix-Aligned - Java

문제 설명

 

Number of Times Binary String Is Prefix-Aligned - LeetCode

 

접근 방법

나의 접근 방법

flips 배열 크기의 boolean형 배열을 생성 후 flips 값 순서대로 해당 배열의 인덱스에 true를 할당해주었습니다. 이후 배열의 인덱스가 1부터 현재 단계의 수(n'th step)까지 모두 true일 경우 결과값에 1을 더해주도록 했습니다. 하지만, 이 경우 flips 값과 상관없이 항상 2중 for문을 돌아 비효율적인 문제가 있었습니다.

 

모범적인 접근 방법

별도 배열 생성 없이, 현재까지 순회된 flips 배열 요소들의 값 중 가장 큰 값을 기준으로 현재 단계 수(n'th step)의 값과 일치하는지를 검증하도록 합니다. 이때 현재 단계 수의 값이 현재까지 순회된 flips 배열 요소들의 값 중 가장 큰 값과 일치한다는 것은 그 이전에 비트 값들이 모두 flip 됐다는 것을 의미합니다.

 

 

소스 코드

나의 소스 코드

class Solution {

    public int numTimesAllBlue(int[] flips) {
        int countOfPrefixAligned = 0;

        boolean[] binaryString = new boolean[flips.length + 1];

        int index = 0;
        Loop : for (int flip : flips) {
            index++;
            binaryString[flip] = true;

            for (int j = 1; j <= index; j++) {
                if (!binaryString[j]) {
                    continue Loop;
                }
            }

            countOfPrefixAligned++;
        }


        return countOfPrefixAligned;
    }
}

 

모범 소스 코드

class Solution {

    public int numTimesAllBlue(int[] flips) {
        int max = 0, cnt = 0;
        
        for(int i = 0; i < flips.length; i++) {
            max = Math.max(max, flips[i]);
            if (max == i + 1) cnt++;
        }
        
        return cnt;
    }
}

 

참고자료

• https://leetcode.com/problems/number-of-times-binary-string-is-prefix-aligned/