105번 쿼드압축 후 개수 세기
/*
문제 분석
1. 정보
- 0과 1로 이루어진 2^n * 2^n 크기의 2차원 정수 배열 arr이 있다고 가정하자.
- 다음과 같은 규칙으로 쿼드 트리와 같은 방식으로 압축 한다
- 특정 영역을 S라고 정의한다면
- 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축한다
- 그렇지 않다면 S를 정확히 4개의 균일한 정사각형 영역으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도한다.
2. 목표
- arr을 압축하였을 때, 배열에 최종적으로 남아 있는 0의 개수와 1의 개수를 배열에 담아 return
3. 제약 조건
- 1 <= arr 행의 개수 <= 1024
- arr의 각 행에 있는 모든 값은 0 또는 1
풀이
1. 아이디어
- 재귀? DFS방식 사용하여 풀이
- compute(0,0,n) : 0,0 부터 n의 길이를 가진 정사각형 범위를 탐색
- 만약 해당 범위가 모두 1이거나 0 이면, 해당 값 ++
- 아니라면,
- compute(x,y,n/2)
- compute(x,y + n/2,n/2)
- compute(x + n/2,y,n/2)
- compute(x + n/2,y + n/2,n/2)로 나누어서 진행
*/
class Solution {
int[] answer = new int[2];
public int[] solution(int[][] arr) {
int n = arr[0].length;
compute(0, 0, n, arr);
return answer;
}
private void compute(int x, int y, int n, int[][] arr) {
int num = arr[x][y];
if (isSame(x, y, n, arr)) {
answer[num]++;
return;
}
compute(x, y, n / 2, arr);
compute(x, y + n / 2, n / 2, arr);
compute(x + n / 2, y, n / 2, arr);
compute(x + n / 2, y + n / 2, n / 2, arr);
}
private boolean isSame(int x, int y, int n, int[][] arr) {
int num = arr[x][y];
for (int i = x; i < x + n; i++) {
for (int j = y; j < y + n; j++) {
if (arr[i][j] != num) {
return false;
}
}
}
return true;
}
}106번 택배상자
/*
문제 분석
1. 정보
- 영재는 택배상자를 트럭에 싣는 일을 한다.
- 실어야 하는 택배상자는 크기가 모두 같고, 1번 상자부터 n번 상자까지 번호가 증가하는 순서대로 컨베이어 벨트에 일렬로 놓여 영재에게 전달된다.
- 컨베이어 벨트는 한 방향으로만 진행이 가능하여 놓인 순서대로 상자를 내릴 수 있음
- 하지만 벨트에 놓인 순서대로 상자를 내려 트럭에 싣게 되면 기사가 배달하는 순서와 상자가 실려있는 순서가 맞지 않아 배달에 차질이 생김
- 만약 컨베이어 벨트의 맨 앞에 놓인 상자가 현재 트럭에 실어야 하는 순서가 아니라면, 그 상자를 트럭에 실을 순서가 될 때 까지 보조 컨베이어 벨트에 놓음
- 보조 컨베이어 벨트는 앞 뒤로 이동이 가능하지만 입구 외에 다른 면이 막혀 있어 맨 앞의 상자만 뺄 수 있다.
- 보조 컨베이어 벨트를 사용해도 기사님이 원하는 순서대로 상자를 싣지 못하면, 더 이상 상자를 싣지 않는다.
2. 목표
- 실을 수 있는 상자의 최대 개수를 return
3. 제약 조건
- 1 <= 상자 순서 <= 1000000
- 상자 순서는 1 이상 길이 이하의 모든 정수가 한번씩 등장
풀이
1. 아이디어
- 보조 컨베이어 벨트를 의미하는 stack을 하나 생성
- 만약 현재 원하는 순서에 맞는 상자가 들어온다면, 상자 쌓음(순서++)
- 원하는 순서의 상자가 들어오지 않는다면, stack에 저장.
- stack이 비어있지 않을 경우, stack.peek() 통해 원하는 순서의 값을 뽑을 수 있는지 확인.
- 뽑을 수 있다면, stack.pop 통해 해당 값 정리
- 순서++
- 만약 스택이 비어있지 않고, 원하는 값을 뽑지 못하였다면, 그대로 종료
*/
import java.util.Stack;
class Solution {
public int solution(int[] order) {
int answer = 0;
Stack<Integer> s = new Stack<>();
int idx = 0;
for (int i = 1; i <= order.length; i++) {
if (order[idx] == i) {
answer++;
idx++;
while (!s.isEmpty()) {
if (s.peek() == order[idx]) {
s.pop();
answer++;
idx++;
}else{
break;
}
}
}else{
s.push(i);
}
}
return answer;
}
}107번 큰 수 만들기
/*
문제 분석
1. 정보
- 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하여라.
2. 목표
- 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 주어질 때, 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return
3. 제약 조건
- 2 <= number 자리 수 <= 1000000
- 1 <= k < number 자리 수
풀이
1. 아이디어
- 그리디 알고리즘 및 스택 사용
- 스택에 가장 왼쪽 수부터 차례 대로 집어 넣음
- 만약 스택이 비어있지 않다면
- 현재 집어 넣을 값과 s.peek()값을 비교
- 집어 넣을 값이 더 크다면, s.pop()후 해당 값 push
- k--;
ex) 4177252841
- 4 / 4
- 1 / 1 4 (3)
- 7 / 7 4
- 7 / 7 7 4
- 2 / 2 7 7 4
- 5 / 5 7 7 4 (2)
- 2 / 2 5 7 7 4
- 8 / 8 5 7 7 4 (1)
- 4 / 4 8 5 7 7 4
- 1 / 1 4 8 5 7 7 4
k = 1 -> 1개 더 제거
-> 스택에 있는 가장 마지막 정수 제거 후 return
*/
import java.util.*;
class Solution {
public String solution(String number, int k) {
Deque<Character> s = new ArrayDeque<>();
for (int i = 0; i < number.length(); i++) {
while (!s.isEmpty() && s.peek() < number.charAt(i) && k > 0) {
s.pop();
k--;
}
s.push(number.charAt(i));
}
StringBuilder sb = new StringBuilder();
while (!s.isEmpty()) {
sb.append(s.pop());
}
sb.reverse();
if (k > 0) {
sb = new StringBuilder(sb.substring(0, sb.toString().length() - k));
}
return sb.toString();
}
}108번 삼각 달팽이
/*
문제 분석
1. 정보
- 정수 n이 매개변수로 주어진다.
- 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후 첫 행 부터 마지막 행 까지 모두 순서대로 합친 새로운 배열을 return
2. 목표
- 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후 첫 행 부터 마지막 행 까지 모두 순서대로 합친 새로운 배열을 return
3. 제약 조건
- 1 <= n <= 1000
풀이
1. 아이디어
- n * n 배열 선언
- 1. 아래로 내려감
- 2. 다 내려가면 오른쪽으로 감(0이 아닌 수가 나오기 전까지)
- 3. 다 같으면 왼쪽 대각선으로 쭉 올라감(0이 아닌 수가 나오기 전까지)
- 위 내용 반복 하여 다 채움
- 해당 배열을 새 int[]배열에 담아 return
*/
class Solution {
int[][] arr;
int[] dx = {1, 0, -1};
int[] dy = {0, 1, -1};
public int[] solution(int n) {
arr = new int[n][n];
int x = 0;
int y = 0;
int idx = 1;
int dir = 0;
int total = n * (n + 1) / 2;
while (idx <= total) {
boolean flag = false;
arr[x][y] = idx++;
int nx = x + dx[dir];
int ny = y + dy[dir];
if (isNotAvailable(nx, ny, n)) {
dir = (dir + 1) % 3;
nx = x + dx[dir];
ny = y + dy[dir];
}
x = nx;
y = ny;
}
int[] answer = new int[total];
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
answer[index++] = arr[i][j];
}
}
return answer;
}
private boolean isNotAvailable(int x, int y, int n) {
return x < 0 || x >= n || y < 0 || y >= n || arr[x][y] != 0;
}
}109번 연속된 부분 수열의 합
/*
문제 분석
1. 정보
- 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분수열을 찾으려고 한다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 한다.
- 부분 수열의 합은 k
- 합이 k인 부분 수열이 여러개인 경우 길이가 짧은 수열을 찾음
- 길이가 짧은 수열이 여러개인 경우 앞쪽에 나오는 수열을 찾음
2. 목표
- 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 k가 매개변수로 주어질 때 위 조건을 만족하는 시작 인덱스와 마지막 인덱스를 배열에 담아 return
3. 제약 조건
- 5 <= sequence의 길이 <= 1000000
- 1 <= sequence 원소 <= 1000
- 5 <= k <= 1_000_000_000
풀이
1. 아이디어
- start = 0, end 0으로 초기화
- sum을 선언하여 start ~ end 까지의 합을 저장
- start, end, size를 가지고 있는 객체 생성 및 List<객체>로 sum == k 일 경우 해당 값을 저장
- 만약 sum == k
- list에 start, end, size로 저장
- 만약 start == 길이 && end == 길이 이면
- 종료
- 만약 sum <= k && end < n
- end++;
- end < n 이면
- sum += sequence[end]
- 아니라면
- 만약 start < n 이면
- sum -= sequence[start]
- start++
- list 값을 구하였다면, 길이 오름차순, 시작 인덱스 오름차순으로 정렬
- list.get(0) 값의 start, end를 return
*/
import java.util.*;
public class Solution {
public int[] solution(int[] sequence, int k) {
int start = 0;
int end = 0;
int sum = sequence[0];
int n = sequence.length;
List<SubArray> subList = new ArrayList<>();
while (true) {
if (sum == k) {
subList.add(new SubArray(start, end));
}
if (start == n && end == n) {
break;
}
if (sum <= k && end < n) {
end++;
if (end < n) {
sum += sequence[end];
}
} else {
if (start < n) {
sum -= sequence[start];
}
start++;
}
}
Collections.sort(subList);
return new int[]{subList.get(0).start, subList.get(0).end};
}
private static class SubArray implements Comparable<SubArray> {
int start;
int end;
int size;
public SubArray(int start, int end) {
this.start = start;
this.end = end;
this.size = end - start;
}
@Override
public int compareTo(SubArray o) {
if (this.size == o.size) {
return this.start - o.start;
}
return this.size - o.size;
}
}
}
110번 두 큐 합 같게 만들기
/*
문제 분석
1. 정보
- 길이가 같은 두 개의 큐가 주어짐
- 하나의 큐를 골라 pop하고, pop한 원소를 다른 큐에 집어넣는 작업을 통해 각 큐의 원소 합이 같도록 만들려고 함
- 이때 필요한 작업의 최소 횟수를 구하고자 한다.
- 한번의 pop과 insert를 1회 수행한 것으로 간주
2. 목표
- 필요한 작업의 최소 횟수 return
3. 제약 조건
- 1 <= queue1의 길이 queue2의 길이 <= 300000
- 1 <= queue1의 원소 , queue2의 원소 <= 10^9
풀이
1. 아이디어
- 슬라이딩 윈도우 & 투 포인터 사용
- 각 큐의 합을 각각 구함
- 만약 두 큐의 합의 총합이 홀수라면 절대 같아질 수 없으므로 return -1
- 두 배열을 하나의 배열로 합침
- left = 0, right = 두번째 큐 시작점
- 두 큐의 합 / 2 가 목표
- 최대 이동 횟수는 3 * n -> 두 큐의 길이가 각 n이라면, 2 * n에 큐는 순환할 수 있으므로 n을 한번 더 해주어야 함.
- 따라서 3 * n
- 투 포인터를 사용하여 슬라이딩 윈도우 탐색 시작(0번부터 3*n까지)
- 만약 합이 목표와 같다면, answer return
- 만약 합이 목표보다 작다면,
- 현재 합에 right 위치의 값 추가
- right++
- 목표보다 크다면
- 현재 합에 left 위치의 값 뺌
- left++;
- answer++;
- 탐색을 다 해도 발견하지 못했다면 return -1
*/
class Solution {
public int solution(int[] queue1, int[] queue2) {
long sum1 = 0;
long sum2 = 0;
for (int i : queue1) {
sum1 += i;
}
for (int i : queue2) {;
sum2 += i;
}
long totalSum = sum1 + sum2;
if (totalSum % 2 == 1) {
return -1;
}
long targetSum = totalSum / 2;
int[] mergeQueue = new int[queue1.length + queue2.length];
int idx = 0;
for (int i : queue1) {
mergeQueue[idx++] = i;
}
for (int i : queue2) {
mergeQueue[idx++] = i;
}
int left = 0;
int right = queue1.length;
long curSum = sum1;
int maxOperations = queue1.length * 3;
int answer = 0;
while (answer <= maxOperations) {
if (curSum == targetSum) {
return answer;
}
if (curSum < targetSum) {
curSum += mergeQueue[right % mergeQueue.length];
right++;
}else{
curSum -= mergeQueue[left % mergeQueue.length];
left++;
}
answer++;
}
return -1;
}
}
문제 해결을 좋아하는 개발자 입니다 :)