[ C++ ] 3756. 0이 아닌 숫자들을 연결하고 합계를 곱하기 II

 

이번 주부터 새로운 사이트를 뚫었습니다.

그것은 바로

LeetCode

https://leetcode.com/

LeetCode - The World's Leading Online Programming Learning Platform

 

영어로 풀어야하는 심각한 문제가 있지만..?

 

오늘의 문제를 준다는것이 괜찮아서

이렇게 문제를 하나씩 풀어볼까 한다.

 

장점은 오늘의 문제를 하나씩 푸는 거

그리고 난이도가 나와서 좋고

틀렸을 때 어디가 틀렸는지 테케를 보여주고 고쳐보라고 이야기해 준다.

친절하시네..ㅎㅋ

 

아!

 

이 사이트의 단점..이라면?

 

영어라는 것..

번역해서 풀어야 한다.

 

 

사실 어제도 풀었는데

어제는 풀 수 있었어서 글을 안 썼다.

 

하지만 오늘은

왕 어려워서 가져왔다.

 

함께 풀어보자.

---

 

사실 풀 때는 그냥 substr이랑 해서

stoll 이렇게 다시 바꿔주면 되지 않을까?

했는데 mod를 해줘야 하는 거 때문에 좀 헷갈렸다.

 

그래도 일단 풀어봈다.

 

 처참한 나의 식..

ㅋㅋㅋㅋㅋㅋㅋㅋ답도 안 나온다.

 

인지 씨를 찾았다.

 

인지 씨는 많이도 틀렸다고 하셨다..

..ㅋ

 

일단 mod를 추가해 주고

10의 9승 + 7 

이 친구는 어차피 큰 수에만 적용되니까 모든 식에 다 넣어줘도 문제가 없다.

크다고 넣어줄 필요가 없다는 것

 

 

하지만 중요한 건 이게 아니었다.

더 중요한 건

둘이 곱했는데 이미 큰 수면 어떡할 거냐? 였다.

 

그래서 우리는 예방책을 하나 만들어두어야 한다고 했다.

 

두 번째 for문에서 보면

글자를 한 글자씩 더해주고 있다.

하지만 어느 순간 한 글자씩 더하다가 크기가 커질 수도 있기 때문에!

그런 가능성이 있기 때문에!

마지막에 mod를 한 번만 하는 게 아니라

매번 걸러줘야 한다는 것이다.

 

그래서 

 

이 식이 필요하다.

으잉? * 10 은 뭐예요?
이게 보면 1234를 한 글자씩 계산하는데

2가 들어올 땐 1이 10의 자리가 되어야 해서

10을 곱해주는 것이다.

10 + 2 = 12 그래서 12가 되고?

3이 들어올 때도 마찬가지로 * 10 해줘서

120 + 3 = 123으로 만드는 것이다.

 

오케이

 

 

좋아진 답변..^-^

 

테케도 다통과..^^

 

 

제출해 보니..

 

ㅇㅅㅇ?!?!?

 

 

아니 이왕 될 거 다 되지..

523개 중에 508은 뭐요..!!

 

하고 이유를 봤는데.. s길이가 굉장히 이상하다..

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

이렇게 긴 숫자면 long long 도 택도 없다...ㅋㅋ

 

다시 읽어보니

제약조건이 중요하더라.

 

아니 제약조건도 문젠데..

그냥 잘 안 읽어서 그런 거 같기도 하다.. ㅎㅋ

 

왜냐면..

그럼 처음부터 제대로 된 식을 알려주지 왜.. 이런 걸 알려주냐며 따지려고 인지 씨를 찾으니..

 

마지막줄에 이렇게 적혀있었다....

 

날 시험하다니..

 

 

그래요. 누적합 같이 해봅시다..

 

이 누적합이 뭐냐?!

 

자 

저금통에 돈을 넣습니다

.

1일에 10원

2일에 20원 = 총 30원

3일에 30원 = 총 60원

4일에 40원 = 총 100원

 

2일이랑 3일에 넣은 돈이 얼마지? 하면

20 + 30 = 50원이야!라고 할 수 있지만

내가 2일에 얼마 넣었는지 기억이 안 난다면..? 곤란하겠죠

 

하지만 우리는 2일 이전인 1일까지 넣은 돈 10원이죠?

우린 4일에 있던 돈 60원에

1일에 있던돈 10원을 빼면?

50원으로 2일 3일에 얼마 넣었는지 알 수 있게 됩니다.

 

이 계산법을 누적합이라고 합니다.

이렇게 총가격을 알게 된다면

끝 지점 - 시작하기 직전으로 값을 구할 수 있게 되는 것!!

 

이 문제도 그렇다

 

문자열이 12345라고 해보자.

앞에서 두 자리 누적한 수 12

다섯 자리 누적한 수 12345

 

우리는 345가 필요할 때

12345 - 12 해줘야 하는데?

이러면 값이 이상해지니까

필요한 글자가 3 글자니까 그 글자수만큼 0을 12에 곱해줘서

12345 - 12000 = 345를 구하게 된다.

 

이 방식대로 문제를 풀어야 한다고 한다.

오케이 알겠습니다.

 

---

 

먼저!

이 누적합을 하려면

누적합 배열을 준비해야 한다고 한다.

 

배열..?

배열은 3가지가 필요하며.

문자열 길이 +1 만큼 만들어주라고 했다.

 

필요한 건 

1. 0이 아닌 숫자들의 합 ex) 12345 , 12 

2. 0이 아닌 숫자의 개수 ex) 3자리, 0이 3개 필요함

3. 0이 아닌 숫자를 자릿수 밀어가며 조립한 누적값 ex) 12345 - 12 * 1000

 

아마 3번이 아까 계속 반복했던 mod 같다.

 

그리고 이 문제를 풀려면..

10의 거듭제곱도 미리 알아두어야 한다고 한다...

그 이유는 아까 3번을 생각해 보면

우리는 12 * 10 해줬었기 때문에 인 듯하다.

 

 

아까 했던 그것이다.

그냥 pow(10, i) 하면 안 되나? 했는데

실수형이어서 문제가 생길 수도 있다고 한다.

그래서 이렇게 해줘야 한다고 한다.

 

 

자, 다음엔

배열 만들기

나는 벡터로 만들어주었다.

 

누적 합이기 때문에

전의 합을 가져와서 이번 합과 더해줘야 한다.

그래서 저번 합을 우선적으로 다 가져온 다음

 

새로운 숫자가 들어왔다면

자릿수에 넣어주고 개수도 하나 추가해줘야 한다.

 

그다음에 우리가 아까 엄청 헷갈렸던!

3번!

기존 숫자를 한 칸으로 밀고 새 숫자를 넣어줘야 한다.

 

 

짠!

 

 

자 그다음!

아까 예시에서 말했듯

2일 3일 돈을 알려면

1일의 돈 누적합과 3일의 누적합을 알아야 하기 때문에

처음에 1일의 누적합을 가져와야 한다.

 

 

그래서 우리는 1일을 L 3일을 R로 표시할 예정이다.

이 구간의 합은

수학적 공식으로

R - ( L -1 )이다.

수학적 공식이기 때문에

컴퓨터에 적용하려면? 컴퓨터는 0이기 때문에

1씩 더해줘야 한다.

즉 ( R+1 ) - L이 된다.

 

아 그리고 나

for 이거 쓸 때 변수 뭐 하지 맨날 고민했는데

맨 앞글자 따도 좋을 거 같다.

잊지 말자!

 

 

솔직히 저기 if를 왜 써야 하나? 했는데,

써야 하는 이유가 있다고 한다.

예를 들어

 

pref_x [R + 1] 이 식이 10이고

pref_x [L] * pow10 [cnt] 이 20이면

 

( 10 - 20 )% mod에 의해 음수값이 나온다고 한다.

그 값이 sum에 들어가며 매우 곤란하니까 mod를 더해주어서 음수를 방지한다고 한다.

참 똑똑한 아이디어다.

 

 

class Solution {
public:
    vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
        int n = s.size();
        long long mod = 1000000007;

        vector<long long> pow10(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            pow10[i] = (pow10[i - 1] * 10) % mod;
        }

        vector<long long> pref_sum(n + 1, 0);
        vector<long long> pref_cnt(n + 1, 0);
        vector<long long> pref_x(n + 1, 0);

        for (int i = 0; i < n; i++) {
            pref_sum[i + 1] = pref_sum[i];
            pref_cnt[i + 1] = pref_cnt[i];
            pref_x[i + 1] = pref_x[i];

            if (s[i] != '0') {
                int digit = s[i] - '0';
                pref_sum[i + 1] += digit pref_cnt[i + 1]++;

                pref_x[i + 1] = (pref_x[i] * 10 + digit) % mod;
            }
        }

        vector<int> answer;
        for (auto& q : queries) {
            int L = q[0];
            int R = q[1];

            long long sum = pref_sum[R + 1] - pref_sum[L];
            long long cnt = pref_cnt[R + 1] - pref_cnt[L];
            long long x = (pref_x[R + 1] - pref_x[L] * pow10[cnt]) % mod;

            if (x < 0)
                x += mod;

            long long cur = (sum * x) % mod;
            answer.push_back(cur);
        }
        return answer;
    }
};

 

전체식 남겨둔다.

 

---

 

오늘은 누적합에 대해 공부해 봤다.

 

너무너무너누머누머누너무너무너무너무 어렵다.

이런 문제는 진짜 평생 풀라 해도 못 풀 거 같다.

 

..

왜 이리 나에게 이런 시련을

나에게는 easy만달라고요..

쉬운 거만 달라고요!!!!!!!!!!

엄청 어려웠지만 굉장히 뿌듯하다.

누적합...

괴롭지만 다음에 본다면

조금은 더 잘 풀 수 있을 것 같다.

 

고생했다, 나 자신

 

이 사이트 몇 번 더 써보고

이렇게 하드인데 중간이라고 거짓말하면

휙 도망가버려야지 크ㅡㅋ킄