๋ฌธ์ ๋งํฌ
Minimum Deletions to Make Character Frequencies Unique - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
aaaabbbccd ์ฒ๋ผ ํ ๋ฌธ์๊ฐ n๊ฐ ์์ผ๋ฉด ๋ค๋ฅธ ๋ฌธ์๋ n๊ฐ๊ฐ ์์ผ๋ฉด ์๋๋ค๋ ๊ท์น์ ๋ง์กฑ์ํค๋๋ก ์ฃผ์ด์ง ๋ฌธ์ s๋ฅผ ํธ๋ค๋ง ํ๋ ๋ฌธ์ ์ด๋ค.
s์ ๊ฐ์ ๊ฐฏ์์ ๋ฌธ์๊ฐ ์กด์ฌํ์ง ์๋๋ก ํ๊ธฐ ์ํด ์ง์์ผํ ๋ฌธ์์ ๊ฐ์๋ฅผ ๊ตฌํด๋ผ.
์ ๊ทผ ๋ฐฉ๋ฒ
๋จผ์ ์ฃผ์ด์ง ๋ฌธ์์ด s์ ๊ฐ ๋ฌธ์๋ณ ๊ฐ์๋ฅผ ๊ตฌํด์ ์๋ก์ด ๋ฐฐ์ด์ ๋ฃ๋๋ค.
// sArr : ๋ฌธ์์ด์ ๋ฐฐ์ด๋ก ๋ณํํ์ฌ ์ ๋ ฌํ ๋ฐฐ์ด // cntArr : ๋ฌธ์๋ณ ๊ฐฏ์๋ฅผ ๋ด์ ๋ฐฐ์ด for(let i = 1; i < sArr.length; i++){ if(sArr[i-1] === sArr[i]) sameWordCnt++; else{ cntArr.push(sameWordCnt); sameWordCnt = 1; } } cntArr.push(sameWordCnt)โ
๋ค์์ผ๋ก ๋ฌธ์์ ์๋ฅผ ๋ด์ ๋ฐฐ์ด cntArr์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๋ค.
cntArr.sort((a,b) => b - a)โ
๋ง์ง๋ง์ผ๋ก ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๋ฐฐ์ด์ ์ํํ๋ฉฐ ์ด์ ๊ฐ๊ณผ ๋ค์ ๊ฐ์ ๋น๊ตํ์ฌ ๋ต์ ๊ตฌํ๋ค.
(๋ง์ฝ [1, 3] ์ด๋ผ๋ฉด cntArr[0] <= cntArr[1] ์ด๋ฏ๋ก cntArr[0] <= cntArr[1]์ด ๋ง์กฑํ์ง ์์๋๊น์ง cntArr[1]์ ๋บ๋ค.)
([2,2,2,2] ๊ฐ์ ๋ฐฐ์ด์ด ์จ๋ค๋ฉด [2,1,0,-1]์ด๋ ๊ฐ์ด ๋์ฌ ์ ์์ผ๋ฏ๋ก cntArr[i] !== 0์ผ ๊ฒฝ์ฐ๋ง ๊ตฌํ๋ค.)
for(let i = 1; i < cntArr.length; i++){ while(cntArr[i-1] <= cntArr[i] && cntArr[i] !== 0){ cntArr[i] -= 1; output++; } }โ
/**
* @param {string} s
* @return {number}
*/
var minDeletions = function(s) {
let sArr = s.split("").sort();
let sameWordCnt = 1;
let cntArr = [];
let output = 0;
for(let i = 1; i < sArr.length; i++){
if(sArr[i-1] === sArr[i]) sameWordCnt++;
else{
cntArr.push(sameWordCnt);
sameWordCnt = 1;
}
}
cntArr.push(sameWordCnt)
cntArr.sort((a,b) => b - a)
for(let i = 1; i < cntArr.length; i++){
while(cntArr[i-1] <= cntArr[i] && cntArr[i] !== 0){
cntArr[i] -= 1;
output++;
}
}
return output;
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] Maximum Bags With Full Capacity Of Rocks (0) | 2022.07.02 |
---|---|
[LeetCode] Maximum Units On A Truck (0) | 2022.07.01 |
[LeetCode]Maximum Points You Can Obtain From Cards (0) | 2022.06.26 |
[LeetCode] Non-decreasing Array (0) | 2022.06.25 |
[LeetCode] Valid Parentheses (0) | 2022.06.24 |