[5번째 알고리즘 모임] 4문제
점점 회차 가 진행될수록 코드를 작성하는 시간보다 생각하는 시간이 더 길어졌다.. 몇 줄 적지 도 못한 문제도 있고 생각만 하다 종료된 문제도 많았다. 바로 문제 풀어보자.
문제 1 색종이 만들기 (백준 2630, Java)
풀러 가기
전형적인 재귀 문제라고 생각한다. 4등분을 해서 타고 타고 타고 비교 가능한 최소 단위까지 타고 들어가서 비교를 시작해 가면서 밖으로 나가면 된다.라고 생각하고 한참 고민했다 코드를 작성하는데.... 특히 좌표를 어떻게 넘겨주어야 할까? 를 제일 많이 고민했던 부분이다. 지난번 제로베이스 1차인가 2차 코테 당시 4번 문제를 사분면으로 나눠서 풀었던 기억이 남아있어 어렵지 않게 접근은 가능했으나... 시간 안에 풀지 못했다... 문제를 푸는 데 있어 1시간 정도 걸렸던 것 같다.
코드를 보자.
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int[][] arr = new int[N][N];
for (int i = 0; i < N; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
arr[i][j] = Integer.parseInt(inputs[j]);
}
}
bf.close();
Boj b = new Boj();
b.main(arr);
}
}
class Boj {
int white = 0;
int blue = 0;
int[][] arr = {};
public void main(int arr[][]) {
this.arr = arr;
helper(0, 0, arr.length);
System.out.println(white);
System.out.println(blue);
}
public void helper(int row, int col, int n) {
if (checker(row, col, n)) {
if (arr[row][col] == 0) {
white++;
} else {
blue++;
}
return;
}
int half = n / 2;
helper(row, col, half);
helper(row, col + half, half);
helper(row + half, col, half);
helper(row + half, col + half, half);
}
public boolean checker(int row, int col, int n) {
int target = arr[row][col];
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (arr[i][j] != target) {
return false;
}
}
}
return true;
}
}전반적인 아이디어는 위에 작성한 대로 4 등분해서 넘겨줄 방법과 좌표를 처음 시작점을 넘겨주는 것에 착안해서 작성했다.
또한 함수 탈출 조건을 위한 한 개 의 종이를 이용해 색구분을 확인하고, 현재 진행 중인 재귀의 색 분별을 통해 재귀 종료 혹은 다음 재귀로 넘겨주는 것이다.
적다 보니 말 몇 줄 안되는걸 약 1시간 동안 이리저리 구른 나를 생각하니 화가 난다.
helper 함수를 재귀적 호출할 메인으로 삼고 이 친구를 4등분 나눠주면서 진행한다. checker를 안에 넣어서 확인하려고 했으나 코드가 길어져서 함수로 따로 빼주었다. 따로 특이한 점 없는 코드다.
나머지 분들 코드도 이와 매우 유사해 코드 가져오신 분의 보다 직관적인 코드를 소개하고자 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Practice094 {
static int[][] arr;
static int blueCnt, whiteCnt, gap;
static boolean cutFlag;
// cut 풀이에 추가로 필요한 변수
static int[] leftUpIdx, rightDownIdx;
// cut2 풀이에 추가로 필요한 변수
static int x, y;
public static void solution(int gap) {
cut(new int[]{0,0}, new int[]{gap - 1, gap - 1}, gap - 1);
System.out.println(whiteCnt);
System.out.println(blueCnt);
}
public static void cut(int[] leftUpIdx, int[] rightDownIdx, int gap) {
cutFlag = false; // 초기화
// 1칸짜리 종이임
if(Arrays.equals(leftUpIdx, rightDownIdx)) {
if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
blueCnt++;
} else {
whiteCnt++;
}
return;
}
// 다른 숫자가 있으면 잘라
for (int i = 0; i <= gap; i++) {
for (int j = 1; j <= gap; j++) {
if(arr[leftUpIdx[0] + i][leftUpIdx[1]] != arr[leftUpIdx[0] + i][leftUpIdx[1] + j]) {
cutFlag = true;
break;
}
}
if(i < gap && arr[leftUpIdx[0] + i][leftUpIdx[1] + gap] != arr[leftUpIdx[0] + i + 1][leftUpIdx[1]]) {
cutFlag = true;
break;
}
if(cutFlag) {
break;
}
}
// 잘라야 하면
if(cutFlag == true) {
gap = (rightDownIdx[0] - leftUpIdx[0]) / 2; // gap은 종이의 가로&세로 사이즈
int next = gap + 1; // next는 다음 종이까지의 인덱스 차이
cut(new int[]{leftUpIdx[0], leftUpIdx[1]}, new int[]{leftUpIdx[0] + gap, leftUpIdx[1] + gap}, gap); // 왼쪽 위
cut(new int[]{leftUpIdx[0], leftUpIdx[1] + next}, new int[]{rightDownIdx[0] - next, rightDownIdx[1]}, gap); // 오른쪽 위
cut(new int[]{leftUpIdx[0] + next, leftUpIdx[1]}, new int[]{rightDownIdx[0], rightDownIdx[1] - next}, gap); // 왼쪽 아래
cut(new int[]{rightDownIdx[0] - gap, rightDownIdx[1] - gap}, new int[]{rightDownIdx[0], rightDownIdx[1]}, gap); // 오른쪽 아래
} else {
if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
blueCnt++;
return;
} else {
whiteCnt++;
return;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
gap = Integer.parseInt(br.readLine());
arr = new int[gap][gap];
for (int i = 0; i < gap; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < gap; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
solution(gap);
}
}
구현에 있어 어려운 좌표 해결을 위와 같이 배열에 좌표를 담아 앞뒤로 넘겨준다. 처음 이렇게 시도하다가 좌표를 계산에 머리가 고장이 나서 지우고 다른 방법으로 접근했다. 구현하려고 하다 실패한 부분을 다른 사람의 코드로 보니 다음에 어떤 식으로 접근해야 할지 영감을 받았다.
문제 2 H-Index(프로그래머스 , Java)
문제를 읽자 자자 읭?이라는 소리가 나온다. ㅋㅋㅋ
우리 위키의 보다 많은 예시를 보고 조금 더 이해에 근접하게 접근할 수 있다. 최초 접근 방법으로는 정렬 후 이분 탐색을 통해 가운데 값을 이용해 접근하려 했으나 대차게 실패했다. ㅋㅋㅋㅋ
문제 가져오신 분의 코드를 보자.(출처 https://oranthy.tistory.com/241)
import java.util.*;
// 프로그래머스 lv 2 H-idx
//
public class Test1 {
public static int solution(int[] citations) {
int answer = 0;
Arrays.sort(citations); // arr2 = [0 1 3 5 6 7 9]
System.out.println();
System.out.println(Arrays.toString(citations));
for(int i = citations.length - 1; i >= 0; --i) {
int H = citations.length - i; // 크거나 같은 것들의 개수
if (H == citations[i]){
return H;
}else if(H > citations[i]) {
return H - 1;
}
if(i == 0){
return H;
}
}
return 0;
}
public static void main(String[] args){
int[] arr1 = {3, 0, 6, 1, 5};
int[] arr2 = {0, 1, 3, 5, 6, 7, 9}; // 정렬 후: 0 1 3 5 6 7 9
int[] arr3 = {3, 0, 6, 1, 5, 2, 4, 7, 8}; // 0 1 2 3 4 5 6 7 8
int[] arr4 = {3, 0, 6, 1, 5, 2, 4, 7, 8, 10, 11, 12, 13}; // 0 1 2 3 4 5 6 7 8 10 11 12 13
int[] arr5 = {0, 1, 3, 5, 6, 7, 9}; //
int[] arr6 = {1, 3, 4, 2, 6, 7,8, 10, 13, 14, 8, 12}; //
int[] arr7 = {1, 2, 3, 16, 17, 18, 19, 20, 21, 22, 23, 8000, 9000, 9500, 10000}; //
System.out.println(solution(arr1)); // 3
System.out.println(solution(arr2)); // 4
System.out.println(solution(arr3)); // 4
System.out.println(solution(arr4)); // 6
System.out.println(solution(arr5)); // 4
System.out.println(solution(arr6)); // 7
System.out.println(solution(arr7)); // 12
}
}인용문 배열의 개수를 이용해서 현재 진행되는 인용문의 횟수를 이용해 계산하는 방식이다. 하.. 나는 바보인가 ㅠ
다른 분의 코드를 보자.
import java.util.*;
class Solution {
public int solution(int[] citations) {
Arrays.sort(citations);
for (int i = 0; i < citations.length; i++) {
int h = citations.length - i;
if (citations[i] >= h) {
return h;
}
}
return 0;
}
}띠 용띠용?
홀리몰리..... 이 그림을 보면 더욱 이해가 쉬워진다. 하 나는 바보였다... 쥬륵
문제 3 점프와 순간이동(프로그래머스 , Java)
문제가 너무 길다 하... 대충 설명하자면 점프와 순간이동을 할 수 있는 슈트 가 있고 점프는 에너지를 1 소모 하지만 순간이동은 에너지를 소모하지 않는다. 즉 최대한 순간이동을 많이 하면 된다. 문제 설명이 길어서 그렇지 비교적 간단한 로직이다. 잉 막상 그려보고 구현하려고 하다 보니 줄줄이 빨간색이다. 최대한 순간이동을 많이 하려면 어떻게 해야 할까... 생각하다 보니 어쨌든 최초 시작 후 순간이동을 계속하다 보면 2의 배수로 늘어난다는 사실을 깨달았다... 이걸 테스트해보기 위해 5000을 2로 나누기 시작 모든 나머지들 더하고 보니 5라는 숫자가 나왔다. 저기 있는 예제가 나에게 힌트를 주었다. 25분 고민하고 코드 1분 작성했다.
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
while(n/=2>0)ans = i%2 != 0 ? ans+1 : ans;
return ans;
}
}
현재 값을 while을 이용해 계속 2로 나눠 주며 답을 업데이트하고 반환한다.ㅋㅋㅋ
문제 가져오신 분의 코드를 보자.
import java.util.*;
public class Solution {
public static int solution(int n) {
return Integer.bitCount(n);
}
public static void main(String[] args) {
System.out.println(solution(15));
}
}응??? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이렇게 생각을 하지 않은 건 아니다. 쉬프트 하면서 1<<n 하면서 문제를 풀려고 했으나 접근법이 틀렸다고 생각했는데 ㅋㅋㅋ 비트 카운트라는 매우 훌륭한 스테틱 매서드를 제공해준다... ㅋㅋㅋㅋㅋㅋㅋ 자바는 알면 알수록 신기한 메서드가 참 많은데 왜 싫어하는 사람들이 많은지 모르겠다...
문제 4 풀링(백준 222 , Java)
1번 문제와 유사하지만 다르다... ㅋㅋㅋ 아 재귀 그만 쓰고 싶다 ㅠㅠㅠ 그렇지만 문제 보자마자 재귀적 풀이 밖에 떠오르지 않았고, 당연히 30분 안에 풀지 못했다. 약 1시간 정도 투자해서 코드를 작성했다. 아이디어는 위와 동일하게 4 등분씩 나눠 가면서 현재 사이즈가 4라면 그냥 계산해서 재귀 탈출하는 것을 조건으로 하였다. 최초 작성은 priorityqueue를 이용해 두 번째 큰 수를 제거해주었으나. 1300 초가 넘어간다. ㅋㅋㅋ 그래서 스터디 원 분 중 한분은 arr, 정렬을 그냥 하셨길래 이용했더니 약 900까지 당겨진다. ㅋㅋ
class kubin{
int[][] arr;
public void main() throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int input = Integer.parseInt(bf.readLine());
arr = new int[input][input];
for (int i = 0; i < input; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
arr[i][j] = Integer.parseInt(inputs[j]);
}
}
System.out.println(helper(new int[]{0,0},input));
}
public int helper(int[] start,int size) {
if(size == 2){
int[] n = new int[4];
int x = 0;
int row = start[0],col = start[1];
for (int i = row; i < row+2; i++) {
for (int j = col; j < col+2; j++) {
n[x++] = arr[i][j];
}
}
Arrays.sort(n);
return n[2];
}
int mid = size/2;
int curRow = start[0];
int curCol = start[1];
int[] needToSort = new int[4];
needToSort[0] = (helper(new int[]{curRow,curCol},size/2));
needToSort[1] = (helper(new int[]{curRow,curCol+mid},size/2));
needToSort[2] = (helper(new int[]{curRow+mid,curCol},size/2));
needToSort[3] = (helper(new int[]{curRow+mid,curCol+mid},size/2));
Arrays.sort(needToSort);
return needToSort[2];
}
}배열 만들어서 다음 계산으로 넘겨주고 현재 사이즈를 줄여가는 것이다. 별로 특별할 것 없는 1번과 매우 유사한 코드인데 1번도 고민하고 이것도 고민하다니.... 바보가 맞는가 보다 ㅋㅋ.
재귀가 아닌 for 문을 이용해서 푸신분의 코드를 보자.
package backjoon17829;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
static int N;
static int[][] matrix;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// 입력받은 수로 N * N 행렬 만드는 부분
matrix = new int[N][N];
for (int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(s[j]);
}
}
int size = N;
while (size > 1) { // N * N 행렬의 가로 세로가 1보다 클 때 까지 반복
// 현재 행렬 가로(세로)길이를 2로 나눈 값을 제곱하면 다음 N * N 행렬을 만드는 데 필요한 수를 저장할 수 있는 1차원 배열의 사이즈를 알 수 있음
// 예를 들어 현재 N * N 행렬의 가로(세로)길이가 8이면 (8 / 2)^2 = 16 -> 4 * 4의 행렬을 만들 수 있음
// 그리고 고정된 2 * 2 크기의 행렬 안에서 두 번째 큰 수를 구해야 하므로 i, j를 +2 씩 증가 시키면서 반복, small_matrix에 저장
int[] small_matrix = new int[(int) Math.pow(size / 2, 2)];
int idx = 0;
for (int i = 0; i < size; i += 2) {
for (int j = 0; j < size; j += 2) {
small_matrix[idx++] = getNum(i, j);
}
}
// N * N 행렬을 전체 탐색 후 크기를 반으로 줄임
// 4 * 4 행렬로 예를 들면 small_matrix의 길이는 16이고 i = 0 ~ 15까지 반복하면서
// row = 0 / 4 = 0, col = 0 % 4 = 0
// row = 1 / 4 = 0, col = 0 % 4 = 1
// row = 2 / 4 = 0, col = 0 % 4 = 2
// row = 3 / 4 = 0, col = 0 % 4 = 3
// row = 4 / 4 = 1, col = 4 % 4 = 0
// row = 5 / 4 = 1, col = 5 % 4 = 1
// row = 6 / 4 = 1, col = 6 % 4 = 2
// row = 7 / 4 = 1, col = 7 % 4 = 3
// 이런식으로 4 * 4 행렬의 값을 채워줄 수 있음
matrix = new int[size / 2][size / 2];
for (int i = 0; i < small_matrix.length; i++) {
int row = i / (size / 2);
int col = i % (size / 2);
matrix[row][col] = small_matrix[i];
}
// matrix에 새로운 값을 넣어준 후 size를 줄여줌
size /= 2;
}
// 맨 마지막에 남은 값 출력
System.out.println(matrix[0][0]);
}
public static int getNum(int row_start, int col_start) {
// 두 번째 큰 수를 뽑기위한 내림차순 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = row_start; i < row_start + 2; i++) {
for (int j = col_start; j < col_start + 2; j++) {
priorityQueue.offer(matrix[i][j]);
}
}
priorityQueue.poll();
return priorityQueue.poll();
}
}재귀로 푼걸 이렇게 for 문을 이용해 작성한 걸 보면 새로운 문제처럼 보인다... while을 이용해 현재 배열이 줄은 상태의 배열을 선언해 안에서 작업해준 후 다음 while 문으로 점점 줄여나간다. 멋진 아이디어 같다. 중간에 행, 열 계산을 나눗셈과 나머지 연산을 사용한 트릭이 인상 깊다. 이분 코드도 priorityqueue 가 아닌 배열을 이용하면 800ms까지 시간 단축이 가능한 코드이니 재귀가 싫다면 이렇게 작성하는 것도 하나의 좋은 해결책이 될 수 있다. 주석 이 깔끔하니 주접 그만 떨고 다음 문제로 넘어간다.
문제 5 Sudoku Solver(LeetCode 37, Java)
알고리즘 3회 차 비슷한 유형이 있으니 참고해주세요
https://guiwoo.tistory.com/3?category=1050412
[3번째 알고리즘 모임] 4문제
장문의 글입니다. 필요한 부분 이 있다 면 찾기로 찾아주세요. 지난번 포스팅 은 미디엄에 있으니 요기로 이동해서 확인해주세요. 0615 PS 3문제. 코딩테스트 그룹 내 뜻이 맞는 사람 들 이 새로운
guiwoo.tistory.com
스도쿠는 그냥 문제를 외워 버렸다. 지난번도 그렇고 이번에도 그렇게 그냥 문제와 풀이 방식을 달달 외웠다.
위의 포스팅에서 자세한 내용이 있으니 설명 은 생략하고 코드만 공유하겠다.
class Solution1 {
public void solveSudoku(char[][] board) {
helper(board,0,0); // 좌표
for(char[] c : board){
System.out.println(Arrays.toString(c));
}
}
public boolean helper(char[][] board, int row,int col){
if(col == 9){ //한줄끝나서 다음줄로 넘겨주는 조건
return helper(board,row+1,0);
}
if(row == 9){
return true; //우리가 찾을 케이스 단하나.
}
if(board[row][col] == '.'){
for (int i = 1; i <= 9; i++) {
if(validateCheck(board,row,col,i)){
board[row][col] = (char)(i+'0');
// return helper(board,row,col+1);
if(helper(board,row,col+1)){
return true;
// }
}
}
board[row][col] = '.';
//위에서 함수 가 다음으로 나아기자못하고 아래로 내려온다면 ? 다시 원복 시키고 false 를 리턴해
// 현재 진행중인 재귀를 종료시켜줍니다.
return false;
}else{
return helper(board,row,col+1);
}
}
public boolean validateCheck(char[][] board,int row,int col,int target){
char tg = (char)(target+'0');
//Col check
for (int i = 0; i < 9; i++) {
if(board[i][col] == tg) return false;
}
//Row check
for (int i = 0; i < 9; i++) {
if(board[row][i] == tg) return false;
}
//Subbox check
int nRow = row/3*3;
int nCol = col/3*3;
for (int i = nRow; i < nRow+3; i++) {
for (int j = nCol; j < nCol+3; j++) {
if(board[i][j] == tg) return false;
}
}
return true;
}
}
//Coordinate Intermediate
class Solution2 {
public void solveSudoku(char[][] board) {
helper(board,0);
for(char[] c : board){
System.out.println(Arrays.toString(c));
}
}
public boolean helper(char[][] board,int n){
if(n == 81)return true; // 왜 끝났으니깐 9*9 ? 81 우리는 0부터 출발합니다.
int row = n/9,col = n%9; // 로우칼럼 계산하기 항상 칼럼으로 나누고 나머지 연산 해주면 로우칼럼 나오는 트릭.
if(board[row][col]!= '.') return helper(board,n+1); // 비어있지 않기 떄문에 넘겨줍니다.
for (int i = 1; i <= 9; i++) { //어떤 숫자가 검증이 된지 모르기 떄문에 for 를돌려줍니다. 1번부터 가던 9번부터 가던 어쩃든 모든 숫자 돌면됩니다.
if(validateCheck(board,row,col,i)){ // 검증 된 숫자라면 진행 시켜 줍니다.
board[row][col] = (char) (i + '0');
if(helper(board,n+1)){
//false 가 경우 단하나. helper 함수가 끝까지 내려가는경우
// 즉 어는 숫자도 검증되지 못해 여기서 다음 재귀로 넘어가지 를 못해 아래로 내려가는 경우
return true;
}
}
}
board[row][col] = '.'; // 저 위에서 다음 재귀로 못넘어간 나머지 가치 가 없으니 원복시키고 함수를 종료 합니다.
return false;
}
public boolean validateCheck(char[][] board,int row,int col,int target){
char tg = (char)(target+'0');
//row check && col check;
for (int i = 0; i < 9; i++) {
if(board[row][i] == tg || board[i][col] == tg){
return false;
}
}
//3*3 chcck;
int nRow = row/3*3;
int nCol = col/3*3;
for (int i = nRow; i < nRow+3; i++) {
for (int j = nCol; j < nCol+3; j++) {
if(board[i][j] == tg) return false;
}
}
return true;
}
}
//Coordinate Master 10.9k view Solution
class Solution3 {
public void solveSudoku(char[][] board) {
dfs(board,0);
}
private boolean dfs(char[][] board, int d) {
if (d==81) return true; //found solution
int i=d/9, j=d%9;
if (board[i][j]!='.') return dfs(board,d+1);//prefill number skip
boolean[] flag=new boolean[10];
validate(board,i,j,flag);
for (int k=1; k<=9; k++) {
if (flag[k]) {
board[i][j]=(char)('0'+k);
if (dfs(board,d+1)) return true;
}
}
board[i][j]='.'; //if can not solve, in the wrong path, change back to '.' and out
return false;
}
private void validate(char[][] board, int i, int j, boolean[] flag) {
Arrays.fill(flag,true);
for (int k=0; k<9; k++) {
if (board[i][k]!='.') flag[board[i][k]-'0']=false;
if (board[k][j]!='.') flag[board[k][j]-'0']=false;
int r=i/3*3+k/3;
int c=j/3*3+k%3;
if (board[r][c]!='.') flag[board[r][c]-'0']=false;
}
}
}
지난번에 이어 이번에 도 시간 안에 푼 건 1문제밖에 없다.. ㅠㅠ 알고리즘 이란 녀석은 알면 알수록 점점 나에게서 멀어지는 기분이 든다.
아는 만큼 보이는게 아니라 아는만큼 생각을 하게 돼서 생각하는 시간이 점점 길어지는데 이걸 어떻게 줄여나가야 할지...
코드를 그냥 외워서 비슷한 유형에 사용하는 방법밖에 모르겠다.
긴 글 읽어주셔서 감사합니다.!