은비블로그

[프로그래머스] Level2 : 타겟 넘버 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr [풀이과정]처음엔 visited를 사용해서 -로 사용할 부분을 체크해서 계산했는데, 이렇게 되면 같은 케이스인데 다르게 취급되어서 중복된 값처리가 이루어지는 로직이었다.그냥 단순하게 풀면 되는 거였음.. 생각을 깊게 하고 버릇처럼 코드 짜는 걸 반성했다. [코드]import java.io.*;class Solution { static int cntNumbers, answer, targetNum; public int solution(i..

[프로그래머스] Level2 : 다리를 지나는 트럭 (JAVA)

https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr [풀이과정]테케로 문제 이해를 해야 해서 좀 힘들었다.바보처럼 이해를 못 해서 엄청 헤맸음..ㅠㅜ 그렇게 어려운 문제는 아니었는데queue를 이용했고 그냥 주어진 순서대로만 무게 되는지 체크해서 트럭 올려두면 된다 [코드]import java.io.*;import java.util.*;class Solution { public int solution(int bridge_length, int weight, int[]..

https://www.acmicpc.net/problem/16139 [풀이과정]처음엔 구간을 나눠서 탐색했는데 50점 받았다.값이 엄청 커져도 제대로 수행되려면 탐색을 줄여야 했기 때문에 누적합 방식으로 풂. 이게 맞는 방식이었다.알파벳이 26개이니까 한 번의 탐색으로 str.index까지 알파벳이 몇 개 있는지 저장했고(l, r) -> l - (r-1) 으로 값을 구했음 [코드-100점]import java.io.*;import java.util.*;/*특정 문자열, 특정 알파벳과 문자열의 구간 [l,r]특정 알파벳이 몇 번 나타나는지 구하기 */public class Main { static BufferedReader br = new BufferedReader(new InputStreamRead..

https://www.acmicpc.net/problem/10799 [풀이과정]막대기를 자르는 레이저의 개수 + 1만큼 막대기가 증식함. 1) '(' 일 때stack에 넣어줌 2) ')' 일 때 -> 두 가지 경우로 나뉨먼저 pop해서 '('를 제거2-1) 레이저의 끝일 때stack에 있는 막대기 모두를 자르기 때문에 +stack.size를 해줌 2-2) 막대기의 끝일 때+1 해주기 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;/*쇠막대기를 겹침.자신보다 긴 막대기 위에만 놓일 수 있..

https://www.acmicpc.net/problem/11048 [풀이과정]점화식으로 안 풀어서 시간초과 났었음 ㅠㅠ 1. DP 값을 채워넣는 공간은 (1,1) ~ (N,M)2. 왼쪽, 위, 왼쪽위대각선 값 중 가장 큰 값을 가져오면서 값을 채움3. (0,0)~(N,M) 크기의 그래프로 계산 [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*NxM 미로가장 왼쪽 윗 방 (1,1), 가장 오른쪽 아랫 방 (N,M)각 방에는 사탕이 있음현재 위치 (1,1)에서 (N,M)으로 이동하려 할 때(r,c)에 있으면 아래,오른쪽,오른쪽..

https://www.acmicpc.net/problem/1463 [풀이과정]DP문제. N을 index로 두고DP[N]를1 ) 3으로 나뉠 때 -> DP[N/3] + 12 ) 2로 나뉠 때 -> DP[N/2] + 1 3 ) -1 할 때 -> DP[N-1] + 13가지 중 가장 작은 값으로 갱신하며 채우기. [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;/*1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. */public class Main{ static Bu..

https://www.acmicpc.net/problem/11726 [풀이과정]전형적인 DP 문제다. 점화식으로 풀면 됨.직접 타일을 그려보면  f(n-1)의 가짓수에 세로 타일을 하나씩 붙이고 + f(n-2)의 가짓수에 가로 타일 2개가 붙은 모양임f(0) = 1, f(1) = 1 이고f(n) = f(n-2) + f(n-1) [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*2xn 크기의 직사각셩을 1x2,2x1 타일로 채우는 방법의 수 구하기 */public class Main { static BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/30470 [풀이과정]stack을 사용하였고 max가 갱신될 때마다 stack에 저장된 값들을 확인하면서 길이를 갱신하며 pop, push를 해주었는데 틀림. 로직은 맞는 것 같은데 왜 틀린지 잘 모르겠음.정답코드는 max 갱신 시마다 값을 확인하는 로직을 없앰. 새로 추가되는 통나무가 항상 제일 긴 통나무이고 max 값을 기준으로 통나무 길이가 갱신되는 것이기 때문에 max값만 저장해준 후 sum 값을 구할 때 로직 실행해켜주면 됨. [코드]import java.io.*;import java.util.*;public class Main { static BufferedReader br = new BufferedReader(new InputSt..

https://www.acmicpc.net/problem/2631 [풀이과정]전형적인 LIS 문제였다. N이 200으로 작아서 O(N^2)인 DP 방식으로 풀이했음.N이 커지면 O(nlogn)인 이분탐색으로 풀이해야 한다. 현재 탐색 중인 번호의 이전 번호들을 보면서 더 크면 DP[현재 번호] = DP[이전 번호 중 가장 큰 값을 가진 번호] + 1을 해주는 것  [코드]import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;/*N명의 아이들1번부터 N번. 옮기는 순서를 최소로 하여 일렬로 정렬 */..

https://www.acmicpc.net/problem/22869 [풀이과정]단순히 도달여부를 확인하기만 하면 되는 문제.O(N^2)이 2500만이어서 DFS로 풀었다가 시간초과가 발생했다. 단순히 N^2이 아닌 실제로 호출되는 함수가 컸던 부분이 원인이었음.DP를 이용해서 도달 가능한 부분만을 true로 삼아 경로를 확인하는 방식으로 호출 횟수를 줄임. [코드]import java.util.*;import java.lang.*;import java.io.*;/*사용하는 힘은 항상 양수.오른쪽으로 갈 때 사용해야 하는 힘이 K가 넘지 않을 때 이동 가능끝까지 도착이 되는지의 유무 계산*/class Main { static BufferedReader br = new BufferedReader(new..