Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처빗물 골드 5 📖 문제 좀 헤맸던 문제다. 높이가 같거나 큰 것 중 작은 거를 기준으로 빗물을 담으면 되는데뭐를 기준으로 할 지가 문제였고, 높이가 줄어드는 형태에서도 문제였다.예제의 4 1 1 2 이 줄어드는 형태다. 각 블록을 기준으로왼쪽 오른쪽으로 같거나 큰 것을 찾는 거로 할려다가 중복 문제가 있어서 깔끔하게 버리고 왼쪽에서부터 기준을 잡고 오른쪽 포인터를 움직이면서왼쪽 포인터의 실제 값보다 작으면 스택에 담아두고 오른쪽 포인터의 실제값이 왼쪽보다 크거나 같으면  왼쪽 값과 오른쪽 값중 더 작은 것을 min값으로 설정하고스택에 넣었던 작은 블록들을 꺼내서 min - stack.pop() 한 값을 answer에 누적합한다.  문제는 높이가 줄어드는 형태인데이 경우 스택을 ..

🧫 문제 분석 ✔️ 출처주유소 실버 3 📖 문제 그리드(탐욕법) 문제로 매우 간단하다. 근데 가끔식 주어진 입력의 크기를 제대로 안봐서 놓치는 경우가 허다하다.  항상 지금 쓰려는 자료형이 적합한지 생각해야한다. 여기서는 리터랑 가격이 최대 10억, 도시 거리가 최대 10억이므로 long 타입으로 계산해주는것이 좋다.  주유소 가격의 최솟값을 도시를 지날때마다 갱신하면서구한 최솟값 * 거리 로 비용을 구한다.  예제 1번을 보면 처음 도시에서는 무조건 충전해야하므로 다음 도시까지 이동하는 최소한의 기름만 충전한다.2L충전 (5 * 2원) 다음 도시에서 이전 도시와 기름값을 비교해서 더 작다면 최솟값을 바꾸고 다음 거리만큼 주유한다.3L(2 * 3) 그 다음 도시에서는 이전 도시보다 비싸므로 이전 도시..

🧫 문제 분석✔️ 출처문자열 게임 2 골드 5 📖 문제 주어진 문자열의 알파벳의 위치 처리 문제다.  처음에는 투포인터로 하면 되겠나 싶었는데 말이 안되는 반례가 너무많이 생각나서 이 방법은 버리고, 각 알파벳의 ASCII 코드에서 'a'의 ASCII 코드를 빼서 0~25 범위의 인덱스로 변환한 후,배열(ArrayList[] list)의 해당 인덱스에 현재 문자열에서 해당 알파벳이 등장한 위치(인덱스)를 저장했다. 그리고 각 알파벳이 k개 이상이면k개씩 묶어서 거리를 구한 후 max, min 값을 갱신했다. 예제를 예시로w = "abaaaba" k = 3 일때list[0] = [0, 2, 3, 4, 6]; // 0 = 'a'알파벳 - 'a' 로 얻은 a알파벳의 인덱스 list[1] = [1, 5]..

🧫 문제 분석 ✔️ 출처크로스 컨트리 실버 3 📖 문제 등수 관련 문제 한 팀에 6명이 출전 , 6명이 안되면 점수 제외결승전 통과한 순서대로 점수를 받는다.각 팀의 4번째 선수까지 팀점수로 계산된다.가장 낮은 점수 팀이 우승이며 , 동점일경우 팀의 5번째 선수의 점수가 더 낮은 팀이 우승하게 된다.   로직은 쉽게 짰는데 map을 초기화해주는걸 까먹어서 이상한데서 자꾸 틀리다가 출력 찍어보니까 알았다...ㅋㅋ여러개의 테스트 케이스가 들어올때는 항상 조심하자..🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 1팀 = 6명 (상위 4명 점수 합) // 결승점을 통과한 순서대로 점수 받음 // 가장 낮은 점수 팀이 우..

🧫 문제 분석✔️ 출처리모컨 골드 5 📖 문제 부서진 버튼을 제외한 버튼들을 가지고 BackTracking으로 완전탐색해서 이동하려는 채널 길이와 가장 가까운 수를 찾는다. 이동하려는 채널 길이 - 1 ~ 이동하려는 채널 길이 +1 까지의 수를 찾는데 그 이유는 998  이문제 15% 와 32%에서 계속 틀렸었다. 15% 실패처음 백트래킹 메서드를 호출할때 매개변수로 깊이를 0, 숫자를 0으로 줘서 n = 1 이고0버튼이 부숴졌다고 했을 때 매개변수로 시작 숫자를 0으로 줘서 버튼이 부숴졌음에도 불구하고 if문에 걸려 바로 최솟값으로 반환되버렸다.  32% 실패단순 Math.abs(n - 탐색으로 찾은 수) Math.abs(n - 탐색으로 찾은 수), len = 현재 num의 길이 이런식으로 구하고탐..

🧫 문제 분석 ✔️ 출처뱀과 사다리 게임 골드 5 📖 문제 주사위를 굴려서 1~6까지 숫자를 현재 위치에 더하면서 BFS 탐색을 하면 된다. (최단 경로) 1차원 배열을 게임 판이라 생각하고 100칸을 만든다. x번 도착하면 y번 칸 이동 , u번 도착하면 v번 칸 이동 이므로왼쪽 입력을 인덱스로 사용, 오른쪽 입력을 값으로 사용한다.  BFS 탐색을 하면서 주사위를 굴려 이동할때 이동한 위치가map에서 값이 있다면 그 값으로 이동한다.  물론 방문 체크를 해줘야한다. 이 경우 특별한 이동방법이 없으므로 1차원 배열로 체크해주면 된다.  특별한 이동 방법을 쓰는 문제 포스팅 보러가기 백준 1600번 : 말이 되고픈 원숭이 자바 백준 2206번 : 벽 부수고 이동하기 자바  🔅 문제 풀이import ..

보통 String.matches, replaceAll 에 많이 사용하므로 거기에 맞춰서 정리1. 기본적인 정규 표현식 요소1.1 문자 클래스(Character Classes).임의의 한 문자 (개행 제외)[abc]a, b, c 중 하나[^abc]a, b, c를 제외한 어떤 문자[a-z]소문자 알파벳 한 글자 (a~z)[A-Z]대문자 알파벳 한 글자 (A~Z)[0-9]숫자 (0~9)[a-zA-Z0-9]영문 대소문자 + 숫자\d숫자 (0-9) (== [0-9])\D숫자가 아닌 문자 (== [^0-9])\w알파벳 또는 숫자 또는 _ ([a-zA-Z0-9_])\W\w가 아닌 문자 (공백, 특수 문자 등)\s공백 문자 (스페이스, 탭, 개행 등)\S공백이 아닌 문자1.2 앵커(Anchors)정규식설명^문자열의 시..

🧫 문제 분석 ✔️ 출처비밀번호 발음하기 실버 5 📖 문제 정규표현식 연습하고싶어서 풀게된 문제다.정규표현식은 매번 까먹기때문에 많이 해봐야하고 잘 숙지해야한다.  3번째 조건 ee, oo는 허용하면서 나머지 같은 글자 연속 2번을 제외하는게 조금 어려웠다. (결국 검색해봄..) 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static String[] eval = {"is acceptable.", "is not acceptable."}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader..

🧫 문제 분석 ✔️ 출처중량제한 골드 3 📖 문제 최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다.  이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 가장 비용이 큰 값을 max로 잡고 1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다. BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.이분탐색에서는 BFS 결과가 true이면 mid 값..

🧫 문제 분석 ✔️ 출처과자 나눠주기 실버 2 📖 문제 이 문제는 조카에게 최대한의 막대 과자 길이를 균등하게 나눠주는 것이 목표이다.  그러기 위해서는 적절한 과자길이를 찾아야하는데 여기서 이분탐색을 활용한다. 문제에서 알려줬듯이 과자를 하나로 합칠 순 없다.  예제 2번을 보면 왜 7인지 의문을 품을 수도 있다. 길이가 8이면 2 2 7 로 합치면 11이되는데 문제에서 여러 조각으로 나눠질 수 있지만 하나로 합칠 수 없다. 라고 나왔기에합치면 안된다. 이분탐색으로 적절한 길이를 찾고, 각 막대과자를 탐색한 길이로 나눈 개수가 조카M명을 넘는지 안넘는지 비교하면서 찾으면 된다.  나눠줄 수 없다면 0을 출력한다. 5 31 1 1 이런 경우 0이다.🔅 문제 풀이import java.io.*;impo..