공부흔적

문제 링크

풀이 )

  가장 먼저 주사위의 마주보는 면을 짝 지어주기 위해 (0, 3), (1, 4), (2, 5) 인덱스에 각각 마주보는 면을 저장해주었다.

  가장 바닥에 올 수 있는 면은 1번 주사위의 면 6개 중 하나이기 때문에 전체 6가지 답이 나올 수 있다.

  각 주사위에 대해서 밑면의 숫자를 bottom, 윗면의 숫자를 top이라고 하면 이때 가장 큰 답이 나오기 위해서는 위, 아랫면을 제외한 4면 중 가장 큰 값을 선택하면 된다.

  이 값을 구하기 위한 getSide( )메서드에서는

• bottom과 top이 각각 5와 6 또는 6과 5인 경우 (즉, 합이 13) 4를 반환
• bottom 또는 top이 6이고 나머지는 5 미만인 경우 5를 반환
• 그 이외의 경우에는 6을 반환한다.

  이전 주사위의 윗면의 숫자와 일치하는 현재 주사위의 아랫면과 현재 주사위의 윗면을 제외한

  나머지 현재 주사위의 옆면에 대해서도 같은 작업을 반복한다.

  이렇게 구한 값 중 최댓값이 답이 된다.

(마주보는 면의 인덱스를 조건문 처리해주지 않기 위해 i와 (i+3)%6으로 구했다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in;

        int n = Integer.parseInt(br.readLine());
        int[][] dice = new int[n][6];
        for(int i = 0; i < n; ++i){
            in = br.readLine().split(" ");
            dice[i][0] = Integer.parseInt(in[0]);
            dice[i][1] = Integer.parseInt(in[1]);
            dice[i][2] = Integer.parseInt(in[2]);
            dice[i][3] = Integer.parseInt(in[5]);
            dice[i][4] = Integer.parseInt(in[3]);
            dice[i][5] = Integer.parseInt(in[4]);
        }

        int max = 0;
        for(int i = 0; i < 6; ++i){
            int bottom = dice[0][i];
            int top = dice[0][(i+3)%6];
            int sum = getSide(bottom, top);
            for(int j = 1; j < n; ++j){
                for(int k = 0; k < 6; ++k){
                    if(dice[j][k] == top){
                        bottom = dice[j][k];
                        top = dice[j][(k+3)%6];
                        break;
                    }
                }
                sum += getSide(bottom, top);
            }
            max = Math.max(max, sum);
        }
        System.out.println(max);
    }

    public static int getSide(int bottom, int top){
        if(bottom+top == 11)
            return 4;
        else if(bottom == 6 || top == 6)
            return 5;
        else
            return 6;
    }
}

문제 링크

풀이 )

  set을 사용하여 더 빠르게 풀 수 있지만 트라이를 이용해서 풀었다.

  n번의 입력에 대해서 트라이를 생성한 이후

  m번의 입력에 대해서 트라이를 타고가면서 마지막까지 도달한다면 끝인지 확인하여 답을 늘려주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");

        int n = Integer.parseInt(in[0]), m = Integer.parseInt(in[1]);
        Node root = new Node();
        while(n-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    cur.children[c-'a'] = new Node();
                cur = cur.children[c-'a'];

                if(i == str.length()-1)
                    cur.isLast = true;
            }
        }

        int ans = 0;
        while(m-- > 0){
            String str = br.readLine();
            Node cur = root;
            for(int i = 0; i < str.length(); ++i){
                char c = str.charAt(i);
                if(cur.children[c-'a'] == null)
                    break;
                cur = cur.children[c-'a'];

                if(i == str.length()-1 && cur.isLast)
                    ans++;
            }
        }
        System.out.println(ans);
    }

    public static class Node{
        Node[] children = new Node[26];
        boolean isLast;

        public Node(){}
    }
}

문제 링크

풀이 ) BFS

  방문한 요소에 대한 재방문을 방지하기 위해 boolean 배열을 선언해줬다.

  같은 depth에 있는 요소를 방문할 때 2배할때는 depth가 더 깊어지지 않기 때문에 queue의 앞에 삽입해주기 위해 deque를 사용했다.

  size만큼의 요소를 방문하면 depth가 늘어나기 때문에 앞에 삽입한 이후 size를 늘려준다.

  나중에 찾아보니 이런 방식으로 0-1BFS라고 한다고 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] in = br.readLine().split(" ");

        int n = Integer.parseInt(in[0]), k = Integer.parseInt(in[1]);
        boolean[] visited = new boolean[100001];
        if(k <= n){
            System.out.println(n-k);
            return;
        }

        Deque<Integer> deq = new ArrayDeque<>();
        deq.offer(n);
        int ans = -1;
        while(!deq.isEmpty()){
            ans++;
            int size = deq.size();
            while(size-- > 0){
                int cur = deq.poll();
                if(cur == k){
                    System.out.println(ans);
                    return;
                }
                visited[cur] = true;

                int tmp = cur*2;
                if(tmp <= 100000 && !visited[tmp]){
                    deq.offerFirst(tmp);
                    size++;
                }
                tmp = cur+1;
                if(tmp <= k && !visited[tmp])
                    deq.offerLast(tmp);

                tmp = cur-1;
                if(0 <= tmp && tmp <= 100000 && !visited[tmp])
                    deq.offerLast(tmp);
            }
        }
    }
}

주의 )

  처음에 위치를 x에서 x-1로 이동함에 있어서 k보다 큰 경우만 가능하도록 했지만 예제와 같이

  5 - 10 - 9 - 18 - 17에서 10 - 9와 같이 목표인 17보다 작아도 내려가는 경우가 있어서 다시 처리해줬다.

문제 링크

풀이 )

  트라이라는 자료구조를 공부한 다음에 풀었다.

  트라이는 k진 트리의 구조를 띄고 있고, 접두어를 찾을 때 효율적인 자료구조이다.

  root 노드를 시작으로 입력받은 숫자를 한자리씩 노드에 추가한다.

  1번 예제에서는 root를 시작으로 911에 대해서 9를 root의 자식 노드로 추가하고 9의 자식에 1, 1의 자식에 1을 추가한 뒤 마지막 1에서 마지막이라는 것을 표시한다.

  97625999은 현재 root에 9가 있기 때문에 9로 이동하고, 이후에 7이 없기 때문에 노드를 추가한 후 이후에도 같은 방식으로 한다.

  마지막 91125426에 대해서는 root에서 9로 이동한 후 1 1을 따라가면 1에 마지막 표시가 있기 때문에 NO를 출력한다.

   root

/

9

|     \

1        7

|          |

1         6

|          |

2         2

|          |

5         5

|          |

4         9

|          |

2         9

|          |

6         9

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        while(t-- > 0){
            Node root = new Node();

            boolean flag = false;
            int n = Integer.parseInt(br.readLine());
            while(n-- > 0){
                Node cur = root;
                char[] number = br.readLine().toCharArray();
                if(flag == true)
                    continue;
                for(int i = 0; i < number.length; ++i){
                    char num = number[i];
                    if(i == number.length-1)
                        if(cur.children[num-'0'] != null){
                            flag = true;
                            break;
                        }

                    if(cur.children[num-'0'] == null)
                        cur.children[num-'0'] = new Node();
                    cur = cur.children[num-'0'];

                    if(cur.isLast){
                        flag = true;
                        break;
                    }
                    if(i == number.length-1)
                        cur.isLast = true;
                }
            }
            if(flag)
                sb.append("NO\n");
            else
                sb.append("YES\n");
        }
        System.out.print(sb);
    }

    static class Node{
        Node[] children = new Node[10];
        boolean isLast;

        public Node() {}
    }
}

주의 )

  중간에 NO를 출력하기 위해 break를 했을 때 n번 입력받는 while을 탈출해서 런타임에러가 났었다.

  자주하는 실수라 기억해둬야할 것 같다.

문제 링크

풀이 )

  가장 큰 수를 두개 뽑아 곱했을때가 다른 두 수를 곱했을 때보다 결과가 크기 때문에 우선 내림차순으로 정렬했다.

  이후 앞에서부터 두 수를 뽑아 곱한다.

  이 때 1과 0은 다른 양수와 곱해지는 경우 곱이 합보다 작아지게 되므로 1부터 예외처리해준다.

  n * 1 < n + 1, n * 0 < n + 0

  음수 2개를 곱하는 경우 양수가 되기 때문에 그 값을 최대로 만들기 위해 절댓값이 큰 끝부터 2개씩 곱하면서 더한다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];

    sort(v.begin(), v.end(), greater<int>());
    int ans = 0;

    int i = 0;
    for(; i < n; i+=2){
        if(v[i+1] <= 1)
            break;
        ans += v[i]*v[i+1];
    }
    for(; i < n; ++i){
        if(v[i] < 1)
            break;
        ans += v[i];
    }

    int j = n-1;
    for(; j > i; j-=2)
        ans += v[j]*v[j-1];
    if(i == j)
        ans += v[j];

    cout << ans << '\n';
}

문제 링크

풀이 )

  현재 입력받은 수에 대해서 한 자리씩 숫자를 하나씩 바꿔가면서 BFS를 한다.

  같은 수를 다시 Queue에 넣는 것을 방지하기 위해 visited 배열을 사용하여 방문 여부를 확인하여 방문한 경우 Queue에 넣지 않는다.

  한 자리씩 바꾸는 경우 현재 수 num, 자릿수 digit, 바꾸자하는 수 i를 매개변수로 받아 결과값을 반환하는 make( )를 만들었다. (제곱을 구하는 pow( )에서는 밑을 10으로 고정하여 지수만 입력받아 반환하도록 했다.)

  ex ) 1234에서 10^2의 자리수 2를 7로 바꾼다하면 make(1234, 2, 7)을 호출한다.

         1734바꾸면 되므로

• 10^2보다 큰 자리에 대해선 그대로 두기 위해 num/pow(digit+1)*pow(digit+1)
• 10^2자리에서는 pow(digit)*i
• 10^2이하 자리에서는 num%pow(digit);

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

bool prime[10000];

int pow(int num){
    if(!num)
        return 1;
    return 10*pow(num-1);
}

int make(int num, int digit, int i){
    return (num/pow(digit+1)*10+i)*pow(digit)+num%pow(digit);
}

int main(void){

    for(int i = 1000; i < 10000; ++i){
        prime[i] = true;
        for(int j = 2; j < 100; ++j){
            if(i%j==0){
                prime[i] = false;
                break;
            }
        }
    }

    int t;
    cin >> t;
    int a, b;
    while(t--){
        cin >> a >> b;

        queue<pair<int, int> > q;   // 숫자, 단계
        bool visited[10000] = {false, };
        q.push({a, 0});
        visited[a] = true;
        while(1){
            int tmp = q.front().first;
            int cnt = q.front().second;
            if(tmp == b){
                cout << cnt << '\n';
                break;
            }
            visited[tmp] = true;
            q.pop();

            for(int digit = 0; digit < 4; ++digit){
                for(int i = 0; i < 10; ++i){
                    if(digit == 3 && i == 0)
                        continue;
                    a = make(tmp, digit, i);
                    if(visited[a] || !prime[a])
                        continue;
                    q.push({a, cnt+1});
                }
            }
        }
    }
}