문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 풀이 예상 이 전에 바로 누적 합 문제를 풀었었기 때문에 바로 누적합이 떠올랐다. 풀이방법 (접근 방법 & 시간복잡도) 백준 2015(수들의 합4)풀이 풀이 방법 은 비슷하게 풀어서 상세하게는 설명하지 않고 달랐던 부분만 적어보겠다. A 배열에서 부 배열의 합을 Amap에 저장한다. (key: 합, value: ..
문제 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 풀이 예상 N의 개수가 200,000 개 이기 때문에 부분 합 전체를 구해서 풀면 시간초과가 날 것 같았다. 문제에서 주어진 부분 합이란 배열 자리 수가 연속된 숫자이기 때문에 누적 합을 통해서 풀 수 있을 것 같다고 생각했다. 풀이방법 (접근 방법 & 시간복잡도) 누적합을 배열에 저장해 두고, 이 전에 나온 누적합과의 차이..
문제 https://www.acmicpc.net/problem/1407 1407번: 2로 몇 번 나누어질까 자연수 N이 주어지면, 자연수를 유지하면서 N을 2로 몇 번까지 나눌 수 있는지를 생각해 볼 수 있다. 즉, N의 모든 약수 중 2의 거듭제곱 꼴이면서 가장 큰 약수를 생각하는 것이다. 예를 들어 15의 www.acmicpc.net 풀이방법 범위가 (1≤A≤B≤10^15) 로, 엄청나기 때문에 숫자 하나 하나 나누면서 계산을 할 수 없다고 생각했다. 그래서 생각해낸 방법이 1~B 까지 더한값에 1~A-1 까지 더한 값을 빼면, 즉 f(B) - f(A-1) 으로 계산하는 방법을 생각했다. function 안에서는 일정한 규칙을 찾았고, 그 규칙에 따라 계산해 주면 된다. 규칙은주어진 숫자 n에 대해서..
https://school.programmers.co.kr/learn/courses/30/lessons/17677?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 문자열을 받아서 char 배열로 만든다. 앞부터 두개씩 잘라서 보고 둘다 알파벳이라면 대문자로 바꿔서 각각의 map에 있는지 검사한다. map에 없으면 value값을 1로저장 map에 있다면 value값을 +1 값으로 저장 맵 값을 전부 순회하며 aNum, bNum, n 값을 채운다 (순서대로 str1의 총개수, str2의 총개수, 교집합개수) aNum 과 bNu..
https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 해시맵과 Priority Queue를 사용. 현재 문자열을 받아와서 전부 대문자로 바꿔준다(toUpperCase() 사용) 맵에 들어있는 개수가 캐시 사이즈보다 작은경우 (pq와 맵에 값을 넣는다.) 이미 맵에 들어있는 값이면 +1 맵에 없는 값이면 +5 맵에 들어있는 개수가 캐시 사이즈와 같은 경우 (pq와 맵에 값을 넣는다.) 이미 맵에 들어있는 값이면 +1 ..
https://school.programmers.co.kr/learn/courses/30/lessons/60058?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이방법 문제를 이해해보려고 했다가 망했던문ㅈ ㅔ... 진짜 문제에서 하란대로 해야지 풀린다 1. 문자열을 두개로 나눈다. -> 나누는 기준 : '(' 이면 -1, ')' 이면 +1을 해주고 0이 되는 지점을 기준으로 앞 문자열을 u, 뒷 문자열을 v 2. u문자열의 맨 앞문자가 '(' 이면 올바른 괄호 문자열이다. 3. 올바른 괄호 문자열인 경우 u를 answer에 추가..
https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 풀이방법 bfs로 풀었다가.. 메모리초과 빔 맞음.. 그래서 생각한 dp풀이 dp[i][j][k] -> i,j 위치에 있는 k 우유를 마셨을 때 우유의 최대 개수 1. 내 기준으로 동쪽, 남쪽을 본다. 2. 현재 위치의 색이 0 이면(딸기우유) 1과 현재 값 중 큰 값을 넣어준다. => 딸기우유가 처음이 아닐 경우를 고려 3. 현재 위치를 기준으로 동쪽우유를 본다 => 현재 위치값과 동쪽값 중 큰 값..
https://www.acmicpc.net/problem/20440 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE 오름차순 Arrays.sort(mos,(a,b) -> { if(a[0] == b[0]) { return a[1] - b[1]; }else { return a[0] - b[0]; } }); PriorityQueue pq = new PriorityQueue(); pq.add(mos[0][1]); count = 1; resultS = mos[0][0]; resultE = mos[0]..
