GHY 's TechBlog

📍LEVEL1 : 시저 암호 유형 : 구현 📍풀이방법 입력값이 String 이고, 한 자리마다 n씩 움직여서 최종 결과값을 내야한다. 1) String의 한 자리씩 확인을 해야한다. -> char를 사용해야겠다고 생각. 2) 대소문자를 함께 입력받는다. -> 대소문자 구분을 해줘야겠다고 생각. 3) char는 int형으로 변경할 수 있고, 계산을 할 수 있기 때문에, 입력받은 n 과 각 자리 char 값을 더해준다. 4) z 또는 Z 를 넘어가는 범위는 있일 수 없기 때문에 a~z의 개수(=26)를 빼준다. (z or Z 범위를 벗어나게 된다면) 5) 영어 알파벳을 제외한 다른 문자(공백)도 들어갈 수 있기 때문에 예외로 처리해준다. 📍코드 class Solution { public String so..

[ 백준 ] 1753번 최단경로 문제풀이 feat. 자바 JAVA 문제 문제풀이방법 이 문제의 특징을 알아보자. 1. 방향이 있는 그래프이다. 2. 시작점이 주어지고 그 점에서 다른 점으로 가는 최단 경로를 구하는 문제이다. 3. 가중치가 존재한다. ( w는 10 이하의 자연수 ) -> 가중치가 양수이고, 특정점이 주어지고 다른 점으로 가는 모든 최단 경로를 구하는 조건들을 봤을 때, 이 문제는 전형적인 다익스트라 문제이다. 생각해볼만한 것 1. Queue를 써서 풀어도 되는 것 아닌가? - Queue를 사용한다는 것은 결국 BFS 구현이 된다. - 값이 작을 때는 문제의 해는 올바른 값을 도출한다. - 하지만, 시간초과가 날 것이다. 2. visited를 꼭 써야하나? ( 방문한 노드를 체크하는 것 )..

[백준] 1655번 가운데를 말해요 문제풀이 feat.자바 JAVA 문제 문제풀이방법 문제에서 요구하는 것은 수빈이가 어떤 수를 말할 때마다 그 수들의 가운데 있는 수를 찾아서 말하는 것이다. 그렇다면 어떻게 해야할까? 1. 단순히 생각했을 때, 입력값들을 저장해놓고 정렬을 한 후에, 가운데 있는 값을 찾아주면 된다. - 하지만, N의 범위가 100,000이고, 매번 정렬을 하는 것의 시간복잡도는 O(NlogN) -> 그러므로 총 시간복잡도는 N*N*logN이 될 것이고 시간초과 다. 2. 입력한 값 중에 중간 값들을 기억하고 있으면 어떨까? - 입력한 값의 작은값을 담는 공간 하나와, 큰 값들을 담는 공간 하나, 총 2개의 공간을 만들어 놓고, 두개의 공간에는 데이터의 수가 일정하게 유지시키면서 작은 ..

ACM Craft 문제풀이 방법 feat. 자바 문제 알아야 할 알고리즘 지식 위상정렬(Topological_Sort) 간단하게 말하자면, 방향이 있는 그래프를 정렬하는 것이다. 전후관계가 분명한 문제에서 방향이 있을 경우, 어떤 것이 먼저 사용될 수 있는지를 파악하여 문제를 풀어나가는 알고리즘이다. 추후, 위상정렬에 관한 알고리즘 포스팅 예정 문제풀이방법 글을 읽어보면, 건물을 건설하는데 순서가 있다고 한다. ex) 1번의 건물의 걸설이 완료되면, 2번과 3번의 건물을 건설할 수 있다. 이와 같은 경우, 방향이 존재한다. ( 1번다음엔 2번, 3번으로 가는 경우만 있다. 즉, 2번에서 1번으로 갈수 있는 경우는 없다. ) 전후관계가 분명하다. 전후관계가 없을 수도 있다. 이 경우에는, 언제 건설이 되어..

[백준] 19640번 화장실의 규칙 자바 코드 및 문제풀이 방법 문제설명 * 더 구체적인 예시는 아래 힌트를 확인하면 된다. 생각해야 할 요소 1. 사람들을 차례대로 M개의 라인으로 집어넣어야 한다. 2. 비교를 할 대상은, M개의 라인 중 첫번째에 위치한 사람들이다. 2-1. 비교 기준은, 고용기간이 오래된 사람 2-2. 고용기간이 같다면, 화장실이 급한사람 2-3. 같다면, line의 숫자가 앞에 있는 것 순서이다. 문제풀이 방법 1. 사람들을 차례대로 M개의 라인으로 집어 넣기 위해서 LinkedList[] 배열을 만들어서, 차례대로 넣어주었다. 2. pq에 조건에 해당하는 것을 Comparator 을 사용하여 정렬해주었다. 문제에서 요구하는 것은 PQ를 적절히 사용할 수 있는지, PQ를 본인의 입..

[ 백준 ] 1715번 카드정렬하기 자바 코드 & 문제풀이 방법 문제설명 생각해야 할 요소 1. 처음엔 문제가 이해가 잘 안갔다. 문제에서 정렬된 두 묶음의 숫자카드가 있다고 나와있는데, 이 말이 입력값이 정렬이 된 상태로 들어온다는 건가? 헷갈렸다. 2. 문제를 읽다가 생각해낸 풀이는, 최소한의 비교 횟수가 나오려면 숫자가 작은 것들끼리 더해야 한다는 한다는 것이었다. 간단하게 생각해서 처음 나온 숫자랑 두번째 나온 숫자는 N-1 번 나올거고, 그 다음은 N-2, N-3 나오는거 아닌가? 해서 풀었다. 결과는 틀렸습니다! 그 이유는, 다른 예시를 보면 이해가 확실히 갈 것이다. 백준에서 주어진 예시에는 (10 + 20 ) < 40 이라 한번에 캐치하기 어려웠을 수도 있다. 이 문제의 패턴은 더해진 숫자..

[백준] 연구소 14502번 - JAVA 문제설명 문제풀이과정 DFS로 벽 3개를 찾는다. BFS로 바이러스를 퍼뜨린다. 안전구역의 개수를 구한다. 안전구역의 개수의 최대값을 구한다. 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Lab_14502 { static int N, M, answer = 0; static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -..

[ 백준 ] 경쟁적 전염 18405- JAVA 문제풀이 문제설명 생각해야할 요소 1. 생각해줘야 할 포인트는 바이러스 번호가 낮은 숫자부터 시작하고 덮어쓰기가 안된다는 것이다. cf) BFS 문제인가? 맨처음 문제를 봤을 때 BFS라고 생각했지만, 문제를 풀다보니까 맞나? 싶기도 하고... 문제풀이 방법 1.사실 무척 간단하다. map을 순회하면서 내가 전이할 virus의 번호와 일치하는 것을 Queue에 몽땅 집어 넣어준다. - 큐에 들어있는 값의 상하좌우를 보고, map의 범위에 벗어나는것, 이미 그 칸을 점령하고 있는 바이러스가 있을 경우를 제외해주고 virus를 넣어주면 된다. 2. 시간이 오래 걸리지 않기 위해서 X,Y 위치에 값이 0이 아니라면 루프를 빠져나갈 수 있도록 했다. 소스코드 imp..

[백준] 치킨배달 15686 - JAVA 풀이 문제설명 생각해야할 요소 1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. ) 2. 치킨집을 어떻게 고를 것인가? ( 백트래킹, 조합 ) 3. 도시의 치킨 거리는 어떻게 구할 것인가? 문제풀이방법 1. 치킨집 중에서 최대 M 개를 고른다. ( M개보다 적게 고를 수 있다. ) - 이 부분은 문제를 풀다가 놓친 부분이다. ( 그냥 M개를 고르면 되는 줄 알았다. ) - 최대 M개라 하면, M보다 작은 수의 치킨집을 골라도 된다는 말이다. - 생각을 했을 때, M보다 작게 뽑게 된다면 치킨과 집간의 거리가 늘어날 것이고 결국 도시의 치킨 거리가 가장 작게 될지 구하지 못할 것이다. - 결국, 무조건 M개를 뽑아야 함을 알 수 있다. 2..

[프로그래머스] 무지의 먹방 라이브 - JAVA 문제설명 문제풀이 방법 일단, Collection.sort를 사용해서 먹는 시간이 가장 빠른 순으로 정렬 while문을 통해 빠른시간 순서대로 값을 빼내서 그 크기만큼 곱해준다. 코드 : ( foods.get(0).time - cnt ) * n while문의 조건식을 보면, 남은 k번을 돌아가는 데 있어, foods의 size가 더이상 줄어들지 않는 크기를 찾아낼 수 있다. 그렇게 하면 더이상의 작업을 할 필요없이 index를 구해주면된다. Food 클래스의 num(index) 순서대로 정렬하고, ( k % n ) 를 통해 num의 값을 찾아주면 된다. 내가 계속 틀렸던 이유 ArrayList를 사용했다. 사실, ArrayList를 사용한다고 문제가 발생하..