문제https://leetcode.com/problems/count-number-of-bad-pairs/description/  풀이문제는 i 일 때 j - i != nums[j] - nums[i]. 인 쌍을 몇 개 찾느냐인데 이 문제는 반대로 생각해야 쉽게 풀린다.  우선 위 식을 "정리" 해볼 수 있는데, 정리하면 nums[j] - j != nums[i] - i 형태로 만들 수 있다. 이제 반대로 생각해보자. 총 쌍의 개수에서 우리는 위 조건에 부합하지 않는 쌍을 찾으면 답을 구할 수 있다.위 조건의 반대는?  j > i 일 때  nums[j] - j == nums[i] - i 이다. 이 말을 풀어보면 내가 j일 때 나보다 작은 값 i 가 있을때 nums[j] - j == nums[i] - i 를 ..

문제https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&envId=top-interview-150  풀이set 의 형태에서, random 값을 뽑아낼 수 있는 자료구조를 만드는 문제이다. 우선 insert 와 remove 를 O(1)에 할려면 set이나 map과 같은 자료구조는 필수적으로 필요하다. 그리고  random 값을 O(1)로 뽑아내기 위해서는 리스트나 배열이 필수적이다. 해당 배열의 사이즈를 활용해서 랜덤 인덱스를 뽑고, 그 값에 한 번에 접근할 수 있으니 말이다. 난 map 과 배열의 조합으로 문제를 해결했다.  우선 배열의 끝을 가리키는 lastIdx 를 선언하고, 이를 -1로 초기화 한다. 다음은 ..

문제https://www.acmicpc.net/problem/2638 풀이단순한 BFS 문제이다. 문제의 조건에 보면 가장자리에는 치즈가 항상 없다고 표시된다.BFS를 "치즈가 없는 가장자리" 에서 시작하면 치즈안의 빈 공간은 탐색을 안하면서, 겉에 있는 치즈를 카운트 할 수 있다. 그렇게 바깥쪽에서 탐색을 하다가 이동시에 치즈이면 해당하는 치즈 방문 카운트를 증가시켜준다. 그렇게 BFS 탐색이 한 번 끝나면, 각 치즈의 방문 카운트를 체크해서 2 이상이면 지워주면 된다. 이 과정을 치즈가 모두 없어질때까지 수행하면 해결! 코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;// 2변 이상에 닿은 치즈 ->..

문제https://www.acmicpc.net/problem/1238 풀이다익스트라 문제이다. 단순히 n개 각각 마을에서 x 마을로의 최단 거리를 다익스트라로 구하고,그리고 x 마을에서 n개의 마을로의 최단거리를 다익스트라로 구해도 풀리긴한다. x마을에서 n개 마을로의 거리는 한번만에 다 구할 수 있으나,n개의 마을에서 x 최단거리를 구하기 위해서는 n + 1 번의 다익스트라를 돌아야하기에 굉장히 비효율적이다. 해결법은 간선의 방향을 반대로 하고 다익스트라를 수행하면 n 개의 마을에서 x 로 가는 가중치를 한번에 구할 수 있다.n개 각각 마을에서 x로 향하는 길들을 반대로 설정하고 x에서의 다익스트라를 수행하면,그건 각 마을에서 x로 향하는 최단거리가 된다. 이렇게 하면 단 두번의 다익스트라로 문제를 풀..

문제https://www.acmicpc.net/problem/1516  풀이 위상정렬을 활용해 풀어야 하는 문제이다. 처음엔 위상정렬 문제인지 모르고 막 풀었다가.. 호되게 당했다. 사실 위상정렬을 공부하고 나면, 선후관계가 있는 이 문제를 어떻게 풀어야하는지 감이온다. 단지 여기서 가장 큰 문제는, 동시에 건물을 지을 수 있다는 점이다. A와 B건물은 선행 건물이 없고, C 건물은 선행건물로 A B 건물이 있다고 하자. A와 B는 동시에 건설이 시작될테고 더 오래걸리는 20 이 소요되고, 그 때 C를 건설할 수 있을것이다. 이런 부분을 고려해야하는데 A와 B는 같은 수준의 레벨이라고 했을때 C 입장에서 더 오래걸리는 시간을 택해야 한다. 식을 만들어보면 [다음 건물 총 건축시간] = Max(다음건물 총..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이이 문제의 핵심은 자동차의 진출 지점을 기준으로 오름차순 하는것이다. Case 1. [1]   | ---------------------- | [2]          | ----------------------|[3]                                  | --------------- | 눈으로 봤을 때 위 문제의 답은 2임을 알 수 있다. 우선 첫번째 차량을 위해 카메라가 한 대 필요하..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/169199?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이bfs 문제이다. 단 조금 신경써야 할 것이 있는데, 한 쪽 방향 끝으로 간다는 것이다. 첫째론 로봇이 언제 멈추는지 정의할 필요가 있다. 1. 범위를 벗어났을 때2. 장애물을 만났을 때 두번째로는 동일한 곳에 방문했을때 처리를 어떻게 해줄것인가다.이거는 해당하는 칸에 몇번만에 방문했는지를 기억하면 된다.최소횟수 답을 구하기 때문에 이전에 여기 온 횟수보다 짧게 왔다면 추가 탐색을 하고, 아니면 더 할 필요..

문제https://www.acmicpc.net/problem/1283 풀이우선 단축키의 등록 여부를 확인하기 위한 캐릭터 Set을 하나 준비한다. 이후 입력을 받으면 공백을 기준으로 String 을 분리하여 String 배열을 만든다. 우선 나뉜 단어의 첫번째 문자가 단축키가 되는지 확인하기 위해 문자열 반복문을 돌며 첫번째 단어가 Set에 추가되어있는지 확인한다. 이 때 대소문자를 구분하지 않는다고 했기에 uppercase 나 lowercase 로 통일하여 검사한다. 만약 첫단어가 추가되지 않은 단축키면 [ ] 괄호를 추가하여 해당 문자열을 업데이트 하고, 출력시켜준다. 첫단어가 추가되지 않았다면 2중 반복문을 돌면서 추가되지 않은 단축키를 찾으면 된다. 코드import java.util.*;impor..

문제https://www.acmicpc.net/problem/18405 풀이아주 조금의 응용이 들어간 bfs 문제였다. 우선 바이러스가 존재하는 위치를 queue에 저장했다. 단, 바이러스가 여러종류가 있기 때문에 map 을 활용해서 key로 바이러스 번호를 설정하고 그 값으로 해당 바이러스 위치를 가지고 있는 queue 를 꺼내올 수 있도록 설정했다. 이후에는 bfs 를 수행하는데, 이 때 전염이 1회 된다는 점을 주의해야한다. 가장 최근에 전염된 바이러스만 자신 주변으로 감염을 시키기 때문에 queue에는 최근 전염된 바이러스들의 위치만 존재해야하고, 다음에 queue를 넣을때도 마찬가지여야 한다. 숫자가 낮은 바이러스부터 전염되기 때문에 작은 숫자의 바이러스의 queue 부터 접근했고,해당 queu..

문제https://www.acmicpc.net/problem/2239  풀이dfs 를 활용하여 푸는 문제이다. 배열의 앞쪽에서부터 작은값을 하나씩 대입해보고, 해당 값이 스도쿠 조건에 맞는지 검사하는 식으로 풀이가 가능하다. 정답이 여러개일경우 사전순으로 출력하라하였기에, 작은 값을 우선적으로 넣어주는 방식으로 풀이했다. 우선 값을 입력받고, 이 때 0의 개수를 체크했다. 추후에 0의 개수가 0개가 된다면 정답을 발견한것으로 판단하기 위한 용도이다. 이후 2중 for문으로 0 값이 있는 위치를 찾은다음, 해당 위치에 1부터 값을 넣어본다. 선정한 값이 가능한지 여부를 확인하고 (가로, 세로, 3*3 공간) 가능하다면 [1] 배열에 값을 세팅해주고,  [2] 0의 개수를 줄여주고 dfs로 다음 위치를 찾아..