๋ฌธ์ ๋งํฌ
Candy - 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
๋ชจ๋ ์์ด์๊ฒ ์ฌํ์ ๋๋ ์ค ์ ์๋ ์ฌํ์ ์ต์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์
ratings : ์์๋ฐฐ์ด
์กฐ๊ฑด 1. ๋ชจ๋ ์์ด๋ ์ต์ 1๊ฐ์ ์ฌํ์ ๋ฐ์์ผํ๋ค.
์กฐ๊ฑด 2. ์ด์ํ ์์ด๋ค๋ผ๋ฆฌ๋ ๋ ๋์ rating์ ๊ฐ๋ ์์ด๊ฐ ๋ ๋ง์ ์บ๋๋ฅผ ๋ฐ์ ์ ์๋ค.
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์๋ left, right ๋ณ์๋ฅผ ๋ง๋ค์ด sliding window ๋ฐฉ์์ผ๋ก ์ ๊ทผํ์๋ค.
ํ์ง๋ง ratings = [3, 2, 1, 2, 3] ๊ฐ์ ๋ถ๋ถ์์ left์ right์ ์ด๋ ์กฐ๊ฑด์ ๋ง์กฑ์ํค๋ ค๋ฉด ์กฐ๊ฑด์ด ๋๋ฌด ๋ณต์กํด์ก๊ณ
์์ ํ์์ ์์์๋ถํฐ 1๋ฒ, ๋ค์์๋ถํฐ 1๋ฒ ์งํํ๋ ๋ฐฉ์์ผ๋ก ๋ฐ๊พธ์๋ค.
1. ratings ๊ธธ์ด์ ๋ฐฐ์ด์ ๋ง๋ค์ด ๋ชจ๋ ๊ฐ์ 1๋ก ์ฑ์ด๋ค.
let candyArr = new Array(ratings.length).fill(1);โ
2. ratings๋ฅผ ์์์๋ถํฐ ratings[i -1] < ratings[i] ์ผ ๊ฒฝ์ฐ๋ฅผ ์ฒ๋ฆฌํ๋ค.
( ratings = [5, 3, 1, 2, 3] => candyArr = [1, 1, 1, 2, 3] )
for(let i = 1; i < ratings.length; i++){ if(ratings[i-1] < ratings[i]) candyArr[i] = candyArr[i-1] + 1; }โ
3. ratings๋ฅผ ๋ค์์๋ถํฐ ratings[i] > ratings[i + 1] ์ผ ๊ฒฝ์ฐ๋ฅผ ์ฒ๋ฆฌํ๋ค.
( ratings = [5, 3, 1, 2, 3] => candyArr = [1, 1, 1, 2, 3] => candyArr = [3, 2, 1, 2, 3] )
for(let i = ratings.length - 2; i >= 0; i--){ if(ratings[i] > ratings[i+1]){ candyArr[i] = Math.max(candyArr[i], candyArr[i+1] + 1) } }โ
/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
let output = 0;
let candyArr = new Array(ratings.length).fill(1);
for(let i = 1; i < ratings.length; i++){
if(ratings[i-1] < ratings[i]) candyArr[i] = candyArr[i-1] + 1;
}
for(let i = ratings.length - 2; i >= 0; i--){
if(ratings[i] > ratings[i+1]){
candyArr[i] = Math.max(candyArr[i], candyArr[i+1] + 1)
}
}
output = candyArr.reduce((acc, cur) => acc + cur)
return output
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] Fibonacci Number (0) | 2022.07.06 |
---|---|
[LeetCode] Longest Consecutive Sequence (0) | 2022.07.05 |
[LeetCode] Maximum Area Of A Piece Of Cake After Horizontal And Vertical Cuts (0) | 2022.07.02 |
[LeetCode] Maximum Bags With Full Capacity Of Rocks (0) | 2022.07.02 |
[LeetCode] Maximum Units On A Truck (0) | 2022.07.01 |