슬라이딩 윈도우5 [백준] 3078: 좋은 친구 - JAVA https://www.acmicpc.net/problem/3078 풀이학생의 이름이 등수 순으로 주어진다. 등수가 k를 넘지 않으면서 이름의 길이가 같으면 좋은 친구이다. 좋은 친구의 쌍을 구해야 한다. 처음에는 단순히 큐를 사용하면 되는 문제인 것 같았다. 하지만 메모리초과... 어떻게 푸는지 방법을 찾아보았다. 이름의 길이가 2~20이므로 길이 20의 큐 배열을 선언한다. 입력받은 문자열의 길이를 len이라고 한다면, 큐 배열의 len 인덱스에 들어있는 값이 해당 번호와 자신의 번호의 차가 k보다 크다면 poll 해준다. poll 해준 뒤 남아있는 개수를 정답에 더해준다. 그 후 같은 인덱스에 자신의 등수를 넣어주면 된다. 메모리: 47332KB시간: 368ms언어: Java 11import jav.. 2024. 5. 19. [백준] 1593: 문자 해독 - JAVA https://www.acmicpc.net/problem/1593 풀이문자열 W와 S가 주어진다. S를 W의 길이만큼 잘라 그 안의 문자 순서를 바꿨을 때 W로 만들 수 있는 개수를 세는 문제이다. map을 두개 선언하여 하나에는 W에 들어있는 문자와 개수를 담았다. 또 다른 하나는 W의 길이만큼 S를 잘라 개수를 담았다. 슬라이딩 윈도우를 이용해 S를 탐색하면서 map의 개수를 조정하여 map 두 개가 같은지 비교하여 같을 경우 답을 하나 증가시켰다. 메모리: 149420KB시간: 900ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOE.. 2024. 5. 19. [프로그래머스] 광고 삽입 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이시청자의 시청 시작, 종료 시각이 주어지고, 광고 지속 시간이 주어진다. 광고 지속 시간동안 누적 재생 시간이 가장 많은 구간을 골라야 한다. 누적합을 이용했다. 시청 시작시간에 +1 하고, 종료시간에 -1을 해놓고 누적합 배열을 끝까지 가면서 `preSum[i] += preSum[i - 1]` 해줬다. 누적합 배열을 완성한 후, 0 ~ 광고시간 까지를 첫 기준으로 삼아 1씩 늘려가면서 비교하며 .. 2024. 5. 18. [백준] 1522: 문자열 교환 - JAVA https://www.acmicpc.net/problem/1522 풀이a와 b로 이루어진 문자열이 주어지고, a를 모두 연속으로 만들어야 한다. 원형 문자열이기 때문에 aaabbba와 같은 문자열도 연속이다. a의 개수를 세어 aCount에 저장했다. 문자열을 처음부터 끝까지 탐색하면서 해당 인덱스를 시작으로하고 길이가 aCount인 부분문자열에서 b의 개수를 세주고 ans를 최솟값으로 갱신했다. b의 개수만큼 바꾸면 a가 연속이게 된다. 메모리: 14268KB시간: 128ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedRead.. 2024. 5. 17. [백준] 15961: 회전 초밥 - JAVA https://www.acmicpc.net/problem/15961 풀이슬라이딩 윈도우를 사용해서 카운트하는 문제였다. 회전 초밥을 연속에서 k개 먹어야하는데 최대한 다양한 종류를 먹으려고 한다. 쿠폰이 하나 주어지고 쿠폰에 적혀진 종류의 초밥을 먹지 않았으면 하나 제공해 준다. 즉, 가장 다양하게 먹으려면 연속된 k개에서 다 다른 초밥을 먹고 쿠폰에 있는 초밥을 제공받아 먹어야 한다. int로 먹은 것을 체크하는 배열을 만들었다. left는 0, right는 k-1부터 시작하여 1씩 늘리면서 체크해준다. 체크 배열에 쿠폰에 있는 초밥이 없으면 bonus를 1로 해주고 cnt + bonus의 최댓값이 정답이 된다. 메모리: 170972KB시간: 548ms언어: Java 11import java.io.*.. 2024. 5. 13. 이전 1 다음