투포인터5 [프로그래머스] 가장 긴 팰린드롬 https://school.programmers.co.kr/learn/courses/30/lessons/12904# 풀이 abbc, abcba 인 경우를 잘 살펴보면 첫번째는 b와 바로 다음 b가 같으므로 펠린드롬 시작, 두번째는 b와 다다음 b가 같아서 펠린드롬이 시작한다. 정리하자면 s 왼쪽부터 순회하면서 현재 = 현재의 다음 혹은 현재 = 현재의 다음다음인 경우에만 팰린드롬 가능성이 있는지 확인하면 된다 s.length-2까지 순회하며 펠린드롬이 가능한 경우를 찾는다 현재 = 다음 인 경우 getPalinLen를 구한 뒤 바로 이전의 result와 max 비교 현재 = 다음다음 인경우 getPalinLen + 1와 이전의 result비교한다 (1은 중간에 낀 문자) getPalinLen은 팰린드롬을.. 2024. 2. 22. [카카오2018] 프렌즈4블록 https://school.programmers.co.kr/learn/courses/30/lessons/17679# 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은.. 2023. 11. 18. [레벨3] 기지국 설치 문제 링크 첫번째 풀이 (실패) set에 1부터 n까지 아파트를 정리한다 stations를 순회하면 영향을 받는 아파트들을 set에서 지운다 set을 배열로 변환하여 순회하면서 연속적인 숫자가 아닌 부분 (즉 2번에서 지운 구간에 의해 나눠진 구간들)을 만날떄마다 range의 갯수로 나눠 기지국 갯수를 구한다. function solution(n, stations, w) { var answer = 0; const numArr = Array.from({length: n},(_, i) => i+1); const set = new Set(numArr); for (const station of stations) { set.delete(station); for(let i = 1; i 2023. 11. 1. [프로그래머스 lv2] 두 큐 합 같게 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/118667 첫번째 풀이 (성공) 탈출조건, 시간초과를 어떻게 세울지 고민했다. 탈출조건 먼저 탈출조건은 두 큐의 합이 같거나 최대이동 횟수를 넘었을 때다 여기서 최대이동 횟수는 두 큐의 길이가 같으므로 queue1.length*2로 설정했다. 최대이동횟수 이상 이동하게 되면 -1을 리턴한다. 시간초과 shift의 시간복잡도는 O(n)으로 시간초과가 난다 따라서 shift를 사용하지 않고 shift 할 위치는 인덱스로 기억하고 push만 한다. 두 개의 큐의 합이 홀수이면 -1 리턴한다 각 큐의 shift할 인덱스 변수를 0으로 설정한다 각 큐의 합이 같거나 최대이동 횟수 전까지 두 큐의 합을 비교해 .. 2023. 10. 10. [프로그래머스 lv2] 연속된 부분 수열의 합JS [투포인터] https://school.programmers.co.kr/learn/courses/30/lessons/178870 문제 요점 비내림차순이란 222, 2334 처럼 nlogN 풀이 투포인터 시작 포인터와 끝 포인터 두 가지를 사용하면서 범위를 넓혀나간다. 포인터 사이의 모든 원소의 합이 k이하면 끝 포인터 값을 늘리고 k초과면 시작 포인터 값을 늘리기 포인터 i, j 둘 다 0인덱스에서 시작하고, j가 sequence 배열 끝에 다다를 때까지 순회하면서 합sum을 계산한다. (j가 sequence를 넘어가면 더 이상 큰 부분수열의 합을 구할 수 없다.) 둘의 합 = k 이면 answer에 {시작 인덱스, 끝 인덱스, 끝 인덱스-시작인덱스}를 저장한다 가장 작은 수인 sequence[i]를 sum에서 빼고.. 2023. 10. 9. 이전 1 다음
