[LeetCode] 525번 문제를 풀어보았다. (ft. java)

2022년 2월 04일 금요일 - 와 2일 일하고 쉰다!

오늘 올려볼 문제는 525번 Contiguous Array 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

오늘 회사에서 1시간 동안 휴게실에 있는 물품을 날랐다. 힘드러따..

입력

사진에서도 볼 수 있듯이 0과 1 로만 이루어진 int 배열 하나를 입력받는다.

---

풀이 및 코드

0과 1로만 이루어진 배열의 부분배열 중 0과 1의 개수가 같으면서 가장 긴 부분배열의 길이를 구하는 문제이다.

처음에는 포인터 2개를 만들어 배열 양쪽 끝에 하나씩 두어 0과 1중 더 많은 것을 빼는 방법으로 구현하려 했다.

하지만 왜인지 통과하지 못하는 테스트케이스들이 있었다.

그래서 다른 방법을 찾아보았다.

그래서 생각한 방법은 hashmap과 dp라면 dp를 활용하는 것이다.

누적된 합을 저장하는 변수에 0이라면 -1을 1이라면 1을 더한다.

더한 후 hashmap에 이를 키값으로 가지는 값이 있는지 보고 없다면 해쉬맵에 넣는다. (해쉬맵에 들어간 value는 index이고 해당 키값을 가지는 값들 중 가장 왼쪽에 해당하는 index가 들어간다.)

키값으로 가지는 값이 있다면 현재 index와 hashmap에 저장된 index와의 차이를 구하고 max 값과 비교하여 update 한다.

이런식으로 시간복잡도 O(N)에 풀 수 있는 방법을 생각해냈다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int findMaxLength(int[] nums) {
        int max = 0, num = 0;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, -1);

        for(int i = 0; i < nums.length; i++)
        {
            // 0이라면 -1을, 1이라면 1을 더한다.
            num += (nums[i] == 1 ? 1 : -1);

            // num에 해당하는 키 값이 없다면 index를 넣어준다
            if(!map.containsKey(num))
                map.put(num, i);
            // num에 해당하는 키 값이 있다면 hashmap에 저장된 index와 현재 index를 비교하여 max값을 갱신한다.
            else
                max = Math.max(max, i - map.get(num));
        }

        return max;
    }
}

---

제출 화면

오늘은 푸는 데 굉장히 많은 시행착오를 겪은 문제였다.

포기할까 생각도 했지만 그래도 "풀 수 있을 것 같다"라는 생각 덕분에 풀 수 있었던 것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.