얘 때문에 자존감 떨어짐....처음에 문제 이해를 못하겠어서 멘붕이 왔었음... 처음 사이즈는 2부터 시작한다.물고기 만약 자기 사이즈 == 먹은 물고기 크기 이면 자기 사이즈를 +1한다. 가장 중요한 점은 아기상어의 먹이 위치 지정이다.바로 이 부분인데, 처음에 보면 멘붕이 오고 여러번 봐도 멘붕이 온다 천천히 봐도 멘붕이 온다. 그런데 그냥 우선순위 큐를 생각하면 된다.보통 BFS에서는 좌표를 Deque (자바기준) 에 넣어서 사용하지만 이 친구의 경우에는 가야하는 좌표가 우선적으로 있으므로 우선순위 큐를 사용하면 된다.1. 우선순위 큐 사용하기 우선순위 큐의 가장 처음 정렬 기준1. 가장 왼쪽에 있는 먹이2. 가장 위에 있는 먹이3. 가장 가까운 먹이 처음에 거리가 가까운 것을 기준으로 정렬한다. ..

BFS 문제였다.어려운 것은 얼음 녹는건 구현에 성공 했는데 얼음 덩어리를 어떻게 파악할 수 있지? 였다..덩어리를 파악하는 방법은, 2차원 배열을 계속 탐색하다가 0이 아닌 수가 나오면 그 주변 값(동서남북)을 계속 탐색하며 동서남북에 대해서도 덩어리가 있는지 체크하는 것이다.방문 배열을 업데이트 해 방문한 것은 visitied[i] 를 true로 둔다.예를 들어 위의 그림에서 0이 아닌 가장 처음 2의 주변을 탐색한다. 2의 동서남북에 위치해있는 0,3,4,0을 탐색하고, 동서남북 중에서도 0이 아닌 수가 나오면 그 주변을 또 탐색한다. 예를 들어 3이 0이 아니므로 3의 주변을 탐색한다. 3의 주변 중에 7을 탐색한다.. -> 이런 식으로 가면 계속 인접한 빙하들을 만날 수 있다.이렇게 큐에 계속 ..

시간복잡도 생각해보기N이 최대 10^5이므로 O(NlogN)에 해결 필요M은 최대 10^4이므로 O(N^2)까지 가능TreeSet, TreeMap을 사용해서 NlogN + 명령어를 수행하는 부분에서 (MlogN) 이므로 총 NlogN풀이 아이디어이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다. -> 문제 번호가 난이도만 다른채 중복 가능하므로 Key는 안 되고 문제번호들을 Value로 두고 난이도를 TreeMap의 Key로 둬서 정렬해서 품.한 난이도 당 여러 문제가 들어갈 수 있고, 명령어 수행 조건에 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다, 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다. 등의 조건이 있으므로 Tr..

시간복잡도 생각해보기최대 길이가 2500이라서 O(N^2)도 가능한 문제였다.투 포인터를 이용해 풀었으므로 문자열 길이 n에 대해서 다 돌면: O(N)하지만 문자열이 다른 경우에 그 문자열을 제외하고 돌아야 하므로 O(N)따라서 총 O(N^2) 에 수렴함풀이 아이디어투 포인터를 이용해서 회문인지 검사하고, 만약 해당 r과 l에 해당하는 문자 char이 다르면, r과 l을 제외한 문자열을 제외하고는 각각 회문인지 다시 검사한다.의사코드 / 풀이 과정전체적인 틀: 투 포인터 활용while(l만약 str.charAt(l) != str.charAt(r): 이면, 그 l,r을 각각 전체 str에서 제거하고 회문이 되는지를 확인한다.boolean skipLeft = isPalindrome(skipLeftStr,0,..

시간복잡도 생각해보기문자열의 총 길이가 10^6 이고 제한시간 2초이므로 2 X 10^8 개의 연산이 가능하다.따라서 O(N^2)에서는 10^12 개의 연산이 필요하므로 제한시간 초과가 되므로 O(NlogN)에 해결해야 한다.풀이 아이디어replace.All() 을 처음에 사용했으나, String은 불변 객체이므로 replaceAll은 내부적으로 새로운 문자열을 생성해 원본 문자열을 대체한다. 따라서 문자열의 크기가 10^6처럼 매우 크거나 대체 작업이 여러번 수행 될 경우에는 새로운 문자열 객체가 과도하게 사용 돼 메모리를 초과한다.메모리를 효율적으로 사용하기 위해서는 Stack의 push, pop을 사용한다.문자열을 charAt으로 나눠서 계속 stack에 푸쉬하다가, bomb의 문자길이와 비슷해지면..

시간복잡도 생각해보기10^6이 최댓값이므로 O(NlogN)안에 해결하는 것이 중요하다.배열을 정렬하고 -> O(NlogN) + N-1개의 차를 계산하고O(N) +O(N-K)만큼 차를 더하므로 =>O(NlogN)풀이 아이디어K개의 집중국이 있을 때 연속된 센서 간의 차를 최소한으로 해라 => 그리디센서 좌표 배열을 받아서 연속된 센서 간의 차를 구한다.연속된 센서 간의 차이를 오름차순으로(혹은 내림차순)으로 정렬한다.집중국 개수 K-1 만큼만 배열들을 더해준다.집중국 K를 세워야 한다면 센서와 센서 사이를 K-1 회 뛰어넘을 수 있기 때문이다. 그리고 자기 자신에만 집중국을 세운다면 거리가 0이 되는 것도 생각해야 한다.의사코드 / 풀이 과정for(int i=0; i참고 자료