Java

문제 접근 방식 숫자를 k번만 삭제해서 짝수로만 이루어진 부분 수열 중 가장 긴 부분 수열의 길이를 구해야 한다. 첫 숫자부터 시작 포인트로 정하고 나머지 하나의 포인터를 사용해 다음 숫자들을 탐색해나가면 된다. {1, 2, 3, 4, 5, 6, 7, 8} 예를 들어 위와 같은 수열이 주어졌고, 2번만 삭제할 수 있다면 짝수만 남겨야하니 홀수를 만날 때만 삭제해주고 다음에 홀수를 만났을 때 더이상 삭제할 기회가 남아있지 않다면 현재 까지 수열의 길이를 계산해주면 된다. (현재 까지 수열의 길이 = 끝 포인터 - 시작 포인터 - 삭제한 홀수의 갯수) // 남은 삭제 기회 // 숫자 1100x 12345 21100x 234567 1100x 34567 21100 45678 순서를 살펴보면 위와 같다. 풀이 p..

문제 접근 방식 분명 이전 투포인터 문제들과 비슷한 문제라 쉽게 풀 수 있을거라 생각했는데 반환값의 범위를 잘못 생각해서 맞왜틀을 시전하느라 시간을 날려먹었다. 수열이 수의 범위가 1 ~ 100,000까지인 10만개의 수들로 이루어져 있어서 결과가 인트형으로 될줄 알았는데 혹시 싶어 long으로 바꿔보니 맞았다... (왜 10만 * 10만을 10억으로 생각하고 있었지...새벽이라 정신줄을 놓고 했나보다) {1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1} 위와 같은 수열이 주어졌을 때 중복되지 않는 수로만 이루어지는 경우를 살펴보자 {1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1} // i[0] 1, 12, 123 // i[1] 2, 23 /..

문제 접근 방식 주어진 수 n까지의 소수를 모두 구한 후에 투 포인터를 사용해 첫 번째 소수부터 기준으로 합이 n과 같거나 커질 때까지 수들을 합해주고 합이 n과 같은 경우에는 카운트를 1 증가시켜 주면서 현재 기준점이 끝날 때마다 합에서 현재 값을 빼준 후에 다음 기준점으로 넘어가면서 계산해 주면 된다. a = {2 3 5 7 11 13 17 23 29 31 37 41} n이 41일 때를 예로 들면, 2 ~ 41까지의 소수는 위와 같다. suma[i]count 221 532 1053 1774 28115 41136v 39-25 56176x 53-35 48-54 41-73v 30-112 53233x 40-132 69293x 52-172x 29-231 60312x 31-291 68372x 37-311 784..

문제 접근 방식 주어진 수들의 부분 수열의 합이 S 이상인 것 중에 가장 길이가 짧은 부분 수열을 찾아야 하는 문제로 이분 탐색이나 투 포인터를 사용해 풀 수 있는데 투 포인터를 연습 중이기 때문에 투 포인터를 사용해서 풀었다. 이전 글에서 풀었던 2230번 문제와 비슷한 문제라 풀기는 쉬웠는데 정렬을 해야 하는줄 알고 하고 풀다가 맞왜틀을 시전하느라 시간을 날렸다. a = {5 1 3 5 10 7 4 9 2 8} / 15 suma[i]count 551 612 933 1454 24105v 19-54v 18-13v 15-32o 위와 같이 10개의 수가 주어지고, 부분 수열의 합이 15이상인 경우를 살펴보면 시작 점을 0, 비교할 인덱스는 1부터 시작했을 때, 합이 15 이상이 될 때까지 더하다 15 미만이..

문제 접근 방식 두 수의 차이가 m 이상이면서 가장 작은 경우를 구해야 하는데 간단하게 이중 반복문으로도 풀 수는 있지만 입력의 크기를 생각하면 시간초과 때문에 다른 방법을 사용해야 한다. 골드 문제지만 투 포인터를 사용해서 풀면 간단하게 풀 수 있는 문제로 6개의 수가 주어졌을 때 차이가 3 이상인 수 중에서 가장 작은 경우를 찾아보겠다. 1 3 5 7 8 10 우선 위와 같이 주어진 수들이 정렬되어 있을 때 순서대로 비교할 기준을 처음인 1과 나머지 숫자들을 차이가 3 이상이 될 때까지 비교해보면 1 - 3 >> 2 1 - 5 >> 4 1 - 7 >> 6 1 - 8 >> 7 1 - 10 >> 9 5와 비교 했을 때 차이가 4로 처음으로 3보다 커지는데 이후의 비교는 차이가 점점 커지기 때문에 의미가 ..

문제 접근 방식 문제에 나오는 환형의 개념 중에서 대각선 이동이 살짝 햇갈렸던 문제인데 위의 사진들처럼 대각선 이동 중 인덱스를 벗어나는 상황을 살펴보면 인덱스가 음수가 되는 경우에는 가장 아래줄의 왼쪽이나 오른쪽으로 한칸 이동 양수가 되는 경우에는 가장 첫줄의 왼쪽이나 오른쪽으로 한칸 이동해주면 된다. 나머지 상하좌우 이동도 환형을 생각해주면서 백트래킹으로 단어를 조합만 해주고 이를 맵을 사용해서 각 단어별로 카운팅을 해줬다. 설명은 이해가 잘 안갔는데 막상 풀어보니 난이도 자체는 어렵지 않았던 문제다. 풀이 public class Main { private static int n; private static int m; private static int min = Integer.MAX_VALUE; p..

문제 접근 방식 처음 풀어보는 DP문제로 백트래킹으로도 풀 수 있지만 시간제한이 빡빡한 문제이기 때문에 DP로 효율적으로 풀어야 풀 수 있는 문제다. 2를 1로 만드는 경우 2 - 1 >> 1 2 / 2 >> 1 3을 1로 만드는 경우 3 / 3 >> 1 3 - 1 - 1 >> 2 4를 1로 만드는 경우 4 / 2 / 2 >> 2 4 / 2 - 1 >> 2 4 - 1 - 1 / 2 >> 3 4 - 1 - 1 - 1 >> 3 가장 작은 경우를 예로 들어 2 ~ 4가 1이 되는 경우를 살펴보면 위와 같은데 4 / 2 / 2 순서로 계산하여 1이 되는 경우에는 숫자의 변화는 4 > 2 > 1이 될 것이고 해당 숫자의 인덱스에 계산 횟수를 기록한다 치면 {0, 2, 1, 0, 0} 이 된다. 여기서 알 수 있는..

문제 접근 방식 바킹독님 시뮬레이션 강의를 들으면서 처음 풀어보는 빡구현 문제로 지문 길이 보고 풀기 싫어지지만 귀찮음을 이겨내고 풀어냈다... 무식하게 풀다 보니 코드가 엄청 길어지긴 했지만 백트래킹을 사용해서 쉽게 풀 수 있는 문제다. (지문의 길이게 겁먹지 말자...) 백트래킹 연습 문제로 풀었던 N과 M 시리즈를 CCTV에 적용하면 되는 문제로 1번 : 위, 오른쪽, 아래, 왼쪽 중 한 방향이벽을 만나기 전까지 감시 가능 2번 : 위/아래, 왼쪽/오른쪽 중 양쪽이 벽을 만나기 전까지 감시 가능 3번 : 위/오른쪽, 오른쪽/아래, 아래/왼쪽, 왼쪽/위처럼 직각인 두 방향이 벽을 만나기 전까지 감시 가능 4번 : 위/오른쪽/아래, 오른쪽/아래/왼쪽, 아래/왼쪽/위, 왼쪽/위/오른쪽처럼 세 방향이 벽을..