최단 경로를 구하는 알고리즘 중 하나이다. 지난번 cs 네트워크 라우터 관련 검색하다가 잠깐 살펴본 내용인데 이번 기회에 흐름을 익혀보고자 글을 작성한다.
위의 그래프 에서 각 노드 간 의 최단거리를 구하는 방법 중 하나이다.
distance 의 배열이 존재하고 모두 최대 값 혹은 엄청 큰수로 초기화를 진행한다. 배열 의 수는 노드의 갯수 만큼 구성해서 계속 저장해 가며 값을 기록한다.
0번 에서 출발한다고 할시 갈수 있는경우 0-1, 0-2 이 가존재하며 배열에는 아래와 같이 기록한다.
distance = 0 | 5 | 1 | INF | INF | INF => 최초 시작점을 0 으로 대입해 시작 하며 이후 다음 노드는 거리가 가장 짧은 2번 부터 진행한다. 이렇게 진행하며 현재 진행 중인 간선의 수가 노드의 갯수-1 이된다면 진행을 멈추고 마지막 값을 리턴하면 그것 이 최단 거리가 된다.
코드로 구현해보자.
class Node{
int to;
int distnace;
public Node(int to, int distance) {
this.to = to;
this.distnace = distance;
}
}
각각 의 노드 에 대한 정보를 기록하기 위해 이너클래스 로 노드를 하나 구성해준다.
class Dijkstra{
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
}
}
노드 를 담기 위한 2중 리스트를 생성 해준다. 각 첫번째 리스트 는 현재 엣지 를 의미하고 그안에 담긴 리스트 들은 갈수 있는 경로 를 생성해 더해준다.
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
int[] shortest_dist = new int[edge];
Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
boolean[] visit = new boolean[edge+1];
q.offer(new Node(start,0));
}
거리 들을 기록할 배열을 하나 생성해주고 , 2^31-1 이 int 의 최대값이니 그전 까지 업데이트 해주자 전에 한번 overflow 나고 나서부터는 이렇게 초기화를 진행하고 있다.
우선순위 큐를 거리가 짧은 순으로 해서 생성해주고, 마지막까지 가는데 있어 중복 계산을 피할 방문 배열을 생성해준다.
처음 시작점을 변수로 제공받기 떄문에 큐안에 시작점을 넣어주자
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
int[] shortest_dist = new int[edge];
Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
boolean[] visit = new boolean[edge+1];
q.offer(new Node(start,0));
while(!q.isEmpty()){
Node cur = q.poll();
if(visit[cur.to]) continue;
visit[cur.to] = true;
for (int i = 0; i < graph.get(cur.to).size(); i++) {
Node next = graph.get(cur.to).get(i);
if(visit[next.to]) continue;
if(shortest_dist[next.to] > cur.distnace+next.distnace){
shortest_dist[next.to] = cur.distnace+next.distnace;
q.offer(new Node(next.to,shortest_dist[next.to]));
}
}
}
System.out.println(Arrays.toString(shortest_dist));
}
큐 안이 비어있기 전까지 계속 반복문 을 돌려준다. 대신 모든 곳을 방문 했다면 큐 를 계속해서 뽑아오기 때문에 반복문 아래부분 까지 내려가지 않고 계속 뽑아주어 함수를 종료해준다.
현재 가려는 방향의 엣지를 받아와 그안에 들어있는 갈수있는 방향들에 대한 정보들을 뽑아와 기록 되어있는 거리와 현재 거리+다음 노드의 거리 를 이용해 최소값을 계속 업데이트 하는 방식이다. 만약 그렇게 업데이트 가 되었다면 큐에 다시 넣어주어 새로운 지점에서 시작하는 노드를 넣어준다. 2~3 번 이상 계속 노트에 손코딩 하다보니 외워버렸지만 미래에 찾고있을 나를 위해 이렇게 정리해 보았다.
전형적인 재귀 문제라고 생각한다. 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);
}
}
구현에 있어 어려운 좌표 해결을 위와 같이 배열에 좌표를 담아 앞뒤로 넘겨준다. 처음 이렇게 시도하다가 좌표를 계산에 머리가 고장이 나서 지우고 다른 방법으로 접근했다. 구현하려고 하다 실패한 부분을 다른 사람의 코드로 보니 다음에 어떤 식으로 접근해야 할지 영감을 받았다.
인용문 배열의 개수를 이용해서 현재 진행되는 인용문의 횟수를 이용해 계산하는 방식이다. 하.. 나는 바보인가 ㅠ
다른 분의 코드를 보자.
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;
}
}
문제가 너무 길다 하... 대충 설명하자면 점프와 순간이동을 할 수 있는 슈트 가 있고 점프는 에너지를 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 하면서 문제를 풀려고 했으나 접근법이 틀렸다고 생각했는데 ㅋㅋㅋ 비트 카운트라는 매우 훌륭한 스테틱 매서드를 제공해준다... ㅋㅋㅋㅋㅋㅋㅋ 자바는 알면 알수록 신기한 메서드가 참 많은데 왜 싫어하는 사람들이 많은지 모르겠다...
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까지 시간 단축이 가능한 코드이니 재귀가 싫다면 이렇게 작성하는 것도 하나의 좋은 해결책이 될 수 있다. 주석 이 깔끔하니 주접 그만 떨고 다음 문제로 넘어간다.
스도쿠는 그냥 문제를 외워 버렸다. 지난번도 그렇고 이번에도 그렇게 그냥 문제와 풀이 방식을 달달 외웠다.
위의 포스팅에서 자세한 내용이 있으니 설명 은 생략하고 코드만 공유하겠다.
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문제밖에 없다.. ㅠㅠ 알고리즘 이란 녀석은 알면 알수록 점점 나에게서 멀어지는 기분이 든다.
아는 만큼 보이는게 아니라 아는만큼 생각을 하게 돼서 생각하는 시간이 점점 길어지는데 이걸 어떻게 줄여나가야 할지... 코드를 그냥 외워서 비슷한 유형에 사용하는 방법밖에 모르겠다.
주어진 needle의 스트링이 haystack 내에 존재하는지 그렇다면 그에 대한 인덱스를 아니라면 -1을 출력하는 간단한 문제이다. 스터디 원 분들도 손쉽게 스트링을 잘 잘라서 이용해서 넣어주시면서 푸셨다.
// 1번 솔루션 1ms
class Solution {
public int strStr(String hay, String needle) {
if(needle.length() > hay.length())return -1; // 니들이 길다면 굳이 탐색해줄 필요없이 -1 뱉어줍니다.
if(needle.length() == hay.length()){ // 만약 서로의 길이가 같다면 ? 서로 문자열 비교해서 맞으면 0 리턴해줍니다.
if(cal(needle,hay)){
return 0;
}else{
return -1; // 아닌경우
}
}
for (int i = 0; i < hay.length()-needle.length()+1; i++) { //for 를 끝까지 이동할 필요 없이 needle 을 셀수있을만큼만 이동
String sub = hay.substring(i,i+needle.length()); //문자 잘라주기
if(cal(sub,needle)){ //넘겨줘서 트루면 현재 인덱스 반환
return i;
}
}
return -1; // for 를 다돌아도 함수가 종료 안된다면 -1
}
public boolean cal(String s1,String s2){ //스트링 2개를 가져와 비교해서 같으면 트루,폴스 리턴 해줌 생각해보니, eqaul 쓰면됨 ㅋㅋㅋ
for (int i = 0; i < s2.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)){
return false;
}
}
return true;
}
}
문자의 서브 스트링 을 해서 잘라서 비교해주는 방법을 생각했고, 이렇게 비교를 진행했다. 예외 케이스는 항상 신경 써주자 너희들의 길이가 매우 자유 로우니 잊어먹지 말자. 특별할 게 없는 코드이다. 이 문제의 연관 주제 중 하나가 투 포인터이다. 억지로 한번 넣어서 풀어보자.
class Solution {
public int strStr(String hay, String needle) {
if(needle.length() > hay.length())return -1;
int start = 0; //시작 점
int end = needle.length(); // 찾을 문자열 끝점
int answer = -1;
while(end <= hay.length()){
String sub = hay.substring(start,end); // 위와 유사하게 문자열 잘라줍니다,
if(checker(sub,needle)){ // 체커 말고 equal 쓰세요 ㅠㅠㅠㅠ
answer = start; // 인덱스 업데이트
break;
}
start++; // 아니면 ++해줍니다
end = start + needle.length(); //문자열 끝점도 업데이트
}
return answer;
}
public boolean checker(String s1 ,String s2){
for (int i = 0; i < s1.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)) return false;
}
return true;
}
}
포인터를 각각 앞뒤로 지정한 후 이동하면서 확인한다. 이 코드를 작성하다 보니 슬라이딩 윈도 가 떠오른다. 아낌없이 아이디어를 발휘해 작성하자.
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() > haystack.length())return -1;
if(needle.length() == 0 )return 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < needle.length(); i++) {
sb.append(haystack.charAt(i)); //0번부터 추가해줍니다.
}
if(sb.toString().equals(needle)){
return 0 ; //같으면 0번 시작이니 고대로 리턴해줍니다.
}
int leftWindow = 0, rightWindow = needle.length()-1; // 윈도우 세팅 해줍니다.
while(rightWindow < haystack.length()){
sb.delete(0,1); //빌더에 요렇게 앞에서 지울수 있는 편의기능 !
rightWindow++; // 윈도우 오른쪽으로 이동 시켜줍니다.
leftWindow++;
if(rightWindow > haystack.length()-1) break; //while 에서 범위에 맞게 들어오더라도 안에서 추가를 했기때문에 다시 확인해야합니다.
//안하면 인덱스 나가요
sb.append(haystack.charAt(rightWindow)); // 늘린만큼 추가해주어 현재 스트링 갯수를 유지해 줍니다.
if(sb.toString().equals(needle)) return leftWindow;
}
return -1;
}
}
사실 이렇게 우아하게 풀지는 않았고 슬라이딩 윈도우 느낌만 내려고 좌우로 버려주고 추가해주고 이동시키면서 비교했는데 다른 사람들의 코드를 보니 이렇게 이퀄도 이용하고 스트링 빌더를 이용해서 앞에서부터 후려치는 게 매우 아름답다. 디큐를 이용해도 되지 않을까 싶지만 문자열 이니깐 복잡하니 그냥 저렇게 하는 게 아름답다.
전형적인 투 포인터 문제이지만, 각 구간의 최대합을 구한다는 부분에서 지난번 공부한 카 데인 알고리즘을 적용하려고 했지만 이해부족인지 구현능력 부족인지 못풀었다... ㅠㅠ 카데인 알고리즘을 다시 공부해보자.
문제 가져오신 분의 코드를 보자.
package backjoon2559;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, K;
static int[] temperatures;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
N = Integer.parseInt(s[0]); // 온도를 측정한 전체 날짜 수
K = Integer.parseInt(s[1]); // 합을 구하기 위한 연속적인 날짜의 수
temperatures = new int[N]; // 측정한 온도를 저장하기 위한 배열
String[] s_temperature = br.readLine().split(" ");
int max_temp = 0;
for (int i = 0; i < N; i++) {
temperatures[i] = Integer.parseInt(s_temperature[i]);
if (i < K) {
max_temp += Integer.parseInt(s_temperature[i]);
}
}
// N = 10, K = 5 일 때
// 위에서 temperatures[0] ~ temperatures[4] 까지 더한 값을 max_temp에 저장하고 temp_sum에 넣어 줌
// 1. 그리고 둘째 날부터 시작해서 temperatures[1] ~ temperatures[5] 까지의 합을 temp_sum에 넣어주고 첫째 날짜는 temp_sum에서 빼준 후
// 2. max_temp와 비교해서 더 큰 값을 업데이트
// 1번, 2번을 for문이 끝날 때 까지 반복
int temp_sum = max_temp;
for (int i = 1; i < N - K + 1; i++) {
int p1 = i - 1;
int p2 = K + i - 1;
temp_sum += -temperatures[p1] + temperatures[p2];
max_temp = Math.max(max_temp, temp_sum);
}
System.out.println(max_temp);
}
}
스터디장 님답게 주석 이 매우 깔끔하다. 핵심만 보고 간다면 좌우측으로 빼주고 더해주는 값을 현재 값에 더해주고 최댓값을 찾아가면서 업데이트를 한다. 입력을 받아올 때 저렇게 for문을 이용해 가장 첫 번째 경우를 미리 계산해주는 모습이 인상 깊다. 지난번 전선 때도 그러시더니 이건 훔쳐야겠다. 설명을 듣다 보니 이것도 슬라이딩 윈도 가 될 것 같은 느낌이다. 바로 구현해주자. (사실 30분 정도 푼 거 같다..ㅋㅋ)
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
int[] arr = new int[Integer.parseInt(inputs[0])];
int day = Integer.parseInt(inputs[1]);
int curSum = 0;
int max = 0;
String[] input2 = br.readLine().split(" ");
for (int i = 0; i < input2.length; i++) {
arr[i] = Integer.parseInt(input2[i]);
if (i < day) {
curSum += arr[i];
max += arr[i];
}
}
for (int i = day; i < arr.length; i++) {
curSum += (arr[i] - arr[i - day]);
max = Math.max(curSum, max);
}
System.out.println(max);
}
}
p1 p2 없이 그냥 슬라이딩 윈도 느낌으로 구현해 봤다. for 문으로 입력받아오면서 미리 계산하기 매우 좋다.
특별할 것 없이 위의 내용 중 p1, p2를 없애고 창문이 움직이듯이 구현했다 움직일 때마다 좌우로 계산해서 빼주는 것이다.
매번 가장 작은 카드 2장을 골라 주어진 연산만큼 더해주고 대입해주는 연산이다. 그 이후 결과 값을 출력! 유일하게 푼 문제다...ㅋㅋ
최초 접근을 arraylist를 이용해서 작성하다 보니 sort를 중복해서 계속 사용해야 된다는 사실을 깨닫고 priorityQueue로 전환했다. 자동으로 해주는데 손 아프게 해주지 말자.
코드를 보자.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = bf.readLine().split(" ");
int cnt = Integer.parseInt(inputs[1]);
PriorityQueue<Long> q = new PriorityQueue<>();
String[] input = bf.readLine().split(" ");
for (int i = 0; i < input.length; i++) {
q.offer(Long.parseLong(input[i]));
}
for (int i = 0; i < cnt; i++) {
long first = q.poll();
long second = q.poll();
q.add(first + second);
q.add(first + second);
}
long rs = 0;
while (!q.isEmpty()) {
rs += q.poll();
}
System.out.println(rs);
}
}
int로 했다가 범위 오류 나서 long으로 다급하게 수정했다. 우리의 아름다운 큐가 이미 정렬을 해주니 q.poll을 두 번 실행하고 더해준 값을 2번 넣어주면 된다. 심플하고 간단하다.
문제 가져오신 분은 다르게 작성하셨다. 색다른 방법이니 확인해보자.
import java.io.*;
import java.util.*;
public class Practice082 {
// 풀이 1 - 0, 1번 원소를 그때마다 삽입정렬
// 메모리 14632 KB, 시간 168ms
public static void solution(int n, int m, long[] arr) {
long answer = 0;
// n이 2면 걔들 둘만 계속 돌리면 됨
if(n == 2) {
for (int i = 0; i < m; i++) {
long tmp = arr[0] + arr[1];
arr[0] = tmp;
arr[1] = tmp;
}
System.out.println(arr[0] + arr[1]);
return;
}
// m이 0이면 배열 더하고 끝
if(m == 0) {
for (long item : arr) {
answer += item;
}
System.out.println(answer);
return;
}
// 배열 정렬
Arrays.sort(arr);
// m번 수행
for (int i = 0; i < m; i++) {
// 0, 1번 원소를 tmp로 업데이트한 후 매번 정렬을 하기 때문에
// 계속 0번, 1번을 더하면 됨
long tmp = arr[0] + arr[1];
arr[0] = tmp;
arr[1] = tmp;
sort(arr, 1); // 1번 인덱스에 있는것 정렬
sort(arr, 0); // 0번 인덱스에 있는것 정렬
}
// 배열 모두 더해서 출력
for (long item : arr) {
answer += item;
}
System.out.println(answer);
}
// 정렬 메서드
public static void sort(long[] arr, int startIdx) {
// 인덱스가 배열길이 - 1까지 (그 뒤에거랑 비교를 하니 -1까지)
while(startIdx < arr.length - 1) {
if(arr[startIdx] > arr[startIdx + 1]) {
// 스왑
long tmp = arr[startIdx];
arr[startIdx] = arr[startIdx + 1];
arr[startIdx + 1] = tmp;
} else { // 뒤에 원소가 더 크면 정렬 종료. (오름차순 정렬되어있기 때문)
break;
}
startIdx++;
}
}
우아한 정렬 메서드를 보자. 직접 구현해서 삽입 정렬을 실행해 주었다. 보통 다 sort를 이용할 텐데 이렇게 접근한다는 것 자체가 매우 신기한 접근법이었다. 지금 당장 나 자신에게 정렬 구현해보라고 하면 자신이 없는데... 블로그 글 작성하고 팬으로 한번 끄적여봐야겠다.
와 문제는 단순했지만 아이디어를 생각하기 꽤 어려웠다.. 반복문을 이용해 앞뒤로 비교해서 지워 나가는 것 을 키포인트로 잡고 왜냐하면 항상 큰 수는 제일 앞에 자리에 의해 결정되기 때문에 이렇게 생각했다. 코드를 작성해서 제출을 해보니 2개가 시간 초과 가 나는 것이다. 보고 가자.
class Solution {
public String solution(String number, int k) {
String answer = "";
StringBuffer sb = new StringBuffer(number);
while (sb.length() + k != number.length()) {
for (int i = 1; i < sb.length(); i++) {
if (sb.charAt(i - 1) < sb.charAt(i)) {
sb.deleteCharAt(i - 1);
break;
}
}
}
return sb.toString();
}
}
빌더를 이용해 앞에서부터 하나씩 잘라줄 생각을 했다. 크다면 자르고 아니라면 브레이크를 넣어주면서 계속 돌린다. 이 코드의 결점이 있다. 바로 821인데 1개를 지워야 한다. 위와 같은 로직이라면 무한 반복을 돈다. 앞에서 뒤로만 비교하는 경직된 코드이기 때문에 어쩔 수가 없다... 고쳐보려고 노력했으나. while 문과 for의 전체적인 부분을 수정해야 해 다른 우아한 코드를 보여주려고 한다.
class Solution {
public String solution(String number, int k) {
StringBuilder sb = new StringBuilder(number);
for (int i = 0; i+1 < sb.length() && k>0; i++) {
if(sb.charAt(i) < sb.charAt(i+1)) {
sb.deleteCharAt(i);
i=-1;
k--;
}
}
if(k!=0)
sb.delete(sb.length()-k, sb.length());
return sb.toString();
}
}
ㅋㅋㅋㅋㅋ for 문을 이용해서 그냥 한번 훑어주고 남은 개수만큼 뒤에서 잘라주면 된다 왜 와이? 앞뒤로 정렬된 상태이기 때문이다. for의 조건 상태가 특이한데 천천히 뜯어보면 i+1 은 sb.length 보다 작다 뒤에 수와 비교하기 위한 조건이고 추가로 k 가 0보다 클떄 까지 만 반복 한다. 저걸 못해서 while을 쓴 나 자신을 반성한다... 그래도 아이디어가 틀리지 않았다는 것에 조그만 위안을 삼고
코드 가져오신 분의 황홀한 코드를 보자.
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
int curK = k;
for (int i = 0; i < number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && curK-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i = 0; i < number.length()-k; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
으응? 여기서 스택을 이렇게 쓴다고? 와 자료구조는 이렇게 이용하는구나라고 감탄만 나온다.. 현재 문자열을 뽑아서 스택에 들어있는 아이들과 비교하고 작다면 과감하게 버려준다. 물론 버려주는 카운트를 하면서 진행한다. 와.. 아름다운 코드다.
문제를 이해하기는 어렵지 않다. 구현하는데 엄청 애먹었다.. ㅠㅠ 범위가 2억이라는 엄청난 범위가 주어지기 때문에 for 문이 아닌 뭔가 색다른 접근법이 필요하다고 생각했고 현재 와이파이 위치에 대한 거리를 이용해 최대 설치 개수를 구해주면서 비어있는 부분 체크를 하려고 했으나 시간 부족 능력 부족으로 구현에 실패했다.
모임 종료 이후 혼자 구현을 마무리했다.
코드를 보자.
class Solution {
public int solution(int n, int[] stations, int w) {
int current = 1, answer = 0,standard = (w*2+1); //자주사용될 아이들 미리 변수선언했다.
for (int i = 0; i < stations.length; i++) { // 범위가 2억이지 주어지는 와이파이가 2억이 아니다. 포문 과감하게 돌리자.
if (current < stations[i] - w) { //와이파이는 정렬된 상태로 들어오기 때문에 이렇게 연산 가능하다.
int left = stations[i] - w - 1 - current + 1; //와이파이가 터지는 왼쪽으로 부터의 거리
answer += left / standard; // 나눗셈을 이용해 정답에 더해주자 왜? 이게 와이파이 설치 최대거리이니깐
if (left % standard != 0) // 이렇게 한이후 나머지 처리를 해주어야한다.
answer++; //0이아니라면 짜잘한 애들이 있으니 추가를 해주고 , 현재 포인트도 업데이트
current = stations[i] + w + 1;
} else { //아니라면 현재포인트만 업데이트한다.
current = stations[i] + w + 1;
}
}
// 위의 기지국을 이용해 갈수 있는 최대 거리까지 이동했으나 n 보다 모자른 경우에 대한연산이다.
// 위와동일한 개념으로 작성했다.
if (current <= n) {
int left = n - current + 1;
answer += left / standard;
if (left % standard != 0)
answer++;
}
return answer;
}
}
왼쪽에 보는 이미지와 같이 저기 사이의 공간을 구해 나눠주는 곳에서 착안해 위와 같이 작성하였다.
문제 가져오신 분의 보다 직관적인 풀이를 보자 이거는 이해를 못 할 수가 없다.
// 기지국 설치
// https://programmers.co.kr/learn/courses/30/lessons/12979
import java.util.*;
public class T3 {
public static int solution(int n, int[] stations, int w) { // 16, [9], 2
int cnt = 0; // 기지국 개수
int position = 1; // 1동부터 시작
int idx = 0; // stations[] 내의 idx
// 전파가 터지는 최대 위치 position
while(position <= n){
// 기지국 설치 하지 않아도 되는 상황
// 현 위치 position은 station[idx]으로부터 전파가 터지는 상황이다.
if(idx < stations.length && stations[idx] - w <= position ){
// position에 2w + 1만큼 온전히 더할 수 없는 상황이니까 position을 변경한다.
// stations[idx] - w 부터 stations[idx] + w 까지 전파 터지니까 그 다음으로 이동
position = stations[idx] + w + 1;
++idx;
// System.out.println("position: " + position + ", idx: "+ idx);
continue;
}
// 기지국 설치해야하는 상황
++cnt;
position += 2 * w + 1;
// System.out.println("position: " + position + ", cnt: " + cnt);
}
return cnt;
}
public static void main(String[] args){
int[] stations = {4, 11};
System.out.println(solution(11, stations, 1)); // 3
stations = new int[]{9};
System.out.println(solution(16, stations, 2)); // 3
stations = new int[]{3, 7, 9};
System.out.println(solution(16, stations, 1)); // 4
}
}
전체적인 맥락은 매우 비슷하다. while을 이용해서 앞에부터 포인터를 이동해가며 설치를 해야 한다면 cnt를 추가해주는 것이다. 이 문제 출제자 님의 설명을 듣고 한 가지 의문이 들었다 굳이 앞에부터 할 이유가 없다고 생각했다. 과감하게 넘기고 연산을 줄일 수 있는 방법에 내 아이디어를 적용한다면 더 빠르게 구현 가능하겠다 싶어 여쭤보니 철저하신분 이라 비슷한 아이디어로 작성한 코드가 있다고 보여주셨다.
class Solution {
public int solution(int n, int[] stations, int w) { // 11, [4, 11] , 1
int left = 0; //기지국 범위 외 왼쪽
int right = 0; //기지국 범위 외 오른쪽
int baseL = 0; //기지국 범위 내 왼쪽
int baseR = 0; //기지국 범위 내 오른쪽
int result = 0;
for(int i = 0; i < stations.length; ++i){
int base = stations[i]; // 4, 11
left = baseR; // 왼쪽 값은 기지국 내의 오른쪽 값, 나중에 개수를 구하기위해 굳이 +1하지않는다.
baseL = base - w;
baseR = base + w; // 너비 w에 따른 기지국의 범위 baseL ~ baseR
if(baseL < 0 ) baseL = 0;
if(baseR > n ) baseR = n; // 배열의 범위를 초과할 때 한정시켜준다.
right = baseL - 1;
if(right < 0) continue;
if(left == right) continue; // 같다면 기지국 사이가 커버 되었을 때이다. ??
if(left > right) continue;
double temp = (double) (right - left) / ((2 * w) + 1);
if(temp % 1 == 0) result += (int) temp; // temp가 정수 일 때
else result += (int) temp + 1;
}
if(baseR != n){ // 모두 처리한 후, baseR은 n이 되어야 한다.
double temp = (double) (n - baseR) / ((2 * w) + 1);
if(temp % 1 == 0) result += (int) temp;
else result += ((int) temp) + 1 ;
}
return result;
}
}
문제 가져오신분의 코드에 정확하게 내가 말한 아이디어만 추가가 되어 구현 된 부분이다. 아이디어는 비슷한대 내가 구현한 코드가 조금더 빨랐다. 미리 처리를 해줘서 그런건가. 잘 모르겠지만 빠르면 좋은게 아닌가 ? 정신승리 하고 넘어가자.
이번 모임 문제의 난이도는 나에게 어려웠다. 투 포인터 그리디가 부족한 부분을 느끼는 하루였다.
매번 문제를 풀며 좌절하는데 이제 너무익숙해져 가는 내 자신이 참 그렇다. 다음 모임 에는 어떤 문제가 나올지 두렵다.. ㅋㅋ 모임에서 문제를 풀고 즉각적인 피드백 과 예외케이스 등을 알아가고 질문을 던지면서 어떤 방식으로 접근했는지 왜 그렇게 생각했는지 등의 이 접근법을 얻는것이 정말 도움이 많이 되는것 같다. 얻어가는 게 많은 하루였다.
내가 가져간 문제이고 나는 풀지 못했다, bfs를 활용해서 풀려고 접근했다가 머리 깡 당했다.
1. 비어있는 부분을 큐에 넣어준다.
2. 3*3 , 세로, 가로 모두 중복된 숫자가 없는지 확인한다.
3. 위의 2번이 통과된다면 숫자를 집어넣고 큐에서 제거한다. 아니라면 다시 큐에 넣어준다.
위와 같은 방식으로 접근했고 줄줄이 틀렸다...... 😭 약 2일 동안 댐 같은 고집으로 이리저리 굴려 봤으나 실패했다... 어떤 부분이 실패의 주된 원인인가 확인해보니 내가 고려한 부분은 오로지 하나의 경우의 수만 고려했기 때문 에 정답이 나오지 않거나 혹은 무한히 스도쿠를 반복하는 경우가 발생한다...ㅠ
모임 안에서도 대부분 비슷한 접근법을 이용하였고, 몇몇 분들은 거의 근사한 접근법까지 접근했으나 시간 부족으로 구현에 실패했거나 혹은 스도쿠라는 개념이 생소하여 문제 이해에서 곤혹을 겪으신 분이 있다. 아래 코드 들은 스도쿠에 대한 기본적인 이해가 있어야 이해가 되니 스도쿠를 모른다면 검색해서 개괄적인 게임 룰을 인지하고 왔으면 한다.
총 3가지 의 방법을 소개하겠다. 하나만 이해가 된다면 모든 풀이법을 이해할수 있으니 읽기 쉽고 본인에게 직관적인 부분을 보고 구현에 힘을 써보자.
1. 풀이 입력을 받아온 숫자에서 만약 빈칸 에 들어갈 모든 수에 대해 dfs를 구현하고 그 수를 이용해 스도쿠를 완성 못한다면 다시 거슬러 올라가면서 문제를 해결하는 방법이다. 말은 쉬우나 막상 코드로 구현해보려면 정말 난해하다.
// 596 ms
public class Boj2580 {
static int[][] grid;
public static void main(String[] args) throws IOException {
grid = new int[9][9];
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < grid.length; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
grid[i][j] = Integer.parseInt(inputs[j]);
}
}
dfs(0, 0); // 0,0 즉 좍측 제일 위에부터 dfs 를 진행할 예정이다.
bf.close();
s.main();
}
/*
dfs 에서 해야할 일
- 1. 모든 스도쿠 방문을 순회해야 한다.
- 2. 만약 비어있는 공간이라면 그곳에 대한 숫자 판별을 하고 다음으로 넘겨주어야 한다.
- 3. 모든 칸을 순회했지만 아직 비어있는 곳이 있다면 ? 다시 거슬로 올라와 다른 숫자를 판별한다.
*/
public static void dfs(int row, int col) {
if (col == 9) { //col 기준 으로 진행 되기때문에 가장 먼저 if 체크를 해준다.
dfs(row + 1, 0); // col이 8 이 된다면 1줄 증가시켜준다.
return;
}
if (row == 9) { // 모든 방문이 끝났다. 그대로 종료해준다.
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(grid[i][j]).append(' ');
}
sb.append('\n');
}
System.out.println(sb.toString());
System.exit(0); // 이부분이 없다면, 결국 2가지의 해답을 얻는다. 모두 채워진 경우 or 아무것도 채우지 않은 경우
}
if (grid[row][col] == 0) { // 0 이 된다면 ? 체크를 진행해주자
for (int i = 1; i < 10; i++) {
if (checker(row, col, i)) { 아래함수 를 참조
grid[row][col] = i; 결과 값에 따른 업데이트
dfs(row, col + 1); 다음 칼럼으로 진행
}
}
grid[row][col] = 0; for 를 이용해 돌았지만 아직 0 이고 다음함수로 못넘어가고 아래로 내려온다면 ? 0으로 복귀
return; //이후 현재 재귀를 종료, 현재 진행중인 칸이 답이 아니니 그 전칸으로 거슬로 올라가자.
}
dfs(row, col + 1); //0이 아니고 col 이 8 도 아니고 row 가 8 도아니라면 ? 다음으로 가자
}
public static boolean checker(int row, int col, int val) {
// 칼럼 체크를 위한 for문 확인
for (int i = 0; i < 9; i++) {
if (grid[i][col] == val)
return false;
}
// 로우 체크를 위한 for 문 확인
for (int i = 0; i < 9; i++) {
if (grid[row][i] == val)
return false;
}
// 3*3 확인을 위한 for 문
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (grid[i][j] == val)
return false;
}
}
return true;
}
}
개괄적인 설명은 위에 주석이 첨부 되어있으니 가장 핵심적인 부분을 다시 반복해서 말하겠다.
왼쪽 이미지를 보자 우리는 칼럼에 의해 순서를 따라가기 때문에 첫 번째 0 에는 1 또는 9 가 들어간다
우리 for 문 logic 에 의해 1 이 가장 먼저 검사가 되고 인증된 숫자로 0자리에 1이 들어가게 된다. 자 두 번째 0 검사를 시작하자 어라 9가 중복되어 들어간다. 3*3 배열을 확인해보니 여기는 숫자가 들어갈 수가 없다.
우리의 재귀는 1 (채운수) > 0 인것이다. 다시 거슬러 올라가(현재 재귀를 리턴으로 종료한다.) for 문의 2부터 다시 탐색을 시작해 결국 9 가 들어가게 되는 것이다. 말을 이렇게 풀어놔서 그렇지 본인이 직접 그려보자. 이해가 더욱 빠를 것이다.
2. 두 번째 풀이를 보자. 큰 포괄적인 개념은 위에 설명한 것과 동일하다.
// 500ms
class Boj2580_03 {
static int[][] grid;
public void main() throws IOException {
grid = new int[9][9];
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < grid.length; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
grid[i][j] = Integer.parseInt(inputs[j]);
}
}
solve(0);
System.out.println("done");
StringBuffer sb = new StringBuffer();
for (int[] g : grid) {
for (int x : g) {
sb.append(x + " ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
// 불리언을 반환해 재귀 호출 할떄 이용한다.
public boolean solve(int n) { // 좌표를 넘겨주는것이 아닌 현재 탐색된 갯수를 넘겨준다.
if (n == 81) // 총 9*9 칸이므로 이와같은 결과 가 나온다.
return true;
int row = n / 9; //나눈값은 로우가 되고
int col = n % 9; // 나머지값은 칼럼이된다. 알아두면 유용하니 기억해두자.
if (grid[row][col] != 0) {
return solve(n + 1); //0이 아니라면 체크해줄 이유가 없으니 다음으로 넘어간다.
} else {
for (int i = 1; i < 10; i++) {
if (isValid(row, col, i)) {
grid[row][col] = i;
// 다음 재귀로 넘겨주는것을 if 로 받는다..
if (solve(n + 1))
return true;
grid[row][col] = 0; //if에걸리지 않아 리턴못한다면 ? 0으로 초기화해준후
}
}
return false; // false 를 리턴한다.
}
}
public boolean isValid(int row, int col, int val) {
// 일기 힘들지만 자세히 본다면 한번에 for 문을 체크하기 때문에 납득할만하다.
for (int i = 0; i < 9; i++) {
if (grid[row][i] == val ||
grid[i][col] == val ||
grid[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == val) {
return false;
}
}
return true;
}
}
1번 코드가 이해되었다면 2번 코드 또한 자연스레 이해가 될 것이다.
이 풀이의 특징이라면 재귀의 반환 값을 불리언을 지정하고 그것을 이용하는 것 과 좌표 가 아닌 숫자를 넘겨 좌표 계산하는 방법이다.
3. 세 번째 풀이
//392ms
class Boj2580_02 {
static int[][] grid;
public void main() throws IOException {
grid = new int[9][9];
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < grid.length; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
grid[i][j] = Integer.parseInt(inputs[j]);
}
}
solve(0);
System.out.println("done");
StringBuffer sb = new StringBuffer();
for (int[] g : grid) {
for (int x : g) {
sb.append(x + " ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
public boolean solve(int cur) {
if (cur == 81)
return true;
int row = cur / 9;
int col = cur % 9;
if (grid[row][col] != 0)
return solve(cur + 1);
boolean[] flag = new boolean[10]; // 숫자를 체크해줄 배열
validCheck(row, col, flag);
for (int i = 1; i < 10; i++) {
if (flag[i]) { //그숫자가 트루인 경우에만 다음으로 넘어간다.
grid[row][col] = i;
if (solve(cur + 1)) {
return true;
}
}
}
grid[row][col] = 0; //위의 for loop 이끝나도록 반환이 안된다면? 0으로 바꾼후 false
return false;
}
public void validCheck(int row, int col, boolean[] flag) {
Arrays.fill(flag, true); // 모두 트루로 채워주고 검사를 통해 false 로 바꿔준다.
for (int i = 0; i < 9; i++) {
if (grid[row][i] != 0)
flag[grid[row][i]] = false;
if (grid[i][col] != 0)
flag[grid[i][col]] = false;
int r = (row / 3) * 3 + i / 3;
int c = (col / 3) * 3 + i % 3;
if (grid[r][c] != 0)
flag[grid[r][c]] = false;
}
}
가장 좋다고 생각한 풀이이다. 배열을 이용해 숫자를 체크해주고 그에 대한 반환 값과 for loop의 연산이 모두 종료된 이후 처리해주는 모든 부분이 제일 직관적이고 빠르다.
제대로 못 풀었다, 좌표를 받아와 이차원 배열에 넣을 때 어떻게 계산을 해주어야 할지 계속 고민하고 그려보고 몇 번을 그려 봤는지 모르겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* 5 7 3
* 0 2 4 4
* 1 1 2 5
* 4 0 6 2
* */
public class Test{
static int N;
static int M;
static int[][] grid;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = bf.readLine().split(" ");
N=Integer.parseInt(inputs[0]) ;
M=Integer.parseInt(inputs[1]) ;
grid = new int[N][M];
for (int i = 0; i < Integer.parseInt(inputs[2]); i++) {
String[] coordinates = bf.readLine().split(" ");
for (int j = Integer.parseInt(coordinates[1]); j < Integer.parseInt(coordinates[3]); j++) {
for (int k = Integer.parseInt(coordinates[0]); k < Integer.parseInt(coordinates[2]); k++) {
grid[j][k] = 1;
}
}
}
bf.close();
for(int[] x :grid){
for(int c : x){
System.out.print(c+" ");
}
System.out.println();
}
ArrayList<Integer> answer = new ArrayList<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == 0){
grid[i][j] = 1;
answer.add(bfs(i,j));
}
}
}
System.out.println(answer.size());
Collections.sort(answer);
for (Integer integer : answer) {
System.out.print(integer + " ");
}
}
static int bfs(int row,int col){
int[] dirs = {0,1,0,-1,0};
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{row,col});
int cnt = 1;
while(!q.isEmpty()){
int[] cur = q.poll();
for (int i = 1; i < dirs.length; i++) {
int nRow = cur[0]+dirs[i];
int nCol = cur[1]+dirs[i-1];
if(0<= nRow && nRow < N && 0<=nCol && nCol<M && grid[nRow][nCol] != 1){
grid[nRow][nCol] = 1;
q.offer(new int[]{nRow,nCol});
cnt++;
}
}
}
return cnt;
}
}
문제 가져오신 분의 설명을 듣고 bfs로 구현해 보았다. 좌표를 그리드에 넣는 부분이 이문제의 키포인트이다.
좌표를 가져와서 그대로 좌우반전만 해서 그리드에 넣는다면 아마 상하 반전이 될 텐데 그걸 이해하고 넘어가야 좌표를 그리드에 집어넣을 수 있다.나머지 부분은 일반 bfs와 다를 바 없다.
문제 가져오신 분의 dfs를 보자.
import java.io.*;
import java.util.*;
// 백준 2583번
// https://www.acmicpc.net/problem/2583
public class Practice070 {
public static ArrayList<Integer> area; // 각 분리된 부분의 넓이 배열
public static int areatmp; // 재귀돌면서 넓이 저장할 변수
public static int[][] grid; // 땅
public static void dfs(int[][] grid, int i, int j) {
int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 동서남북
grid[i][j] = 1; // 1로 바꾸고 (방문배열이 필요한 경우도 있음)
areatmp++; // 넓이 더하기
for (int[] d : dir) {
int x = i + d[0];
int y = j + d[1];
// 그리드 안에 있으면서, 0인 경우
if(x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]==0) {
dfs(grid, x, y); // 재귀호출
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int m, n, times;
String[] tmp1 = br.readLine().split(" ");
m = Integer.parseInt(tmp1[0]);
n = Integer.parseInt(tmp1[1]);
times = Integer.parseInt(tmp1[2]);
grid = new int[m][n];
area = new ArrayList<>();
// 배열에 1 집어넣기
for (int i = 0; i < times; i++) {
int x1, x2, y1, y2;
String[] tmp2 = br.readLine().split(" ");
x1 = Integer.parseInt(tmp2[0]);
y1 = Integer.parseInt(tmp2[1]);
x2 = Integer.parseInt(tmp2[2]);
y2 = Integer.parseInt(tmp2[3]);
for (int j = y1; j < y2; j++) { // <- for문을 돌때
for (int k = x1; k < x2; k++) { // <- 미리 배열의 인덱스를 제대로 처리해보자
grid[j][k] = 1;
}
}
}
// 배열 돌면서 0이면 dfs돌기
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(grid[i][j]==0) {
dfs(grid, i, j);
area.add(areatmp);
areatmp = 0;
}
}
}
// 출력
area.sort(Comparator.naturalOrder());
System.out.println(area.size());
for (int i = 0; i < area.size(); i++) {
System.out.print(area.get(i) + " ");
}
}
}
주어진 랜선을 잘라 원하는 개수를 맞춰주어야 하는데,,, 범위가 어마 무시하다. 이분 탐색을 바로 생각해 어렵지 않게 풀이가 가능했다.
import java.io.*;
public class Test{
static int N;
static int target;
static int[] lenCable;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = bf.readLine().split(" ");
N = Integer.parseInt(inputs[0]);
target = Integer.parseInt(inputs[1]);
lenCable = new int[N];
long total = 0;
for (int i = 0; i < N; i++) {
lenCable[i] = Integer.parseInt(bf.readLine());
total += lenCable[i];
}
long left = 1;
long right = (total/target);
while(left <= right){
long mid = (left+right)/2;
int cnt = 0;
for (int i = 0; i < lenCable.length; i++) {
cnt += (int)lenCable[i]/mid;
}
if(cnt < target){
right = mid-1;
}else{
left = mid+1;
}
}
System.out.println(left-1);
}
}
left와 right의 범위를 설정해주는 부분만 신경 쓴다면 어렵지 않은 문제이다. long을 이용해 범위가 아웃되는 예외를 처리해주고, 들어갈 전깃줄의 모든합 을 이용해 나누어주어 최대 값을 선정하는 부분이 이문제의 키포인트이다.
현재의 진행된 작업과 작업의 진행의 속도가 다르고, 또 작업은 앞에서부터 순차적으로 마무리되어야 한다.
최초 생각은 arraylist를 이용해 작업을 해 줄생각을 해보니 굳이 지우고 해줄 필요가 없는 것이다.. 큐를 이용하면 들어온 순서로 쉽게 구현이 가능한데 굳이 돌아갈 이유가 없어 반줄 정도 작성한 코드를 지우고 큐를 이용해 구성했다.
문제 가져오신 분의 코드를 보자 주석과 설명이 깔끔하다.
import java.util.*;
public class Test1 {
public static int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> daysQueue = new LinkedList<>();
Queue<Integer> resQueue = new LinkedList<>();
for(int i = 0; i < progresses.length; ++i) {
int d = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
// 올림한다. ceil()과 같음
daysQueue.offer(d);
// daysQueue = [7, 3, 9] 로부터 [2, 1]을 반환하도록 한다.
// [7 3] [9]으로 찢어서 [2, 1]이 나오도록
}
int day = daysQueue.poll(); // 7
int cnt = 1;
while(!daysQueue.isEmpty()){
int n = daysQueue.poll(); // 3
if(day >= n){ // 기준값(day)보다 작은 값이 나오면? (기준값보다 큰 값이 나올 때 까지 ++cnt)
++cnt;
continue;
}
// 기준값(day)보다 n이 큰 경우는?
// 현재 cnt를 resQueue에 넣고 cnt를 1로 초기화해야하는 상황
resQueue.offer(cnt);
cnt = 1;
day = n; // 7이었던 비교 기준이 9로 바뀐다.
}
resQueue.offer(cnt); // 마지막 데이터에 대한 cnt를 넣는다.
return resQueue.stream().mapToInt(Integer::intValue).toArray();
}
}
두 개의 queue를 이용해 작업이 완성되면 완성 큐에 넣어주고 완성 큐를 반환한다. 깔끔하다. 모임원 중 한 분이 큐&스택 태그인데 어떻게 스택으로 푸는지도 궁금해하셔서 코드를 작성해 보았다.
class Solution01 {
public int[] solution(int[] progresses, int[] speeds) {
//**님이 말씀하신 것처럼 스택 을 이용해서 풀어보고자 이렇게 스택선언!
Stack<Deploy> stack = new Stack<>();
//역순으로 집어넣기 위한 for 문
for (int i = progresses.length - 1; i >= 0; i--) {
stack.push(new Deploy(progresses[i], speeds[i]));
}
// 정답의 추가를 위한 list
ArrayList<Integer> list = new ArrayList<>();
// 누적된 일수를 기록
int days = 0;
while (!stack.isEmpty()) {
Deploy d = stack.pop();
int deployed = 1; // 항상 뽑으면 1을 진행한 횟수입니다 !!
d.current = d.current + d.speeds * days; // 현재 배포진행 율 업데이트 위한 구역
days += (100 - d.current + d.speeds - 1) / d.speeds; // days 에 나눠준만큼 더하기(란님이 알려주신 내용 사용)
while (stack.size() > 0 && stack.peek().current + stack.peek().speeds * days >= 100) {
//peek 을이용해 다음을 구분하고, poll 사용시 하나 제거됨으로 peek
//다음 stack 에서 나오는 진행율 + 현재 일자*배포진행속도 가 100 이상이라면 ? 바로 pop 진행하고 배포를 하나 늘려줍니다
stack.pop();
deployed++;
}
list.add(deployed);
}
System.out.println(list);
return list.stream().mapToInt(Integer::intValue).toArray();
}
class Deploy {
int current;
int speeds;
Deploy(int current, int speeds) {
this.current = current;
this.speeds = speeds;
}
}
}
스택을 이용하기 위해 for문을 이용해 역으로 쌓아 올렸다.
이외에 while 문을 이용해 하나씩 빼서 돌리신 분도 있다. 코드를 보자.
public static ArrayList<Integer> solution(int[] progresses, int[] speeds) {
ArrayList<Integer> answer = new ArrayList<>();
int serveIdx = 0; // 배포된 서비스 인덱스
int serveCnt = 0; // 한번 배포될 때 배포된 기능 카운트
// 배포를 다 할때까지
while(serveIdx < progresses.length) {
// 각 기능 개발
for (int i = 0; i < progresses.length; i++) {
if(progresses[i] < 100) {
progresses[i] += speeds[i];
}
}
// 기능이 완성된것이 있으면 인덱스 옮기고
if(progresses[serveIdx] >= 100) {
while(progresses[serveIdx]>=100) {
serveIdx++;
serveCnt++;
if(serveIdx == progresses.length) {
answer.add(serveCnt);
return answer;
}
}
// 배포된 기능개수 정답배열에 더하기
answer.add(serveCnt);
serveCnt = 0;
}
}
return answer;
}
서비스의 인덱스를 기록해주는 것이 이 코드의 포인트이다. 큐 스택을 따로 이용하지 않기 위해 포인트 지접이 되는 곳을 하나씩 기록을 해주는 것이다.
삼각형이 주어지고 하나의 선을 그리면서 아래로 이동후 마지막 줄에서 가장 큰 수를 반환하는 것이다. 즉 위에서 부터 숫자를 가지고 내려가는 방식으로 진행이 된다. 그냥 더해주면서 가면 되고, 중간 숫자들은 윗줄의 앞뒤 숫자를 비교해 큰 값을 넣어주면 되겠다 싶어서 재귀 함수로 구현했다.
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
helper(triangle, 1);
return Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();
}
public void helper(int[][] triangle, int level) {
if (level == triangle.length) {
return;
}
triangle[level][0]+= triangle[level-1][0];
triangle[level][triangle[level].length-1] += triangle[level-1][triangle[level-1].length-1];
for (int i = 1; i < triangle[level].length-1; i++) {
triangle[level][i] += Math.max(triangle[level - 1][i - 1], triangle[level -
1][i]);
}
helper(triangle, level + 1);
}
}
특별할 것은 따로 없다 단지 좌우측 끝에 들어갈 아이들은 for 문밖에서 미리 계산을 해주고 가운데 들어갈 아이들은 max 메서드를 이용해 큰 수를 더해주는 방법이다.
문제 가져오신 분의 코드를 보자 2종류이다.
class Solution {
/*
public int solution(int[][] triangle) {
int answer = 0;
for(int i = 1; i < triangle.length ; i++){
for(int j = 0; j < triangle[i].length; j++){
if(j == 0)
triangle[i][j] = triangle[i][j] + triangle[i-1][j];
else if(i == j)
triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
else{
int left = triangle[i][j] + triangle[i-1][j-1];
int right = triangle[i][j] + triangle[i-1][j];
triangle[i][j] = Math.max(left, right);
}
answer = Math.max(answer, triangle[i][j]);
}
}
return answer;
}
*/
////
public int solution(int[][] triangle) {
for(int i = triangle.length-2; i >= 0 ; i--){
for(int j = 0; j < triangle[i].length; j++){
int left = triangle[i][j] + triangle[i+1][j];
int right = triangle[i][j] + triangle[i+1][j+1];
triangle[i][j] = Math.max(left, right);
}
}
return triangle[0][0];
}
}
위에서 내가 구현한 코드를 for 문으로 바꾼다면 위에 첫 번째 설루션과 동일하다 신기한 것은 2번째 설루션이다.
생각의 발상을 바꿔 for 문을 역으로 도는 것이다 아래에서부터 위로 올라가 결국 마지막 하나 남은 꼭대기를 반환하는 와 참신하고 효율적인 방법이라고 생각한다.!!
대략 4시간 정도를 슬랙의 화상회의를 이용해 문제풀이 및 해설을 진행하였고, 오늘 역시 배워가는 부분이 많아 블로그 작성 중 에도 다시 한번 코드를 보게 되어 좋았다.
Ps 해결 과정 중에 몇개중에 몇개를 선택하세요 등의 해결해야 하는 경우가 간간히 발생하게 된다.
왼쪽 과 같이 정해진 배열 안에서 가능한 경우의 수를 모두 구해서 찾고자 하는 값을 리턴할떄 보통 순열 의 방법을 생각하고 구현하려고 한다. 보이는 것처럼 순열 에는 미디움 레벨의 중간 난이도로 측정을 하고 있다. ps를 하면서 많이 사용은 안하지만 가끔 나오면 헷갈려서 찾아보곤 하는데 이번에 정리를 해보자.
1. 재귀를 이용한 방법 , 이 방법을 항상 제일 먼저 떠올리고 사용하는것 같다.
[1,2,3] 에 대해 3 자리수 순열을 구해 본다면 3! 해서 6을 쉽게 떠올릴수 있다. 코드를 구현하려고 하면 막막한데 어떻게 하면 될까?
위의 그림을 타고 내려간후 깊이가 3이라면 ? 출력 을 하거나 멈춰주는 재귀 의 조건을 걸어주면 된다. 코드를 보자.
public void main() {
int[] arr = { 1, 2, 3 };
int[] out = new int[3];
boolean[] visit = new boolean[3];
System.out.println("=== Permutation ===");
permutation_fisrt(arr, out, visit, 0);
}
public void permutation_fisrt(int[] arr, int[] out, boolean[] visit, int depth) {
if (depth == out.length) {
System.out.print(Arrays.toString(out) + " ");
return;
} else {
for (int i = 0; i < arr.length; i++) {
if (visit[i] != true) {
visit[i] = true;
out[depth] = arr[i];
permutation_fisrt(arr, out, visit, depth + 1);
visit[i] = false;
}
}
}
}
위의 그림과 동일한 결과가 나온다. 현재의 깊이와 내가 출력하고자 하는 개수가 같다면 재귀를 멈춰주는 것이 키 포인트이다.
함수의 재귀 호출 이후 visit[i] 를 false 해주는 이유가 뭘까 ?
visit 은 모든 재귀 호출시에 공유 되어지는 동일한 변수이다. 따라서 현재 재귀 실행중인 수를 사용후 다시 반납을 해주어야 현재 레벨에서 진행되는 다른 재귀에 영향을 주지않는다. 만약 저 다시 숫자를 반납하지 않는다면 [1,2,3] 의 하나의 경우만 출력하게 된다. 재귀의 마지막 레벨에 도달하면 다시 위의 레벨로 거슬러 올라가는것을 생각해 본다면 조금 더 생각하기 쉽다.
2. 인덱스 순서를 이용해 위치를 바꿔주는 방법
재귀의 깊이에 따라 인덱스 보다 높은 인덱스 들의 배열 순서를 바꿔주는 것이다. 그림으로 본다면 아래와 같다
public void permutation_second(int[] arr, int out[], int depth) {
if (depth == out.length) {
System.out.print(Arrays.toString(out) + " ");
return;
} else {
for (int i = depth; i < arr.length; i++) {
out[depth] = arr[i];
swap(arr, depth, i);
permutation_second(arr, out, depth + 1);
swap(arr, depth, i);
}
}
}
public void swap(int[] arr, int depth, int i) {
int temp = arr[depth];
arr[depth] = arr[i];
arr[i] = temp;
}
