hwooo

https://leetcode.com/problems/count-number-of-bad-pairs/풀이힌트 2를 보고 j - i !=  nums[j] - nums[i] 식은 nums[j] - j!= nums[i] - i와 같다는 걸 깨달았다.해서 모든 원소에서 num[i] - i을 계산 후 해당 값을 map에 저장했다. 저장된 값을 순회하며 goodPairs의 개수를 구해 전체 개수에서 빼줬다.C/C++ 코드class Solution {public: long long countBadPairs(vector& nums) { map m; long long len = nums.size(); for (int i = 0; i second; goodPa..

https://leetcode.com/problems/battleships-in-a-board/풀이공간복잡도가 O(1)이고 한 번만 순회하여 답을 구해야 했다.주어진 battleship은 수직 혹은 수평으로만 주어지기에 위에서부터 순회하며 현재 셀에 battleship이 있고, 해당 셀의 위쪽 혹은 왼쪽이 X가 아니라면 즉, 이미 카운팅된 battleship이 아니라면 카운트 해 답을 구했다.C/C++ 코드class Solution {public: int countBattleships(vector>& board) { int row = board.size(); int col = board[0].size(); int cnt = 0; for (int i ..

https://leetcode.com/problems/decode-ways/description/ 풀이재귀로 풀릴 것 같아 도전했으나 답이 나오지 않아 답지를 봤다. 먼저 현재 값이 0이 아니라면 경우의 수 1개를 더한다.만약 현재 값이 1이거나 바로 뒤의 숫자 하나까지 더해 'z'의 값인 26 이하(두 자릿수가 가능한 경우)라면 해당 경의 수를 하나 더 더해주었다.이런 방식으로 뒤에서부터 탐색하며 처음 위치에까지 경우의 수를 구해 총 가짓수를 구했다.C/C++ 코드class Solution {public: int numDecodings(string s) { int len = s.size(); int dp[101] = {0, }; dp[len] = 1; ..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이누적합을 이용하여 풀어야겠다는 생각을 했지만, 2차원 배열에서의 누적합은 어떻게 해야 할지 몰라 다른 분들의 풀이를 참고했다. 위의 그림과 같이 행과 열을 기준으로 누적합을 총 2번 계산한다. 이를 위해서 누적합 배열을 선언할 때 네 모서리에 각각 값을 넣어주어야 한다.N의 데미지를 입는다 가정했을 때,먼저 행을 기준으로 일차원 배열에서와 동일하게 데미지를 입는 시작 부분에 -N, 데미지를 입는 부분 + 1 열에 +N을 더해준다.다음으로는 열..