분류 전체보기 (241) 썸네일형 리스트형 [프로그래머스 JAVA] 전화번호 목록 https://school.programmers.co.kr/learn/courses/30/lessons/42577 전화번호 목록 문제를 다시 정리하면서, 왜 어떤 풀이는 통과하고 어떤 풀이는 일부 테스트에서 실패했는지를 단계적으로 정리해본다. 핵심은 접두사 관계를 한쪽 방향만 보지 않았는지 여부다. 문제 핵심어떤 전화번호가 다른 전화번호의 접두사인 경우가 하나라도 있으면 false를 반환해야 한다. 여기서 중요한 점은 접두사 관계가 입력 순서와 무관하게 성립한다는 것이다. 짧은 번호가 먼저 나오든, 긴 번호가 먼저 나오든 모두 잡아내야 한다. 기존에 실패했던 접근의 한계HashSet에 지금까지 등장한 번호만 넣고, 현재 번호의 prefix가 set에 있는지를 검사하는 방식은 이전 번호가 현재 번호의 접두.. [프로그래머스 JAVA] 짝지어 제거하기 https://school.programmers.co.kr/learn/courses/30/lessons/12973 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 문제 요약알파벳 소문자로 이루어진 문자열에 같은 문자열이 2개 붙어있다면 제거한다위 과정을 반복해서 문자열을 모두 제거할 수 있다면 1, 아니라면 0을 리턴한다.문자열의 길이는 1,000,000 (백만) 이하의 자연수 2. 내가 막혔던 지점처음에는 큐나 스택과 같은 자료구조를 사용하면문자열 길이가 최대 백만이기 때문에 메모리가 많이 들 것 같다는 걱정이 들었다.그래서 반복문으로 문자열을 순회하면서연속된 문자가 발견되면 substring을 이용해 .. [프로그래머스 JAVA] 피보나치 수 간단한 문제인데 long 자리수를 설마 넘어가나? 싶어서 오래걸렸다. 1. 문제 요약2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 구하는 문제이다.n은 100,000 이하의 자연수이다. 2. 내가 막혔던 지점n 이 재귀로 풀기엔 크기 때문에 반복문으로 접근하였고 Integer가 감당하지 못할꺼같아서 처음부터 long으로 풀었다. 제출했을때 중반부터 끝까지 쭉 틀리는것을 보고 이거는 오버플로우가 나는거같았지만 long 이상의 어떤 무언가를 표현하기에는 문자열로 해야하는데 그러면 시간이 너무 오래걸릴꺼같았다. 즉, long이상의 오버플로우를 해결하지 못했다. 3. 핵심아이디어 100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex... [백준 JAVA] 투포인터 모아풀기 마이다스 코테를 준비하면서 예전에 있던 문제들을 다시 풀어보았는데 투포인터에서 항상 막히고 못푸는 모습을 보였다.관련 문제들을 풀면서 이번기회에 제대로 한번 개념을 잡고가보도록 하자. 우선 투포인터란투 포인터(two pointers)는 배열에서 두 개의 인덱스를 이동시키며 조건을 만족하는 구간을 찾는 기법이다.주로 연속된 부분 배열 문제에서 사용되며, 이중 반복문을 O(N)으로 줄이기 위해 활용한다.핵심은 포인터가 한 방향으로만 이동한다는 점이다.왼쪽 포인터와 오른쪽 포인터는 각각 최대 N번 이동하므로 전체 시간 복잡도는 O(N)이다. 연속 부분합 문제에서 투 포인터의 기본 구성은 다음과 같다.l: 구간 시작 인덱스r: 구간 끝 인덱스 (보통 포함하지 않음)sum: 현재 구간의 합구간의 합(sum)을 유.. [백준 JAVA] 2138번: 전구와 스위치 https://www.acmicpc.net/problem/2138 문제 접근하는데 2틀정도 걸렸다. 원래는 이렇게 풀면 안돼고 30분 정도 고민해서 안나오면 풀이를 보고 넘어가야되는데 이번 문제는 왠지 내손으로 풀어보고 싶었다. 하지만 도무지 풀 방법이 생각이 나지 않아 해답을 보고 문제를 풀었다. 먼저 내가 했던 시행착오에 대해 먼저 설명하겠다. 1. 모든 스위치를 누르는 순열에 대하여 풀이 - 이 방법은 N의 갯수가 10만이기 때문에 애초에 불가능해서 포기하였다. 2. 스위치를 누르는 순서는 중요하지 않다 -> 어떤 스위치를 누르느냐만 결정하면됨 -> 조합 - 마찬가지로 N의 갯수가 10만이기 때문에 불가능한 해답이었다. 이후로는 그리디 하게 푸는 방법, 이진탐색으로 스위치를 누르는 횟수를 결정한 뒤.. [백준 JAVA] 2110번: 공유기 설치 https://www.acmicpc.net/problem/2110 N개의 집에 C개의 공유기를 놓을 때 가장 인접한 두 공유기 사이의 거리가 최대로 하는 문제이다. 제한 조건: N C 좌표 가장 간단하게 푼다면 경우의 수를 따져서 각각 공유기를 설치해본다음 거리를 계산하는 방법인데 시간복잡도가 nCc 이므로 너무 터무니없이 크다. 그래서 완전 다른 방법인 DP나 이분탐색, 투포인터로 사고를 전환했다. 하지만 고민해도 마땅한 방법이 떠오르지 않아서 GPT 한테 힌트를 달라고 요청했다. 이분탐색으로 풀어야한다는 말을 듣고 문제를 혼자 풀어보았다. 잘 안풀려서 보고 풀었다. import java.io.*;import java.util.*;public class Main { static int N, C;.. [백준 JAVA] 2075번: N번째 큰 수 https://www.acmicpc.net/problem/2075 처음에 가장 쉽게 풀 수 있는 방법을 떠올려 봤을 때 우선순위 큐에 모든 수를 넣고 N번 뺀 결과를 넣는것이었다. 우선 수의 갯수는 N 그래서 문제에 있는 조건인 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것을 이용해야 할 꺼 같았는데 우선 처음으로 가장 큰 수를 찾을때 맨 아래줄에서만 찾으면 된다. 그리고 그다음 큰 수를 찾을때는 이전에 찾았던 수는 바로 위에 칸에서 찾고 나머지는 다시 맨 아래줄에서 찾으면 된다. 따라서 해당 열을 몇번 방문했느냐를 int 배열로 관리해서 매번 N 개 만큼 찾으면 N * N 만에 찾을 수 있을꺼같아서 해당 방법으로 문제를 풀어보앗다. import java.io.*;import java.util... [백준 JAVA] 1987번: 알파벳 https://www.acmicpc.net/problem/1987 처음 접했을때 R, C가 최대 20이라 맵의 사이즈는 400이고 DP로 풀 수 있을지 확인을 했다. 하지만 이전 경로값이 이후의 선택값에 영향을 주므로 DP는 힘들꺼라고 생각했고 DFS 또는 BFS를 활용하여 문제를 풀어야겠다고 생각했다. 이전의 경로를 방문배열로 처리하려 했기 때문에 큐에 이 방문배열을 전부 들고다녀야하는 BFS 보다는 DFS가 좀더 효율적일꺼같아서 DFS 로 문제를 풀이하였다. import java.io.*;import java.util.*;public class Main { static int R, C, ans; static int[][] map; static int[] visited; stati.. 이전 1 2 3 4 ··· 31 다음