= 내 접근 방법 ( 오답 ) = 흔히 사용하던 2중 for문을 사용했기 때문에 오답이다. 투 포인터 알고리즘은 언제 사용해야 될까? 문제를 잘 봐야한다. 시간 제한은 1초, n은 1000000이기 때문에 2중 for문을 이용한 단순한 코드는 O(N^2)이기 때문에 시간을 초과한다. 이러한 문제에 닥쳤을 때 투 포인터 알고리즘을 이용해서 해결해야 됨! https://byungil.tistory.com/193 이 링크에서 알고리즘에 대한 설명을 써놨다. = 알고리즘을 이용한 접근 ( 정답 ) = 1. 정렬된 배열이 필요. 2. 왼쪽 맨끝 과 오른쪽 맨끝에서 순차적으로 번갈아 가면서 접근 만족 => end-- or start++ 둘 중 하나, count++ 두 수의 합이 더 크면 end-- 두 수의 합이 더..
투 포인터 개념 각 원소마다 모든 값을 순회해야할 때, *연속하다는 특성을 이용해서 처리, 단순 반복문을 이용해서 문제를 해결하려고 하면, 시간 복잡도가 O(N^2), O(N^3)인 경우가 있기 때문에 투 포인터 알고리즘을 이용해서 문제를 해결해야 된다. 포인터 2개가 1차원 배열을 증가하는 방향으로만 순회하므로 O(N) + O(N) = O(N) 이 알고리즘을 처음 접했을 때 어려웠는데 이제는 기본적인 문제는 풀 수 있게 되었다. 그만큼 계속 반복함! https://www.acmicpc.net/problem/2003 이 문제를 기반으로 설명을 하겠따. n개로 나열 된 수, +해서 m이되는 경우의 수를 구하자 - 자연수로 이루어진 1차원 배열이 주어진다. - 연속되는 부분 배열 중 원소의 합이 M이 되는 ..
이 문제에 대한 설명이 너무 부족하다. 이 문제만 보고 완벽하게 이해하고 넘어간다는게 정말 힘든 것 같다. 예제 입력 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 = ..
= 내가 접근한 방법 = 숫자 카드1 문제랑 똑같이 접근했다. Map을 이용해서 Map의 메서드 getOrDefault를 활용하는 방식으로 해결했는데 이 문제도 이분 탐색을 이용해서 풀어야 되는 문제였다. 지난 숫자 카드1보다는 조금 더 간결하게 코드를 짜긴 했지만, 결국 이분 탐색이 핵심이다. getOrDefault라는 메서드는 card라는 맵 안에 내가 입력한 값이 있으면 그 key의 밸류를 갖고오는 것이고 없으면 defaultValue ( 내가 지정한 값 ) 0을 넣는 메서드다. 이 메서드를 활용하면 이분 탐색을 안 하고 쉽게 해결할 수 있다. = 이분 탐색 = https://st-lab.tistory.com/267 이 블로그를 참고해서 공부했다. 나보다 훨씬 자세한 설명은 이 블로그에 있다. 간단..
= 내가 접급한 방법 = Map을 이용해서 접근했다. 1. 상근이가 갖고 있는 카드를 Map으로 이렇게 저장 2. 주어진 카드를 새로운 Map으로 이렇게 저장 (result) ( 순서 유지를 위해 LinkedHashMap을 이용 ) 3. card에 있는 key값을 for문을 이용해서 뿌려줄 때, contains메서드를 이용해서 result에 그 key값이 존재한다면 로 수정을 했다. 그리고 결과를 그대로 출력해주면 됨. = 이분 탐색을 이용한 방법 = 이 문제의 핵심은 이분 탐색 알고리즘을 활용할 수 있냐 없냐 문제였다. 시간 복잡도를 logN으로 할 수 있는 최적의 탐색 방법이다. 정렬된 배열을 탐색하는 것인데, 반을 쪼개고 반을 쪼개고 반을 쪼개서 찾는 방식이다. 1 ~ 10까지의 값이 존재하면 1 ..
