= 접근 과정 ( 틀림 ) = 이렇게 N개의 전구와, K가지의 색 => 최대 200개의 전구, 최대 20개의 색이므로 완전 탐색을 이용하면 시간 초과로 분명히 오답! => O(N!), 이유는 N개의 색이 모두 다 다를 수 있기 때문 이러한 문제는 DP를 이용해서 시간을 줄이는게 핵심이다. 처음 나는 재귀 함수를 이용해서, 이미 거친 전구들은 return하는 형식으로 문제를 접근했다. 1. int[] arr = new int[n] 배열에 1, 1, 2, 3, 3, 3, 2, 2, 1, 1의 값을 넣고 0번 index의 값을 2로 바꿨을 때, 인접한 값(1번 index)이 0번째 값(1)이랑 같을 때 같이 2로 변경해주고 아니면 return을 하는 형식으로 count를 했다. 2. 모든 값이 k로 다 통일 ..
투 포인터 알고리즘을 이용해서 해결하는 문제. = 내가 틀린 이유 = 시간 초과로 틀렸다. while문 안에 for문을 이용해서 코드를 짰는데, 이렇게 하면 시간 복잡도는 O(NlogN) while문 하나만 이용해서 O(N)을 만들어야 해결할 수 있는 문제다. = 접근 방법 = 1. 부분합을 구하는 문제이기 때문에 정렬할 필요 x 2. 투 포인터 알고리즘을 이용해서 부분합 구한 후, 최솟값을 계속 갱신 3. while문 종료 조건을 if (sum >= s) 이후, else if에 end == n을 사용하는 이유는? 예제 입력 1에 9, 2, 8 부분을 보면 9, 2, 8일 때, 19이고 if (sum >= s) 를 타고 2, 8이 된다. 그리고 end == n 이라는 조건을 만나서 while문 종료 따라..
= 내가 접근한 방법 = 1. 주어진 제한 시간은 1초, n의 범위를 생각하면 2중 for문으로는 분명히 시간 초과 ! 따라서 투 포인터 알고리즘 사용 2. 0번째 index 값과, n - 1번째 index값을 비교 합한 후, 절댓값을 씌우고 최솟값을 계속 갱신한다. 최솟값을 갱신하면서 index의 값도 갱신. = 내가 틀린 이유 = 1. 맨 처음 값과 맨 마지막 값의 합을 비교하면서 1-1. 0보다 클때, end값을 증가 1-2. 0보다 작을 때, start값을 증가 1-3. 0일 때, break; 라는 조건을 생각해야 되는데 절댓값을 씌운 상태에서 이 3가지 조건문을 사용했다. 절댓값이 없는 그냥 순수한 합을 통해서 이 3개의 조건문대로 움직였어야했는데 실수했다. 절댓값을 씌우고 if문이 진행이 되면..
= 내 접근 방법 ( 오답 ) = 흔히 사용하던 2중 for문을 사용했기 때문에 오답이다. 투 포인터 알고리즘은 언제 사용해야 될까? 문제를 잘 봐야한다. 시간 제한은 1초, n은 1000000이기 때문에 2중 for문을 이용한 단순한 코드는 O(N^2)이기 때문에 시간을 초과한다. 이러한 문제에 닥쳤을 때 투 포인터 알고리즘을 이용해서 해결해야 됨! https://byungil.tistory.com/193 이 링크에서 알고리즘에 대한 설명을 써놨다. = 알고리즘을 이용한 접근 ( 정답 ) = 1. 정렬된 배열이 필요. 2. 왼쪽 맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 접근 만족 => end-- or start++ 둘 중 하나, count++ 두 수의 합이 더 크면 end-- 두 수의 합이 더..
이 문제에 대한 설명이 너무 부족하다. 이 문제만 보고 완벽하게 이해하고 넘어간다는게 정말 힘든 것 같다. 예제 입력 1부터 설명하겠다. 첫번째 줄 8은 숫자를 총 8개를 입력한다는 뜻이고, 4를 입력 -> 1 2 3 4를 push (4번 / +는 4개 저장) 그리고 맨 마지막 4를 pop (1번 / -는 1개 저장) 그럼 내 스택에는 1, 2, 3이 저장되어있고 다음에 입력할 숫자는 3이기 때문에 peek했을 때 3이면 pop하고 끝 (1번 / -는 1개 저장) 그다음 입력하는 숫자는 6, 근데 우리가 지금까지 입력한 숫자 중 최댓값은 4다 ( 맨 처음에 입력한 숫자는 4였다 ) 따라서 최댓값보다 큰 5, 6만 push (2번 / +는 2개 저장) 그리고 맨 마지막 6을 pop (1번 / -는 1개 저..
= 내가 접근한 방법 = import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { // 1. input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); int n = ..
