본문 바로가기

Algorithm

 (140)
Programmers - 기둥 과 보 설치 with JAVA 로직 1. 설치 연산시 -> 우선 설치 후, 모든 구조물이 괜찮은지 확인 -> 괜찮지 않다면 삭제 2. 삭제 연산시 -> 우선 삭제 후, 모든 구조물이 괜찮은지 확인 -> 괜찮지 않다면 설치 모든 구조물이 괜찮은가? 1. 기둥 : 땅 위에 있거나 보 위에 있거나 기둥 위에 있으면 괜찮다. 2. 보 : 기둥 위에 있거나 양쪽으로 보가 연결되어 있으면 괜찮다. 코드 import java.util.*; class Solution { public List solution(int n, int[][] build_frame) { List answer = new ArrayList(); for(int[] frame : build_frame){ int x = frame[0]; int y = frame[1]; int stu..
Programmers - 리코쳇 로봇 with JAVA 로직 1. 미끄러져 방문한 노드는 방문처리해서 다시 방문하지 않아도 된다. 2. 시작점, 목표점 또한 방문 가능한 노드임을 인지한다. 코드 import java.util.*; class Solution { public int solution(String[] board) { int answer = -1; int x_len = board.length; int y_len = board[0].length(); int[] start = new int[2]; int[] end = new int[2]; int[] dx = {-1, 0, 1, 0}; int[] dy = {0, -1, 0, 1}; for(int i=0; i 0){ List now = queue.poll(); int cost = now.get(0); in..
Programmers - 표편집 with JAVA (V) 해결 이 문제는 시간복잡도를 고려해야하는 문제이다. ArrayList나 Map 등 다른 것들을 사용해서 해결하려고 했지만 시간복잡도에서 문제가 생겼고 구현하기도 어렵다. LinkedList로 해결을 하였고 코드는 아래와 같다. 원리적으로는 저장공간을 늘려 검색이나 삭제등의 복잡도를 줄이는 원리를 통해 시간복잡도를 전체적으로 줄인다. 코드 import java.util.*; class Solution { static class Node{ public Node prev; public Node next; public boolean isDeleted = false; } public static String solution(int n, int k, String[] cmd) { Stack deleted = new ..
Programmers - 풍선 터트리기 with JAVA 문제 풍선마다 서로 다른 번호를 가지고 있으며 해당 조건에 따라 풍선을 터트리고자 한다. 조건 1. 인접한 풍선 중에 하나를 터트릴 수 있다. 조건 2. 숫자가 큰 풍선을 터트리되 한번은 숫자가 작은 풍선을 터트릴 수 있다. 이러한 경우, 마지막까지 살아남을 수 있는 풍선의 개수를 구하라. 로직 1. 마지막까지 살아남을 수 있는 풍선을 기준으로 왼쪽의 풍선 중 가장 번호를 작은 풍선의 번호를 구한다. = left_min 2. 마지막까지 살아남을 수 있는 풍선을 기준으로 오른쪽의 풍선 중 가장 번호를 작은 풍선의 번호를 구한다. = right_min -> 만약, 해당 풍선의 번호가 두 변수보다 작다면 해당 풍선 제거 가능 -> 만약 둘 중 하나보다 작다면 풍선 제거 가능 -> 만약 둘 모두보다 크다면 제거..
Programmers - 입국 심사 with JAVA (V) 문제 심사관들이 각각 한명을 심사하는데 걸리는 시간들이 주어지고 대기자 명수가 주어진다. 모든 사람을 검사하는데 걸리는 가장 짧은 시간은?? 로직 기본적으로 대기자수의 범위가 너무 크기때문에 자료구조를 활용하는 등의 방법은 시간 초과의 문제가 있다. 따라서 이분탐색을 사용한다. 1. s_time : 총 검사 시간의 최소값 - 1 2. e_time : 총 검사 시간의 최대값 - 배열의 가장 큰 수 * 사람 수 3. 이분 탐색 시작 (의미 : 해당 시간만큼 검사를 진행한다면 몇명을 검사할 수 있는지 확인) -> 해당 시간만큼 검사시 검사해야하는 사람을 모두 검사하지 못한다면 ? s_time = n_time + 1; -> 해당 시간만큼 검사시 검사해야하는 사람을 모두 검사한다면? e_time = n_time ..
Programmers - 경주로 건설 with JAVA 문제 맵이 주어지고 왼쪽 위 끝에서 오른쪽 아래 끝까지 도달한다. 맵에는 길이 있고 벽이 있다. 벽을 피해서 지나야 한다. 또한 직선 도로로 갈 시 100, 한번 꺾을 때마다 500의 cost가 발생한다. 가장 적은 cost를 사용하여 목표지점까지 도달한다. 로직 기존의 유사한 문제와 다른 점은 cost 조건이 상이하다는 점과 벽이 존재하는데 기존의 방문한 곳을 재방문 하는 것을 방지하는 로직이나 현재 확인하고자 하는 cost 보다 작으면 방문하지 않는 로직을 그대로 사용할 수 없다는 점이다. 그렇다면 결과적으로 최소값을 구할 수 없기 때문이다. 따라서 cost보다 작으면 방문하지 않는 로직을 사용하되, 기존보다 유하게 cost 판단을 해 이를 해결하였다. 코드1 import java.util.*; cl..
Programmers - 가장 큰 정사각형 찾기 with JAVA (V) 문제 0, 1로 이루어진 2차원 배열이 주어진다. 이 때, 1로만 이루어진 정사각형의 넓이 중 가장 큰 넓이를 반환하라. 로직 해당 문제는 DP로 해결을 했다. 처음에는 DP를 항상 일차원적으로만 해석해왔기에 DP라는 아이디어를 떠올리기조차 어려웠다. 하지만 완탐을 하기에는 시간복잡도를 고려해보았을 때, 불가능하다. DP 아이디어는 "현재 x,y좌표에 맞는 최대 넓이는 (x-1, y), (x, y-1), (x-1, y-1)에 해당 하는 값의 최소값 + 1이다." 예를 들어보면, 아래와 같은 2차원 배열이 있다고 가정하자. 매번 1이 나올때마다 체크한다. 0111 1111 1111 0010 (0, 1)까지의 최대 넓이는 1이다. (0, 2)까지의 최대 넓이는 1이다. (0, 3)까지의 최대 넓이는 1이다...
Programmers - 줄 서는 방법 with JAVA 문제 1~n번 까지 번호를 갖는 사람이 있다. n은 20이하의 자연수이다. 사람을 사전순으로 나열할때, k번째 줄은 어떤 순서인가? 로직 사실 이 문제는 효율성 테스트에서 애를 많이 먹었다. 하지만 로직에 문제가 있던게 아닌 long이 아닌 int를 사용해서 오류가 낫던 것이다. 이런 실수를 줄이는 게 중요한 것 같다. 로직은 간단하다 예를 들어, 20명이 줄을 선다면, 19! 간격으로 앞자리가 바뀐다. 이 아이디어만 고려하면 된다. 항상 자료형을 신경쓰자 !! 코드 import java.util.*; class Solution { public List solution(int n, long k) { List answer = new ArrayList(); List check = new ArrayList()..

티스토리툴바