오답 노트 & 새로 알게 된 점 항상 두 포인터 문제를 풀면 연속 부분 수열, 순서를 지키며 차례대로 라는 말이 문제에서 나왔다. 하지만 이 문제에서는 그러한 힌트가 없었다. 그래서 나는 코테에서 이런 문제가 나온다면 내가 풀 수 있을까?라는 생각이 들었다. 아마 처음에 접근했을 때는 완탐으로 생각을 할 것이다. 그렇다면 타겟을 하나 고르고 -> O(N) 더해서 타겟이 되는 두 수를 구한다 -> O(N^2) 그래서 O(N^3)이다. 당연히 TLE가 난다. 그렇다면 여기서 어떤 방법을 사용해야 시간 복잡도를 줄일 수 있을까? 두 포인터를 사용하여 타겟을 하나 정하고 O(N) 두 수를 정할 때, O(N)을 사용하면 된다. 두 수를 정하고 합이 target보다 작으면 최소 입장에선 최대를 더했는데 작기 때문에..

오답 노트 & 새로 알게 된 점 문제에서 연속한 1개 이상의 수를 뽑았을 때 라는 말로 투 포인터 힌트를 줬다. 투 포인터를 구현하는 코드는 어렵지 않았지만 경우의 수를 계산할 때 생각이 필요하다. 1 2 3 1 2 에서 처음에 1에서 3까지 e가 이동할 수 있다. 그렇다면 경우의 수는 1 1 2 1 2 3 이 있다. 이 점을 보았을 때, e - s + 1를 하게 되면 경우의 수를 계산할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 package TwoPointers; import java..

오답 노트 & 새로 알게 된 점 문제에서 최대 N개의 연속된 문자열로 투 포인터에 대한 힌트를 주었다. 처음에 문제 접근을 할 때, possible 배열을 boolean으로 했다. 그러나 abbcc와 같은 경우 b의 개수는 2개이므로 b를 하나 없애도 결국 하나 남기 때문에, b가 모두 없어져야 알파벳의 한 종류가 사라지게 된다. 그래서 boolean으로 하면 틀리게 된다!! 처음부터 int로 할껄 그랬나보다.. 아무튼 위에서 말했듯이 b의 개수가 2개라면 0개가 되야지 한 종류의 알파벳이 사라지게 된다. 따라서 s를 움직일 때, possible의 값이 0이 되야지 cnt(종류의 개수를 나타냄)를 -1 할 수 있다. 또한, e를 움직이면서 possible값을 ++ 해줄 때, possible이 1이 되면 ..

오답 노트 & 새로 알게 된 점 문제에서 차이가 M이상이면서 제일 작은 경우를 구하라고 했다. 그렇다면 e를 움직이면서 A[e] - A[s] >= M 되는 순간에 while문을 종료하고 최소값을 갱신하면 된다. 배열은 정렬되어있기 때문에 조건을 만족하는 순간 현재 s에서 구할 수 있는 최소값이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 package TwoPointers; import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

오답 노트 & 새로 알게 된 점 이 문제는 이분 탐색으로도 풀었던 문제이다. 투 포인터를 이용해서도 풀 수 있기 때문에 투 포인터 공부할 겸 풀어보았다. 당연히 일일이 계산하는 O(N^2) 는 TLE다. O(N)인 투포인터를 생각하게 되었다. 처음에 여기서 i < j 를 보고 정렬하면 안되는건가? index를 유지하라는 말인가?라고 생각했다. 하지만 그게 아니였고, 단지 중복 계산을 막기 위해서이다. 예로 12 + 1과 1 + 12는 서로 같은 것임을 나타낸 것 같다. (나의 생각) 그래서 정렬하고 처음과 끝에서부터 각각 시작하여 투 포인터를 하면 해결할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

오답 노트 & 새로 알게 된 점 이때까지 두 포인터 문제를 풀 때마다 항상 s와 e가 왼쪽 끝에서 시작하여 오른쪽 끝까지 가는 문제만 풀어보았다. 그래서 해당 문제를 보고 투 포인터로 풀어야겠다라는 생각이 들고, 한 시간동안 어떻게 풀어야하지 생각했다. 이 문제는 s와 e가 양쪽 끝에서 시작하는 투 포인터이다. i * j의 최댓값을 구하려면 A도 최대, B도 최대여야한다. 여기서 그러면 s와 e 중에 어떤 기준으로 움직여야할까? 라는 생각을 해야한다. A[i]와 A[j], 둘 중에 최대값을 움직여본다고 생각해보자. 그렇다면 결국에 min값은 그대로이거나 더 작아지게된다. 마찬가지로 둘의 사이가 가까워져 값이 줄어들게 된다. 결국 최대값을 움직일 필요가 없다. 코드 1 2 3 4 5 6 7 8 9 10 1..

오답 노트 & 새로 알게 된 점 문제에서 홀수를 K개 없애면서 짝수로 이루어진 연속된 수열 중 가장 긴 길이를 구하는 것이다. 만약에 K개의 홀수를 골라 길이를 구한다고 생각하면 바로 TLE가 난다. 그래서 투 포인터를 사용하여 앞에서부터 홀수이면 cnt를 증가시키면서 cnt가 K개 이하일 때까지 e를 늘리면서 길이의 max값을 구하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.io.BufferedReader; import java.io.IOException; import java.io..

오답 노트 & 새로 알게 된 점 투 포인터 공부를 하고 있어서 이 문제는 무조건 투 포인터로 풀어야한다는 생각을 버리고 풀었다. 처음에 접근할 때, O(N^2)로 풀면 바로 TLE가 나기 때문에 아마 O(NlogN)이하로 풀어야한다. 그리고 연속 부분 수열의 길이라는 힌트를 줬기 때문에 투 포인터로 접근할 수 있다. 여기서 아마 중복 처리를 어떻게 해줬냐가 중요한 것 같다. possible이라는 배열을 만들어 A[i] 배열의 value들을 index에 넣어 ++ 해주었다. 그 중 K값을 넘지 않게 탐색하면서 길이의 최댓값을 구해주면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

오답 노트 & 새로 알게 된 점 이 문제는 분할 정복에서 아마 정렬된 배열들을 합치는 부분을 코드로 구현하면 된다. 다만 N,M 크기가 크기 때문에 TLE에 조심해야한다. 처음에 ArrayList에 담아서 출력했는데 바로 TLE가 났다. 아마 이 문제를 풀 때에는 합칠 때마다 바로 출력을 해야 TLE가 나지 않을 것이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 package..

오답 노트 & 새로 알게 된 점 1의 개수가 K개 만큼 있을 때, 집합의 개수를 최소화시켜야한다. 이 때에는 e를 늘리면서 1을 만나게 되면 cnt++을 해주고, 개수를 만족시키면 s를 한칸씩 밀면서(배열에서 빼면서) 온다. 이 때, 배열에서 뺄 때 1을 빼게 된다면 cnt--을 해줘야한다. 투 포인터 기본 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 package TwoPointers; import java.io.BufferedReader; import java.io..

오답 노트 & 새로 알게 된 점 두 포인터의 기본 문제이다. 처음에 배열의 처음부터 K까지의 값을 더해준다. 그리고 나서 s와 e를 하나씩 늘리면서 A[s]는 빼주고, A[e]는 더해주면서 최대값을 구하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 package TwoPointers; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stri..

오답 노트 & 새로 알게 된 점 이 문제를 보고 내가 나중에 이걸 보고 투 포인터를 사용할 수 있을까라는 생각이 들었다. 제일 처음에 드는 생각은 당연히 O(N^2)일 것이다. 숫자 하나를 선택하고 나머지 숫자들을 다 더해보고 절댓값이 가장 작은 값을 고르는 방법이다. 하지만 N이 100,000이기 때문에 TLE가 바로 난다. 그렇다면 여기서 우리는 어떤 방법을 사용해야 시간 복잡도를 줄일 수 있을까? 배열들을 정렬하고 최소값과 최대값을 더해보자. 더한 값이 양수라면, 최대 입장에서는 최소값을 더해도 양수가 나온다면, 나머지 값들은 당연히 계산을 안해도 양수가 나올 것이다. 따라서 e를 하나 줄여준다. 더한 값이 음수라면, 최소 입장에서는 최대값을 더해도 음수가 나오니까 나머지 값들은 계산을 안해도 당연..