프로그래머스 풀이

• 하노이탑 (재귀)

1번 자리에서 3번자리로 이동시 1번에서 2번을 n-1개 만큼 이동하는 것을 먼저 생각한다.

import java.util.*;
public class Main {
static ArrayList<int[]> seq;
static int[][] solution(int n) {
seq = new ArrayList<>();
hanoi(n, 1, 3, 2);
int[][] answer = new int[seq.size()][2];
for(int i = 0 ; i < seq.size() ; ++i){
int[] cmd = seq.get(i);
answer[i][0] = cmd[0];
answer[i][1] = cmd[1];
}
for(int i=0;i<answer.length;i++)
{
System.out.println(answer[i][0]+” “+answer[i][1]);
}
return answer;
}
static void hanoi(int n, int from, int to, int via){
int[] move = {from, to};
if(n == 1) {
seq.add(move);
} else {
hanoi(n — 1, from, via, to);
seq.add(move);
hanoi(n — 1, via, to, from);
}
}
public static void main(String[] args)
{
solution(3);
}
}

프로그래머스 N-QUEEN

// n 큐

public class Main2 {
static int[][] arr;
static int cnt;
public static void dfs(int row, int col,int N) {
arr[row][col] = 1;
if(row == N — 1) cnt++;
for(int i = 0; i < N; i++) {
if(check(row + 1, i,N)) dfs(row + 1, i,N);
}
arr[row][col] = 0;
}
public static boolean check(int row, int col,int N)
{
for(int i = 0; i < row; i++) {
if(arr[i][col] == 1) return false;
}
for(int i = 1; i < N; i++) {
if(row — i >= 0 && col — i >= 0 && arr[row — i][col — i] == 1) return false;
// 현재 기준에서 왼쪽 대각선 위에 이미 퀸이 있으면 return false
if(row — i >= 0 && col + i < N && arr[row — i][col + i] == 1) return false;
// 현재 기준에서 오른쪽 대각선 위에 이미 퀸이 있으면 return false
}
return true;
}
public static int solution(int N)
{
arr = new int[N][N];
cnt = 0;
for(int i = 0; i <N; i++) {
dfs(0, i,N);
}
return cnt;
}
public static void main(String[] args) {
System.out.println(solution(4));
}
}

코딩테스트 대비 6.11

. hash -map / compareTo 다루기 편

n명의 선수들이 각각 토너먼트로 경기를 할때 우선순위 대로 각 선수의 승리수와 score 점수를 출력

입력
3
a 2 b 0
a 2 c 1
b 2 a 1
b 0 c 2
c 0 a 2
c 1 b 2
출력
a 3 4
b 2 -2
c 1 -2

풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;
public class Main2 {
static public class temp implements Comparable<temp> {
int win;
int score;
public temp(int win, int score) {
super();
this.win = win;
this.score = score;
}
@Override
public int compareTo(temp o) {
return o.score — this.score ;
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n=input.nextInt();
HashMap<String,temp> map = new HashMap<String,temp>();
ArrayList<String> key = new ArrayList<String>();
for(int i=0;i<n*(n-1);i++)
{
String front = input.next();
int front_score= input.nextInt();
String end = input.next();
int end_score= input.nextInt();
//초기값 설정
if(map.containsKey(front)==false) {
key.add(front);
map.put(front, new temp(0, 0));
}
if(map.containsKey(end)==false) {
key.add(end);
map.put(end, new temp(0, 0));
}
if(front_score >end_score )
{
map.put(front, new temp(map.get(front).win+1,map.get(front).score+(front_score-end_score)));
map.put(end, new temp(map.get(end).win,map.get(end).score-(front_score-end_score)));
}
else
{
map.put(end, new temp(map.get(end).win+1,map.get(end).score+(end_score-front_score)));
map.put(front, new temp(map.get(front).win,map.get(front).score-(end_score-front_score)));
}
}
for(int i=0;i<n;i++)
{
System.out.println(key.get(i) + map.get(key.get(i)).win+ map.get(key.get(i)).score);
}
List<String> keySetList = new ArrayList<>(map.keySet());
Collections.sort(keySetList, (o1,o2 ) ->map.get(o1).compareTo(map.get(o2)));
for(String i : keySetList)
{
System.out.println(map.get(i).win+” “+ map.get(i).score);
}
}
}

최소공배수 /최대 공약수

int gcd(int a, int b){
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

(최소공배수 * 최대공약수 = a * b)를 이용

int lcm(int a, int b){
    return a * b / gcd(a,b);
}

여러 값일 경우
예시 A, B, C의 최소공배수
① A와 B의 최소공배수를 구한다.
② ①에서 구한 A와 B의 최소공배수와 C의 최소공배수를 구한다.

코딩테스트 -거스름돈 (프로그래머스)

내 풀이 : 단순히 Arraylist에 각각 원소에 대한 배수들을 넣어놓고 dfs로
각각의 원소들을 하나씩 선택하여 조합하면 문제는 해결 되었다. 하지만 효유성 문제에서 떨어졌기 때문에 다른 풀이를 참고하였다 .

풀이 과정 :

class Solution {
 
 static ArrayList<int[]> arr = new ArrayList<int[]>();
 static int answer=0;
 
public static void dfs(int depth, int result,int n)
 {
 if(result > n) return ;
 
 if(depth>=arr.size()) // 조합을 리스크 종류 만큼 
 {
 
 if(result==n) {
 answer++;
 //System.out.println(result);
 }
 return;
 }
 
 for(int i=0;i<arr.get(depth).length;i++)
 {
 
 dfs(depth+1,result+arr.get(depth)[i],n);
 }
 }
 
 
 public int solution(int n, int[] money) {
 

 for(int i=0;i<money.length;i++)
 {
 
 int a[] = new int[n/money[i]+1];
 
 for(int j=0;j<=n/money[i];j++)
 {
 a[j]=money[i]*j;
 }
 
 
 arr.add(a);
 }
 // 각 원소에 대해서 배수들을 list에 저장 list에서 하나씩 뽑고 확인 
 
 for(int count=0;count<arr.get(0).length;count++) // 처음 값 부터 dfs 로 넣고 
 {
 
 dfs(1,arr.get(0)[count],n);
 }
 
 return answer % 1000000007;
 }
}

다른 사람 풀이

class Solution {
    
    static final int MOD = 1000000007;
    
    public int solution(int n, int[] money) {
        int[][] dp = new int[money.length + 1][n + 1];
        
        Arrays.sort(money);
        
        dp[0][0] = 1;
        
        for(int r = 1 ; r < dp.length ; ++r){
            for(int c = 0 ; c < dp[0].length ; ++c){
                if(c < money[r - 1]){
                    dp[r][c] = dp[r - 1][c] % MOD;
                } else if(c == money[r - 1]){
                    dp[r][c] = dp[r - 1][c] + 1 % MOD;
                } else {
                    dp[r][c] = dp[r - 1][c] + dp[r][c - money[r - 1]] % MOD;
                }
            }
        }
        
        return dp[money.length][n];
    }
}