Algorithm (140) 썸네일형 리스트형 Programmers - 파괴되지 않은 건물 with JAVA (V) 문제 2차원 배열이 주어진다. 그리고 각 스킬들이 주어지는데 스킬은 공격, 회복 두 개로 나뉜다. 공격시에는 해당 범위만큼 2차원배열에서 특정 값을 빼고 회복시에는 해당 범위만큼 2차원 배열에서 특정 값을 더 해준다. 결과적으로 배열에서 1보다 큰 칸의 개수를 구하라. 로직 첫번째로 굉장히 쉬워보이는 문제지만 요구사항을 확인해보면 배열 한 행과 열의 크기는 최대 1000, skill의 개수는 최대 25000이다. 따라서 25000 * 1000 * 1000, O(KNM)의 시간복잡도로는 효율성 테스트를 통과할 수 없다. (스킬 수 K, 맵의 가로 N, 맵의 세로 M) 누적합을 통해 해결하고자 한다. 로직은 우선 아래와 같다. 1. 스킬마다 누적합을 위한 값을 구한다. O(K) 2. 구한 누적합으로 최종 누.. Programmers - 가장 긴 팰린드롬 (V) 문제 문자열 s의 부분 문자열 중 앞뒤를 뒤집어도 똑같은 문자열 중 가장 긴 문자열을 구하라. 로직 1. s의 길이를 구한다. 2. s의 초기 길이부터 1을 빼가며 진행 3. 앞뒤로 같은지 판단하고 같으면 종료 이 문제는 어렵지 않지만 효율성에서 .substring, .StringBuilder의 reverse, 등을 활용해 경우마다 부분문자열을 구하는 것보다는 인덱스를 통해 비교하는 것이 더 효율적이라는 것을 기록하기 위해서 작성한다. 코드 class Solution{ public int solution(String s){ int length = s.length(); while(true){ if(length Programmers - 징검다리 건너기 with JAVA (V) 문제 징검다리의 칸마다 건널 수 있는 횟수가 정해져 주어지고 사람이 건너 뛸 수 있는 칸의 수가 주어진다. 이 때, 최대한 많은 사람들이 건너게 하고자 할 때, 최대 몇명이 건널 수 있는가? 로직 이 문제에 대해서 많은 고찰이 있었다. 시간 복작도를 충분히 고려해야하는 문제이다. 첫번째 생각했던 방법은 0~k, 1~k+1마다 최댓값을 구하고 이 최댓값들 사이의 최솟값이 정답이 되는 로직을 설정하였다. 이는 시간복잡도에서 큰 문제를 갖는데 매 순간 정렬을 해줘야 하기에 문제가 생긴다. 따라서, 이분탐색으로 해결을 하였다. 1. 주어진 배열 정렬해 리스트에 담는다. 2. 이분 탐색으로 숫자를 정해가며 해당 리스트에서 지금 값을 뺐을 때, k보다 작거나 같거나 크거나를 고려하여 start, end 인덱스를 변.. Programmers - 124 나라의 숫자 with JAVA 문제 124나라의 숫자는 아래와 같이 표현된다 1 - 1 2 - 2 3 - 4 4 - 11 5 - 12 6 - 14 n을 124나라의 숫자로 표현하라. 로직 설명하기 어렵지만 설명하자면.. n에서 누적합(sum)을 빼고 3의 현재 배수(now)로 나눈 값이 3의 전의 배수(before)보다 (0보다 크지만 before보단 작다, before보단 크지만 before의 2배보다 작다 , before의 2배보다 크거나 0과 같다.)에 따라 1, 2, 4가 추가되고 만약 sum+now가 n보다 크다면 종료된다. 예를 들어서 보면 아래와 같다. (n = 15, sum = 0) now = 3의 1의 배수 = 3 before = 3의 0의 배수 = 1 (n-sum)이 before의 값에 따라 1, 2, 4 중 하나로.. Programmers - 삼각 달팽이 with JAVA 문제 반시계방향으로 1층부터 n층까지 채워 피라미드를 만든다. 로직 - 재귀함수를 사용한다. - 아래로 가는경우(x+1), 위로가는 경우(x-1, y-1), 옆으로 가는 경우(y+1) 로 나누어 차례대로 돌린다. 코드1 import java.util.*; class Solution { public List solution(int n) { List answer = new ArrayList(); int[][] map = new int[n][n]; find(0, 0, 0, 1, n, map); for(int i=0; i Programmers - 쿼드압축 후 개수 세기 with JAVA 문제 2의 N승 X 2의 N승 크기의 배열이 주어지고 이 배열은 0 또는 1로 이루어진다. 이 때, 연속적으로 4만큼 배열을 나누어 해당 범위안에 모든 숫자가 같으면 묶을 수 있다. 묶게 된다면 해당 그룹은 모두 0 또는 1 하나로 묶인다. 이 때, 0의 개수와 1의 개수를 구하라. 로직 1. 초기 배열의 크기를 구한다. 2. 4등분 한다. 3. 4등분한 각 파트가 모두 0이거나 1인지 확인한다. 4. 3번이 참이라면 0 또는 1을 결과로 증가시킨다. 5. 3번이 거짓이라면 해당 범위를 다시 4로 나누어 반복한다. 추가적으로, 만약 초기 값이 모두 같은 값인지 처음에 체크해 같다면 0또는 1을 1개로해서 반환한다. 코드 1 class Solution { public static int[] answer =.. Programmers - 자물쇠와 열쇠 with JAVA 문제 자물쇠와 열쇠가 주어지고 열쇠는 회전이 시계방향으로 90도 회전이 가능하다. 자물쇠와 열쇠의 상호간 돌기와 홈이 딱 맞으면 자물쇠를 풀 수 있다. 해당 열쇠로 자물쇠를 풀 수 있는지 판단하다. 로직 1. 맵 생성 - 자물쇠 크기의 3배로 설정 2. 맵에 자물쇠 설치 3. 키를 0도 - 90도 - 180도 - 270도 회전, 총 4회 반복 4. 키는 0,0으로 시작해 (0, 1), (0, 2) .... (1, 0), (1, 1) 과 같이 이동을 한다. (+연산을 통해 키 움직임) 5. 이동시마다 자물쇠가 풀리는지 체크 6. 키 제거 (- 연산을 통해 키 제거) 추가적으로, 키와 자물쇠가 만나 2가되면 열리지 않는걸로 처리한다. 추가적으로 회전 함수는 암기해두는 것이 좋다. new_key[y][x의길이.. XOR 연산 with JAVA XOR 연산을 위한 코드를 기록해두려고 한다. 아래 코드는 순서대로 리스트의 값들을 XOR 연산하는 코드이다. public static int getXOR(List result) { int sum = result.get(0); for (int i = 1; i < result.size(); i++) { sum ^= result.get(i); } return sum; } 이전 1 ··· 4 5 6 7 8 9 10 ··· 18 다음
