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

2022년 04월 06일 수요일 - 회식 다음날은 너무 힘들다...

오늘 올려볼 문제는 923번 3Sum With Multiplicity 이라는 문제이다.

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

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

오늘 뇌가 굳은거 가타따..

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 값 1개가 입력으로 들어온다.

---

풀이 및 코드

인덱스 i, j, k 가 i < j < k 를 만족하면서 모두 더한 값이 target이 되는 경우의 수가 몇인지 구하는 문제다.

오늘은 처음부터 정답을 생각해냈다.

각 숫자의 개수를 저장한다.

i, j는 for문을 돌면서 찾고 k는 target에서 i, j를 뺀 값으로 찾는다.

i == j == k 일 때, i == j != k 일 때, j < k 일 때를 나누어서 계산하는 방법으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int threeSumMulti(int[] nums, int target) {
        long[] count = new long[105];
        int mod = 1000000007;
        long result = 0;

        for(int num : nums) count[num]++;

        for(int i = 0; i <= 100; i++)
        {
            for(int j = i; j <= 100; j++)
            {
                int k = target - i - j;
                if(k > 100 || k < 0) continue;

                if(i == j && j == k)
                {
                    result += count[i] * (count[i] - 1) * (count[i] - 2) / 6;
                }
                else if(i == j && j != k)
                {
                    result += count[i] * (count[i] - 1) / 2 * count[k];
                }
                else if(j < k)
                {
                    result += count[i] * count[j] * count[k];
                }
            }
        }

        return (int)(result % mod);
    }
}

---

제출 화면

어제 회식의 여파로 머리가 굳은 거 같아서 꽤 힘들게 문제를 풀었다.

내일은 좀 잘 풀었으면 좋겠다.

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