import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; class Solution { public int[][] solution(int n, int[][] build_frame) { int[][] answer = {}; boolean[][] bar=new boolean[n+5][n+5]; boolean[][] plate=new boolean[n+5][n+5]; for (int[] ints : build_frame) { int x=ints[0]; int y=ints[1]; int isBar=ints[2]; //0:기둥 1:보 int isDelete=ints[3]; //0:d..
class Solution { public long solution(int n, int[] times) { long maxTime=0; for (int time : times) { maxTime=Math.max(maxTime,time); } long right=maxTime*n/times.length; long answer = right; long left=0; while (left
import java.util.*; class Solution { public int solution(int[][] routes) { int answer = 0; List routeList=new ArrayList(); for (int[] route : routes) { routeList.add(new Route(route[0],route[1])); } Collections.sort(routeList); int nowEnd=routeList.get(0).end; answer++; for (int i = 1; i nowEnd){ //need camera answer++; no..
class Solution { public long solution(int a, int b, int[] g, int[] s, int[] w, int[] t) { long left=0; long right=(long)(10e9*2*10e5*2); long answer = right; while (left=t[i]){ //현재 시간(mid)에서 왕복하고 남은 시간이 편도 보다 크거나 같다면 한번 더 가도 됨 move++; } //현재 시간만큼 왕복해서 자원을 채취한다 //현재 시간에 자원을 모두 캘 수 있다면 모두 캐고, 그렇지 않다면 캘 수 있는 만큼만 캔다 gold+=Math.min(g[i],move*w[i]); silver+=Math.min(s[i],move*w[i]); sum+=Math.min(g[i..
뭔가 문제를 보자마자 딱 떠오른 생각들이 전부 비효율적일거라 생각되어 쉽사리 접근하지 못했던 문제였다. 고민하다 선택한 방법은 매 회차에서 보석을 기준으로 새로운 집합을 만들어 검증할 리스트에 추가하고, 검증 리스트를 돌며 모든 보석을 모은 집합을 대상으로 최소 갱신을 한 후 해당 집합을 리스트에서 삭제하며, 이 과정에서 리스트에 있는 값들 중 현재 최소 거리보다 이미 큰 거리를 가진 집합들은 모두 삭제하였다. 이걸 주어진 보석 배열을 전부 순회하며 실행하면, 문제에서 요구하는 답을 얻을 수 있다. 하지만 이 코드 역시 시간초과가 났다. 모든 보석 배열을 순회하는데 그 안에서, pickedGemList를 계속 돌기에 효율적이지 않은 것이다.. 아래는 내가 제출했던 시간초과 코드이다. import java..
맨 앞,뒤는 해당 풍선을 제외하고 남은 풍선을 모두 큰 풍선만 골라 터트린다면 남은 풍선과 맨 앞(뒤)풍선 중 어떤게 크든 작든 아직 작은 풍선을 터트리는 기회가 남아 있기에 무조건 남길 수 있다. 여기서, 더 나아가면 3개의 풍선이 있다고 했을 때, 가운데 풍선이 양 옆의 풍선보다 크다면 절대 풍선을 남길 수 없다 ( 수가 더 작은 풍선을 터트리는 기회는 최대 1회 이므로) 여기서 잘 생각해보면 i번째 풍선을 남기기 위해선 0~i-1번째 풍선을 모두 수가 큰 풍선만 터트려 1개를 남기고 i+1~n번째 풍선을 마찬가지로 큰 풍선만 터트려 1개를 남긴 후 이 3개의 풍선을 비교하여 i가 제일 크다면 i번째 풍선을 절대 남길 수 없게된다. 이제 푸는 방법을 알았으니 코드로 구현해보면 배열을 0번부터 끝까지 ..
이 문제의 핵심은 "오른쪽과 아래쪽으로만"움직인다는 것이다 (이걸 안보고 처음 코드를 냈을 때 모든 테스트케이스를 틀려 많이 당황했었다..) i,j점을 오는 최단 경로는 i-1,j점까지의 최단경로+i,j-1까지의 최단경로가 되는 것이다. 로직 자체는 쉬우니 dp만 알면 이해가 될거라 생각한다. 우선 첫행, 첫열을 모두 1로 초기화하고 장애물이 첫행이나 첫열에 놓이면 그 밑의 경우의수를 모두 0으로 바꾼 후 2행부터 그리고 2열부터 끝까지 검사하는 방식으로 코드를 짜 제출했더니, 3~4개의 테스트케이스에서 실패하게 됐다.. 그러다, 질문게시판에서 그 이유를 찾게 되었다. 이런 코드라면 중간에 가는길이 막혔을 때 그 아래에 1로 초기화 된 값에 의해 최단 경로수가 0이 아닐 수 있다는 것이다. 사실, 장애물..
효율성 0점 코드 import java.util.Stack; class Solution { public String solution(int n, int k, String[] cmd) { String answer = ""; boolean[] isDeleted=new boolean[n]; Stack deleteStack=new Stack(); for (String command : cmd) { char c = command.charAt(0); if(c=='U'){ int count=Integer.parseInt(command.split(" ")[1]); int step=0; while (true){ if(isDeleted[--k]) continue; step++; if(step==count) break; }..
