📍 달팽이는 올라가고 싶다https://www.acmicpc.net/problem/2869   A와 V는 최대 10억이므로 단순히 반복문을 돌리면 시간초과 난다. (시간제한 0.25초)정상에 올라간 후에는 미끄러지지 않으므로 한 번 올라갔다는 가정하에 V-A를 한다.int answer = (V-A);   그 뒤로는 올라갔다 내려가는 것의 반복이므로 (A-B)로 나눈다. (Bint answer = (V-A) / (A-B);   최소한 하루는 올라가야 하는데 (1V와 A가 같을 경우 answer는 0이 되어버린다. 따라서 +1을 해준다.int answer = (V-A) / (A-B) + 1;   🎱 반례여기까지 작성하면 테스트케이스는 통과되지만 틀린 코드이다.// 반례5 1 8  반례의 경우, 달팽이가 ..

🔗 공원 산책 로봇 강아지가 공원 내 이동한 최종 위치를 계산하는 문제이다. 🥊 접근 방법 🥊단순 구현 문제이다. 주의할 점은 이동 조건이 맞지 않을 경우, 시작위치인 S로 이동하는 것이 아니라 바로 전 위치로 되돌아가야 한다. 이거때매 30점 맞고 한참을 고민했다 ㅜ ✨ 방법 1 ✨ (2024-07-08)0. 준비currPos : x, y의 현재좌표를 담을 Point 객체 타입의 변수originX : 이동하기 전의 X 좌표originY : 이동하기 전의 Y 좌표cnt : 이동 횟수를 체크하기 위한 변수x, y 좌표는 계속 사용되기 때문에 객체로 생성했다.static Point currPos;static int originX;static int originY;static int cnt;static ..

🔗 타겟 넘버 주어진 숫자 배열에서 각 숫자를 더하거나 빼서 특정 타겟 숫자를 만들 수 있는 모든 경우의 수를 찾는 문제로, 가능한 모든 조합을 탐색하기 때문에 완전탐색이다. 🥊 접근 방법 🥊numbers 값을 계속 더하다가 target 값이 안 나오면 빠꾸해서 값을 빼주면 되겠다고 생각했다. 비슷한 문제를 풀어본 적이 있어서 바로 DFS를 떠올렸다. DFSDFS를 사용해 각 숫자에 더하기(+), 빼기(-) 두 가지 경우 모두를 탐색한다.// basis partif(i == numbers.length){ if(total == target) answer++; return;} // inductive partDFS(numbers, target, i+1, total + numbers..

📍 벌집https://www.acmicpc.net/problem/2292   ✨ 방법1 ✨ 문제의 그림을 방별로 표시해보았더니 규칙이 보였다.  i >= 2 일 경우, 이러한 점화식이 나온다. 근데 dp 아니고 그리디였다.아무튼 dp의 크기를 N의 최대 크기인 10억으로 할 경우 메모리 초과가 난다.따라서 N이 10억일 때 결과값인 18258에 1을 더해 18259로 초기화했다.   ✨ 전체코드 ✨import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { ..

🔗 추억 점수사진 속 인물들의 이름과 그리움 점수를 기반으로 각 사진의 추억 점수를 계산하는 문제이다. photo에 name이 있으면 해당하는 점수(yearning)를 더하면 된다. 🥊 접근 방법 🥊보자마자 HashMap의 contains 메서드가 떠올랐다. 시간복잡도는 O(1)이다. 1. HashMapname과 yearning을 형태로 담기 위해 HashMap를 사용해 각 인물의 이름과 그 인물의 그리움 점수를 매핑한다.HashMap hash = new HashMap(); 2. 추억 점수 계산photo 배열을 순회하면서 각 사진에 대해 해당 사진에 등장하는 인물들의 그리움 점수를 합산한다. 이때, 사진 속 인물의 이름이 해시맵에 존재하는 경우에만 그리움 점수를 더한다.// photo 배열 순회f..

🔗 달리기 경주 선수들의 최종 순서를 계산하는 문제이다. 🥊 접근 방법 🥊player의 최대 길이가 5만, callings의 최대 길이가 100만이다. 단순히 players의 순서를 스왑하면 시간초과가 날 것이므로 ✅ HashMap을 떠올렸다. 참고로 HashMap을 사용하면 시간복잡도가 O(n^2) -> O(1)이 된다. 1. HashMapHashMap 를 사용해 각 선수의 이름과 그 선수의 현재 등수를 매핑한다. 인 이유는 Key에 따라 Value를 바꿔주기 위함이다.HashMap hash = new HashMap(); 2. 등수 업데이트callings 배열을 순회하면서, 부른 선수의 현재 등수를 확인하고, 그 선수와 바로 앞에 있는 선수의 등수를 바꾼다. 이때 HashMap을 사용해 각 선..

🔗 문자열 섞기✨ 전체코드 ✨class Solution { public String solution(String str1, String str2) { String answer = ""; for(int i=0; i 🌀 성능메모리 : 77.5 MB시간 : 9.24 ms   🔗 문자 리스트를 문자열로 변환하기🌟 방법1 : 반복문 🌟class Solution { public String solution(String[] arr) { String answer = ""; for(int i=0; i 🌀 성능메모리 : 76.6 MB시간 : 1.39 ms ✨ 방법2 : join 메서드 ✨✅ join 지린다class Solution { public..

🔗 올바른 괄호주어진 문자열 s가 올바른 괄호 문자열인지 확인하는 문제이다. 🥊 접근 방법 🥊24년 상반기 소프티어에서 비슷한 문제가 출제된 적이 있었다. 그때는 스택으로 풀었는데, 다른 사람의 풀이를 들어보니 단순 계산으로도 풀리는 문제였다. 비슷한 문제를 풀어봤기 때문에 금방 풀 수 있었다. ✨ 방법 1 : 단순 계산 ✨1. 기본 길이 체크괄호가 바르게 짝지어지려면 문자열의 길이는 무조건 짝수여야 한다.if(s.length() % 2 != 0) return answer; 2. 괄호 검사문자열의 각 문자를 확인하면서 '(' 문자가 나오면 cnt를 1증가시키고, ')' 문자가 나오면 cnt를 1 감소시킨다. 이 때 cnt가 음수가 되면 ')'가 '(' 보다 먼저 나왔다는 뜻이므로 올바른 괄호가 아니..

🔗 덧셈식 출력하기✨ 전체코드 ✨import java.io.*;import java.util.*;public class Solution { public static void main(String[] args) throws IOException{ BufferedReader sc = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(sc.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); System...