BOJ - USC Spring 2019

-
문제들(링크)

영어로 된 문제 세트들입니다.
ICPC 같은 국제대회에선 거의 모든 문제가 영어로 출제되기에 감을 익혀볼 겸 풀어보는 것도 좋은 것 같습니다.

A번 - Cap Size(17659번)

0부터 1000 사이의 모자 크기를 주고, 주인공에게 딱 맞거나 맞을 것 같은 모자의 개수를 찾는 문제입니다.
모자의 크기와 숫자가 주어지는데, 의미는 다음과 같습니다.

숫자가 1 -> 주인공의 머리가 그 모자보다 크다.
숫자가 0 -> 딱 맞는 모자이다.(단, 딱 맞는 모자는 이 모자밖에 없습니다.)
숫자가 -1 -> 주인공의 머리가 그 모자보다 작다.

capSize[1001] 의 배열을 선언하고 1과 -1 사이의 모자 개수를 세주면 됩니다.
단, 논리적으로 말이 안되는 입력이면 "Inconsistent feedback" 을 출력해야 하는데, 
예외 상황이 좀 많습니다.

1. 숫자 0이 각각 다른 모자에 주어질 때 -> 딱 맞는 모자는 하나 뿐
2. 숫자가 이미 주어졌는데 다른 숫자가 또 주어질 때
3. 숫자 0이 주어진 모자보다 큰 모자가 1을 가질 때
4. 숫자 0이 주어진 모자보다 작은 모자가 -1을 가질 때
5. -1이 1 보다 앞에 올 때
6. 같은 모자에 같은 숫자가 계속 주어질 때 -> 맞는 입력입니다.





코드

import java.io.*;
import java.util.*;

public class Main {

    public static int N, T;

    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            T = Integer.parseInt(st.nextToken());

            int[] capSize = new int[1001];
            Arrays.fill(capSize, -2);

            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N ; j++) {
                capSize[Integer.parseInt(st.nextToken())] = 2;
            }

            boolean impo = false;
            int cnt = 0;
            int p_idx = 0;
            for (int j = 0; j < T ; j++) {
                st = new StringTokenizer(br.readLine());
                int c = Integer.parseInt(st.nextToken());
                int f = Integer.parseInt(st.nextToken());

                if(capSize[c] == 2)
                    capSize[c] = f;
                else if(capSize[c] == f)
                    continue;
                else
                    impo = true;
            }
            bw.write("Data Set " + (i + 1) + ":\n");

            if(!impo) {
                int largeIdx = -1;
                int smallIdx = 1001;
                int fit_cnt = 0;

                for (int j = 0; j <= 1000; j++) {
                    if(capSize[j] == 1)
                        largeIdx = Math.max(largeIdx, j);
                    if(capSize[j] == -1)
                        smallIdx = Math.min(smallIdx, j);
                    if(capSize[j] == 0) {
                        fit_cnt++;
                        p_idx = j;
                    }
                }

                if(fit_cnt == 0) {

                    if(largeIdx < smallIdx){
                        for (int j = largeIdx + 1; j < smallIdx ; j++) {
                            if(capSize[j] == -2)    continue;
                            cnt++;
                        }
                    }
                    else
                        impo = true;
                }
                else if(fit_cnt == 1){
                    cnt = 1;
                    if(p_idx >= smallIdx || p_idx <= largeIdx)
                        impo = true;
                }
                else
                    impo = true;

                if(!impo)
                    bw.write(cnt + "\n\n");
                else
                    bw.write("Inconsistent feedback\n\n");
            }
            else
                bw.write("Inconsistent feedback\n\n");
        }
        bw.flush();
        bw.close();
    }
}


B번 - First-Name Basis(17660번)

여러 개의 first 이름과 second 이름이 주어졌을 때, first 이름은 first 이름으로만, second 이름은 second 이름으로만 사용되게끔 이름을 반전시켜 주어야 하는데, 이 때 최소한의 반전 횟수를 구하는 문제입니다.

즉,
5
a b
a c
c d
d d
d e
입력의 정답은 (a , b) , (a , c) 두 세트를 반전시켜주면 되기 때문에 2입니다.

 풀이 코드는 http://contest.usc.edu/index.php/Main/Spring2019USCProgrammingContest?action=download&upname=sp19.first.hemant.java.txt 를 참고했습니다.

입력이 String으로 들어오기 때문에 HashMap 을 이용했고, 이분 그래프를 만들기 위해 입력값들을 양방향 그래프로 이어 주었습니다.
위의 입력은 다음과 같습니다.(양방향 그래프이기때문에 방향은 표시하지 않았습니다.)
이제 위 그래프를 이분 그래프로 바꾸어 색칠하면 다음과 같습니다.
이제 위 이분 그래프에서 정답을 어떻게 찾느냐가 문제인데, 먼저 이분 그래프를 만들 때 "Impossible" 의 경우는 걸러지게 됩니다.("Impossible" 인 경우 색깔이 겹치게 됩니다.)

정답을 찾기 위해 위의 입력을 다시 사용해야 합니다.(따로 배열에 저장합니다.)
이 문제에서 정답은 결국 first 이름은 모두 빨강(or 파랑) , second 이름은 모두 파랑(or 빨강) 이 되게끔 입력값들을 반전시켜 주는 것입니다.

입력 배열을 모두 보면서, first 이름의 색깔에 따라 색의 count를 각각 증가시킵니다.
위 입력에선 a,a,c,b,b 이므로 빨강 = 2개, 파랑 = 3개가 됩니다.
즉,  빨강 2개만 반전시켜 주면(파랑으로 만들면) 최소값을 구할 수 있습니다!

단, 문제에서 하나의 그래프가 나오는게 아니라 여러개의 그래프 집합이 만들어지므로 각각의 그래프에서 위 작업을 수행한 뒤 더해주어야 합니다.






코드

import java.io.*;
import java.util.*;

public class Main {

    public static int N;
    public static ArrayList<Node> tree;
    public static HashMap<String, Integer> hm;
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K ; i++) {
            bw.write("Data Set " + (i + 1) + ":\n");

            N = Integer.parseInt(br.readLine());
            tree = new ArrayList<>();
            hm = new HashMap<>();

            StringTokenizer st;
            int idx = 0;
            int[][] query = new int[N][2];

            for (int j = 0; j < N ; j++) {
                st = new StringTokenizer(br.readLine());
                String first = st.nextToken();
                String second = st.nextToken();

                if(!hm.containsKey(first)){
                    tree.add(new Node(idx));
                    hm.put(first, idx++);
                }
                if(!hm.containsKey(second)){
                    tree.add(new Node(idx));
                    hm.put(second, idx++);
                }
                int from = hm.get(first);
                int to = hm.get(second);
                query[j][0] = from;
                query[j][1] = to;

                tree.get(from).next.add(tree.get(to));
                tree.get(to).next.add(tree.get(from));
            }
            int setNum = binary();
            if(setNum == -1)
                bw.write("Impossible\n\n");
            else{
                int[][] answer = new int[setNum][2];
                //각 집합마다의 정답이 저장됩니다.

                for (int[] temp : query) {
                    //각 입력에서 첫 번째 문자의 색깔에 따라 분류해서 카운트합니다.
                    int first = temp[0];
                    if(tree.get(first).color == 0)
                        answer[tree.get(first).setNum][0]++;
                    else
                        answer[tree.get(first).setNum][1]++;
                }
                int res = 0;
                for (int[] cost : answer) {
                    res += Math.min(cost[0], cost[1]);
                }
                bw.write(res + "\n\n");
            }
        }
        bw.flush();
        bw.close();
    }
    public static int binary(){
        int set = 0;
        for (int i = 0; i < tree.size() ; i++) {
            if(tree.get(i).color != -1) continue;
            //이미 색칠된 집합이면 continue
            tree.get(i).setNum = set;
            set++;
            tree.get(i).color = 0;
            Queue<Node> q = new LinkedList<>();
            q.offer(tree.get(i));

            while(!q.isEmpty()){
                Node now = q.poll();

                for (int j = 0; j < tree.get(now.num).next.size() ; j++) {
                    Node next = tree.get(now.num).next.get(j);

                    if(now.color == next.color) return -1;
                    if(next.color != -1)    continue;
                    next.setNum = now.setNum;
                    next.color = 1 - now.color;
                    q.offer(next);
                }
            }
        }
        return set;
    }
}

class Node{
    int num;
    int setNum;
    int color = -1;
    ArrayList<Node> next;
    public Node(int num){
        this.num = num;
        next = new ArrayList<>();
    }
}

C번 - Mangling Names(17661번)

 주어지는 단어마다 모음의 개수와 자음의 개수를 세고 2차원 배열에 맞게 값을 더해주면 되는 간단한 문제입니다.
2차원 배열 cost[i][j] 의 의미는 모음 i 개, 자음 j 개일 때의 값입니다.






코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static int N, M;
    public static int[][] time;
    public static void main(String[] argc) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int K = Integer.parseInt(br.readLine());

        for (int i = 0; i < K ; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            time = new int[N + 1][N + 1];

            for (int j = 0; j < N + 1 ; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < N + 1 ; k++) {
                    time[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            int res = 0;
            for (int j = 0; j < M ; j++) {
                String now = br.readLine();

                res += sum(now);
            }

            bw.write("Data Set " + (i + 1) + ":\n");
            bw.write(res + "\n\n");
        }
        bw.flush();
        bw.close();
    }
    public static int sum(String s){
        int vowel = 0;
        int cons = 0;

        for (int i = 0; i < s.length() ; i++) {
            if(s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'o' || s.charAt(i) == 'y' || s.charAt(i) == 'i' || s.charAt(i) == 'u')
                vowel++;
            else
                cons++;
        }
        return time[vowel][cons];
    }
}




댓글

댓글 쓰기

이 블로그의 인기 게시물

HTML - input file 버튼 꾸미기

-
이미지
 이번 글에선 HTML 에서 기본적으로 제공하는 input 태그의 file 속성일 때의 모양을 바꿔보려고 한다. 열심히 구글링을 해본 결과 보안상의 문제로 직접 input 태그에 변경을 가할 수는 없다고 한다. 따라서 input 태그에 속성을 넣는 게 아닌 약간의 편법?을 이용해서 업로드 버튼처럼 보이게 만들어야 한다. 먼저, 파일의 이름을 출력할 가짜 input 태그를 넣자. <input type= "text" id= "file_route" disabled= "disabled" value= "파일 선택" > value 에 안내 문구를 넣었고, disabled를 지정했기 때문에 커서를 옮겨도 아무 것도 할 수 없다. 잘 생성됐다. 이제 오른쪽 버튼과 "선택된 파일 없음" 문구를 없애고 새 버튼을 만들어야 하는데 label과 style 속성을 잘 활용해서 없애보자. <input type= "text" id= "file_route" disabled= "disabled" value= "파일 선택" > <label for= "upload_file" style= "border: solid 1px black;" > 업로드 </label> <input type= "file" id= "upload_file" accept= "image/*" required= true style= "position:absolute; clip:rect(0, 0, 0, 0);" > label 태그는 for 속성으로 연결한 id의 태그와 자신(라벨)을 연결해 준다. 즉, "업로드" 를 클릭해도 input 태그를 클릭한 것...
자세한 내용 보기

HTML - 이미지 미리보기(jQuery 없이)

-
이미지
 최근에 웹 클론 코딩을 하면서 이미지 미리보기 기능을 구현해야 됐는데 구글링해서 나온 대부분이 제이쿼리를  이용한 코드여서 찾는데 애를 좀 먹었다. 이 글에선 제이쿼리를 쓰지 않고 이미지 미리보기를 구현해보려고 한다. 먼저, 기본으로 제공되는 input 태그와 미리보기를 하기 전 기본 이미지를 띄워보자. <img src= "고양이.jpg" id= "img_section" style= "width: 400px; height: 400px;" > <br> <input type= "file" id= "upload_file" accept= "image/*" required= true value= "업로드" > src 는 본인이 원하는 기본 이미지 경로로 설정해주면 된다. (어차피 나중에 src 속성을 바꿔서 이미지가 변경됨!) id , style 등등 나머지 속성을 지정해주자. 아직은 이미지와 input 버튼만 만들었기 때문에 파일을 아무리 업로드해도 아무 변화가 없다. 이제 동적으로 img 태그의 src 를 바꿔주는 스크립트를 작성해보자. <img src= "고양이.jpg" id= "img_section" style= "width: 400px; height: 400px;" > <br> <input type= "file" id= "upload_file" accept= "image/*" required= true value= "업로드" > <script> const reader = new FileReader(); reader.o...
자세한 내용 보기

BOJ - DNA 유사도(2612)

-
문제(링크) LCS 알고리즘 응용문제입니다. dp[i][j] = i, j 지점에서 나올 수 있는 최대 유사도 공백을 추가할 때, 현재 유사도가 음수가 되버리면 그 지점부터 다시 시작하는게 이득입니다. 따라서 lcs 알고리즘과 비슷하게 문자가 같지 않다면 왼쪽, 왼쪽 위, 위 값의 최댓값을 현재 값으로 가져오는데 해당 값에 공백을 추가한 값, 즉, -2 를 한 값을 가져오고 최종 값이 음수가 되면 0으로 바꿔줘야 합니다. 문자가 같다면 lcs 알고리즘에서 처럼 +3을 해줍니다. dp 배열을 완성했다면 유사도가 최대인 점을 찾습니다. 최대인 점으로부터 가로, 세로, 대각선을 체크하면서 시작 점을 찾아가는데, 가로, 세로는 +2 , 대각선은 -3 으로 찾아가면서 0이 될때까지 찾아가고, 역으로 시작점부터 끝점까지 출력하면 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector<pii> #define IMAX 2000000001 #define LM...
자세한 내용 보기