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을 더해준다.다음으로는 열..

https://www.acmicpc.net/problem/14719풀이dp 등의 방법으로 풀 수 있을 거라 생각했지만 떠오르지 않아 답을 봤다.현재 위치에서 양옆으로 가장 큰 블럭을 찾고, 현재 위치가 양 옆의 블럭보다 작다면 (양 옆 블럭 중 작은 값 - 현재 블럭)을 고인 빗물 값에 저장하여 출력한다.C/C++ 코드#include #include using namespace std;int main() { int H, W, sum = 0; int blocks[500]; scanf("%d %d", &H, &W); for (int i = 0; i  Java 코드import java.io.BufferedReader;import java.io.IOException;import java.i..

https://leetcode.com/problems/keys-and-rooms/description/풀이0번 방부터 dfs로 탐색하며 방문 가능한 방을 모두 탐색한다. 이 때 방문 여부를 저장해, 미리 방문한 방은 다시 탐색하지 않는다.모든 방을 탐색한 후 탐색하지 않은 방이 있다면 false, 모든 방을 탐색했다면 true를 반환한다.C/C++ 코드class Solution {public: bool visited[1001] = {false, }; void dfs(vector>& rooms, int now) { if (visited[now]) return; visited[now] = true; for (int next : rooms[now]) ..