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

2022년 03월 21일 월요일 - 아니 왜 아직도 월요일???

오늘 올려볼 문제는 763번 Partition Labels 이라는 문제이다.

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

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

오늘 문제 좀 어려워쓰

입력

사진에서도 볼 수 있듯이 String 하나가 입력으로 들어온다.

---

풀이 및 코드

주어진 String을 최대한 많은 Partition으로 나누는데 한 Partition에 포함된 원소들이 다른 Partition에는 존재하면 안된다고 할 때 Partition들의 크기를 담은 List를 리턴하는 문제다.

오늘은 시행착오를 겪다가 문제를 풀었다.

Stack을 사용할까 했는데 그냥 for문 한 번 더 도는 방식으로 구현하기로 했다.

dp라는 배열에는 list넣을 index를 저장하고 있게끔 했다.

주어진 String을 읽으면서 중복된 원소가 나오면 중복된 원소부터 이번 원소까지 중복된 원소가 가지고 있는 index로 모두 바꾸어주고 중복된 원소의 위치를 현재 원소로 바꾸어주었다.

후에 dp를 순회하면서 list에 size를 넣어주는 방식으로 구현했다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public List<Integer> partitionLabels(String input) {
        HashMap<Character, Integer> map = new HashMap<>();
        int[] dp = new int[input.length()];
        int index = 0;

        for(int i = 0; i < input.length(); i++)
        {
            char now = input.charAt(i);

            if(map.containsKey(now))
            {
                for(int j = map.get(now) + 1; j <= i; j++)
                {
                    dp[j] = dp[map.get(now)];
                }
                map.put(now, i);
            }
            else
            {
                dp[i] = index++;
                map.put(now, i);
            }
        }

        List<Integer> result = new ArrayList<>();
        int pre = 0;
        for(int i = 0; i < input.length(); i++)
        {
            if(dp[pre] != dp[i])
            {
                result.add(i - pre);
                pre = i;
            }
        }
        result.add(input.length() - pre);

        return result;
    }
}

---

제출 화면

생각보다 어려웠는데 그래도 풀어서 다행인 것 같다.

내일 문제도 적당히 어려우면서 재밌었으면 좋겠다.

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