[SWEA] 1289. 원재의 메모리 복구하기 D3 - Array

제출일 : 2019-07-16

문제 풀이 시간 : 15M

난이도 : ★☆

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 메모리의 원래 값이 주어진다.

메모리의 길이는 1이상 50이하이다.

Output

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

초기값(모든bit가 0)에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

Example

input

2
0011
100

output

#1 1
#2 2

Solution & Inpression

문제에서 초기값은 모든 비트가 0이라고 정해져있다.

오른쪽부터 현재 메모리의 값(해당 비트의 값)이 복구하고자 하는 메모리 값이 아니라면 바꾸고자 하는 값으로 현재비트부터 첫번째 비트까지 값을 바꾸어 준다.

위작업을 비트수만큼 진행한다.

Code

언어 : JAVA

메모리 : 20,540 kb

실행시간 : 138 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;
import java.lang.reflect.Array;

public class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for(int tc = 1; tc <= T; tc++){

            char[] input = sc.next().toCharArray(); 
            char[] tmp = new char[input.length()];

            int cnt=0;

            for(int i =0 ; i<input.length();i++) {
                tmp[i]='0';
            }


            for(int i =0 ; i<input.length();i++) {
                if(input[i]!=tmp[i]) {
                    char tmpNum=input[i];
                    for(int j=i; j<input.length();j++) {
                        tmp[j]=tmpNum;
                    }
                    cnt++;
                }       
            }
            System.out.println("#" + tc + " " + cnt);
        }
    }
}

[SWEA] 1204. 최빈수 구하기 D2 - Array

제출일 : 2019-07-16

문제 풀이 시간 : 15M

난이도 : ★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV13zo1KAAACFAYh

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 테스트 케이스의 번호가 주어지고 그 다음 줄부터는 점수가 주어진다.

Output

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

Constraints

학생의 수는 1000명이며, 각 학생의 점수는 0점 이상 100점 이하의 값이다.

Example

input

10
1
41 85 72 38 80 69 65 68 96 22 49 67 51 61 63 87 66 24 80 83 71 60 64 52 90 60 49 31 23 99 94 11 25 24 51 15 13 39 67 97 19 76 12 33 99 18 92 35 74 0 95 71 39 33 39 32 37 45 57 71 95 5 71 24 86 8 51 54 74 24 75 70 33 63 29 99 58 94 52 13 35 99 46 57 71 23 17 3 94 48 77 18 83 11 83 25 59 62 2 78 86 7 94 65 80 32 39 84 60 65 72 61 58 84 8 72 12 19 47 49 49 59 71 52 34 22 21 20 92 33 80 39 74 9 28 97 100 93 29 25 4 66 79 81 98 21 91 62 82 4 59 100 34 1 51 80 92 69 77 39 38 97 51 34 35 19 22 1 67 9 90 31 82 11 51 84 78 70 74 42 100 88 53 80 57 62 32 51 48 63 92 46 4 61 31 98 69 52 88 20 68 41 48 79 97 98 56 44 73 3 63 100 87 87 41 79 64 83 63 1 21 72 24 9 75 51 25 53 77 0 52 30 96 93 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 2 20 68 22 29 10 1 23 19 47 16 76 47 49 90 94 10 18 55 69 14 26 59 77 73 8 21 72 1 74 76 51 94 44 24 98 71 77 59 9 12 49 38 72 22 55 35 61 16 48 41 21 67 74 92 4 7 85 34 92 39 96 42 26 1 1 4 64 33 96 62 23 67 76 26 47 32 73 82 30 14 61 21 92 40 4 2 38 76 64 8 14 3 49 71 31 38 86 98 17 15 98 32 55 69 46 61 3 44 67 50 44 76 0 45 23 25 11 82 99 11 39 50 40 21 52 17 60 44 90 44 6 16 38 3 41 43 56 26 24 0 9 90 36 50 13 42 88 87 66 32 28 73 94 52 11 35 47 9 87 37 57 15 56 38 95 6 43 23 30 84 39 88 69 5 34 81 93 86 2 77 10 28 30 97 68 14 12 88 1 100 35 73 30 2 43 11 41 58 82 6 84 71 16 18 67 41 100 92 78 57 7 35 69 56 76 13 93 26 26 38 21 96 7 88 2 60 17 54 95 26 2 0 21 87 11 96 36 83 88 31 24 24 62 14 88 84 39 22 17 84 96 1 78 91 53 9 35 75 87 100 33 80 42 7 20 50 65 81 92 14 45 96 34 6 20 86 51 4 19 70 91 13 0 42 70 43 15 47 14 96 72 41 91 11 72 7 92 12 16 51 13 86 40 50 43 55 26 7 1 70 18 71 99 49 55 94 78 40 59 20 96 34 6 28 85 42 70 62 63 32 34 97 80 49 47 50 73 85 63 20 29 0 19 91 84 58 55 33 4 68 55 12 38 49 9 13 99 4 35 26 5 42 29 98 20 95 77 36 63 41 42 45 81 40 53 60 5 55 9 13 34 6 52 28 35 33 29 21 67 57 61 21 41 95 54 50 19 81 75 67 73 77 47 40 83 16 28
.......

output

#1 71
#2 76
.......

Solution & Inpression

제약 사항을 보면 학생수는 1000명이고 학생의 점수는 0~100 사이의 값으로 0점부터 100점까지의 점수를 받은 학생수를 저장할 배열의 크기를 101로 해당 점수를 맞은 학생수를 하나씩 증가시켜 최종적으로 배열에서 가장 큰 값을 출력하였다.

Code

언어 : JAVA

메모리 : 52,420 kb

실행시간 : 202 ms

import java.util.Arrays;
import java.util.Scanner;
import java.io.FileInputStream;

public class Solution{
    public static void main(String args[]) throws Exception {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();


        for (int i = 1; i <= N; i++) {
            int num = s.nextInt();
            int[] array = new int[1000]; 

            for (int j = 0; j < 1000; j++) { 
                array[j] = s.nextInt();
            }


            int[] countarray = new int[101];

            for (int j = 0; j < 1000; j++) {
                countarray[array[j]]++; 
            }

            int result = 0;
            int temp = 0;

            for (int j = 100; j >= 0; j--) {
                if (result < countarray[j]) {
                    result = countarray[j];
                    temp = j;
                }
            }

            System.out.println("#" + num + " " + temp);

        } 
    }
}

[BOJ] 5427. 불 - BFS

제출일 : 2019-09-04

문제 풀이 시간 : 1H 15M

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/5427

Input

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

Output

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 IMPOSSIBLE을 출력한다.

Example

input

5
4 3
####
#*@.
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#....*#
#@....#
.######
5 5
.....
.***.
.*@*.
.***.
.....
3 3
###
#@#
###

output

2
5
IMPOSSIBLE
IMPOSSIBLE
IMPOSSIBLE

Solution & Inpression

BFS 응용 문제.불이 먼저 퍼지고 사람이 이동. 한턴 한턴 수행하면 쉽게 풀리는 문제였지만 처음부터 생각하기 힘들었던 문제.

Code

언어 : JAVA

메모리 : 119,172 kb

실행시간 : 720 ms

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class pos {
        int y;
        int x;

        pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("res/백준_5427_불.txt"));
        int dy[] = { -1, 1, 0, 0 };
        int dx[] = { 0, 0, 1, -1 };
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        Queue<pos> fire = new LinkedList<>();
        Queue<pos> me = new LinkedList<>();
        for (int tc = 1; tc <= T; tc++) {
            me.clear();
            fire.clear();
            boolean flag = false;
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            char[][] map = new char[h][w];
            boolean[][] visit = new boolean[h][w];
            int py = 0, px = 0, flame = 0, per = 0;
            for (int y = 0; y < h; y++) {
                map[y] = br.readLine().toCharArray();
                for (int x = 0; x < w; x++) {
                    if (map[y][x] == '*') {
                        fire.offer(new pos(y, x));
                    } else if (map[y][x] == '@') {
                        visit[y][x] = true;
                        me.offer(new pos(y, x));
                        map[y][x] = '.';
                    }
                }
            }
            int result = 0;
            while (!me.isEmpty()) {
                result++;
                flame = fire.size();
                for (int f = 0; f < flame; f++) {// 불을 먼저 붙여버리겠음
                    int y = fire.peek().y;
                    int x = fire.peek().x;
                    fire.poll();
                    for (int i = 0; i < 4; i++) {
                        int ny = y + dy[i];
                        int nx = x + dx[i];
                        if (ny >= 0 && nx >= 0 && ny < h && nx < w && map[ny][nx] == '.') {
                            map[ny][nx] = '*';
                            fire.offer(new pos(ny, nx));
                        }
                    }
                }

                per = me.size();
                for (int pidx = 0; pidx < per; pidx++) {
                    py = me.peek().y;
                    px = me.peek().x;
                    me.poll();
                    if ((py == 0 || px == 0 || py == h - 1 || px == w - 1)) { // 다음번에 바로간다
                        flag = true;
                        me.clear();
                        break;
                    }
                    for (int i = 0; i < 4; i++) {
                        int npy = py + dy[i];
                        int npx = px + dx[i];
                        if (npy >= 0 && npx >= 0 && npy < h && npx < w && map[npy][npx] == '.' && !visit[npy][npx]) {
                            me.offer(new pos(npy, npx));
                            visit[npy][npx] = true;
                        }
                    }
                }
            }
            if (flag)
                System.out.println(result);
            else
                System.out.println("IMPOSSIBLE");
        }
    }
}

[BOJ] 6593. 상범빌딩 - BFS

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://www.acmicpc.net/problem/6593

Input

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다.

Output

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다.

Escaped in x minute(s).

여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다.

만일 탈출이 불가능하다면, 다음과 같이 출력한다.

Trapped!

Example

input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

output

Escaped in 11 minute(s).
Trapped!

Solution & Inpression

2차원 배열의 BFS문제들과 비슷하게 풀어나갔다. 다만 탐색을 6방향으로 해야 문제를 해결할 수 있다.

Code

언어 : JAVA

메모리 : 18,104kb

실행시간 : 148ms

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

public class Main {
    static int L, R, C;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            if (L == 0)
                break;

            char[][][] building = new char[L][R][C];
            boolean visit[][][] = new boolean[L][R][C];
            Queue<int[]> q = new LinkedList<int[]>();
            for (int k = 0; k < L; k++) {
                for (int i = 0; i < R; i++) {
                    String str = br.readLine();
                    for (int j = 0; j < C; j++) {
                        char cur = str.charAt(j);
                        building[k][i][j] = cur;
                        if (cur == 'S') {
                            q.offer(new int[] { k, i, j, 0 });
                            visit[k][i][j] = true;
                        }
                    }
                }
                br.readLine();
            } // 입력 끝

            int[] dk = { -1, 1, 0, 0, 0, 0 };
            int[] dx = { 0, 0, -1, 1, 0, 0 };
            int[] dy = { 0, 0, 0, 0, -1, 1 };
            int res = Integer.MAX_VALUE;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                 //System.out.println(Arrays.toString(cur));
                if (building[cur[0]][cur[1]][cur[2]] == 'E') {
                    res = (cur[3] > res) ? res : cur[3];
                    continue;
                }
                for (int k = 0; k < 6; k++) {
                    int l = cur[0] + dk[k];
                    int x = cur[1] + dx[k];
                    int y = cur[2] + dy[k];
                    if (range(l, x, y) && !visit[l][x][y] && building[l][x][y] != '#') {
                        visit[l][x][y] = true;
                        q.offer(new int[] { l, x, y, (cur[3] + 1) });
                    }
                }
            }
            System.out.println((res == Integer.MAX_VALUE) ? "Trapped!" : "Escaped in " + res + " minute(s).");

        }
    }

    private static boolean range(int l, int x, int y) {
        if (0 <= l && l < L && 0 <= x && x < R && 0 <= y && y < C)
            return true;
        return false;
    }
}

[SWEA] 1263. 사람 네트워크2 D6 - Floyed Warshall

제출일 : 2019-09-23

문제 풀이 시간 : 1H

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN

Input

맨 위의 줄에는 전체 테스트 케이스의 수 T가 주어진다.

그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄에 주어지며, 사람 수인 양의 정수 N이 주어진 다음, 사람 네트워크의 인접 행렬이 행 우선 (row-by-row) 순으로 주어진다.

단, 각 숫자 사이에는 1개의 공백이 주어진다.

Output

총 T줄에 T개의 테스트 케이스 각각에 대한 답을 한 줄에 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 사람 그래프에서 사람들의 CC 값들 중에서 최솟값을 한 줄에 출력한다.

Constraints

입력으로 주어지는 사람 네트워크에서 노드 자신을 연결하는 간선은 없다.

또한 사람 네트워크는 하나의 연결 요소(connected component)로 구성되어 있다.

단, 사람 네트워크의 최대 사용자 수는 1,000 이하이다.

테스트 케이스들은 아래의 그룹들로 이루어져 있다.

그룹 1 싸이클이 없고 N <= 10 인 경우
그룹 2 싸이클이 없고 10 < N <= 100 인경우
그룹 3 싸이클이 있고 N<= 10
그룹 4 싸이클이 있고10 < N <= 100
그룹 5 모든 경우가 존재하고 100 < N <= 1000

Example

input

20
5 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0
5 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 0
...

output

#1 4
#2 5
…

Solution & Inpression

플루이드 워샬 알고리즘을 이용하여 해결하였다.

Code

언어 : JAVA

메모리 : 120,644 kb

실행시간 : 3,686 ms

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

public class Solution {

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("res/D6_1263_사람네트워크2.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            System.out.print("#" + tc + " ");
            int N = sc.nextInt();
            int[][] matrix = new int[N][N];
            int INF = 987654321;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    if (i != j && tmp == 0)
                        matrix[i][j] = INF;
                    else
                        matrix[i][j] = tmp;
                }
            }

            for (int k = 0; k < N; k++) {
                for (int i = 0; i < N; i++) {
                    if (k == i)
                        continue;
                    for (int j = 0; j < N; j++) {
                        if (j == k || i == k)
                            continue;
                        if ((matrix[i][k] + matrix[k][j]) < matrix[i][j])
                            matrix[i][j] = matrix[i][k] + matrix[k][j];
                    }
                }
            }
            int min = INF;
            for (int i = 0; i < N; i++) {
                int sum = 0;
                for (int j = 0; j < N; j++) {
                    sum += matrix[i][j];
                }
                if (sum < min) {
                    min = sum;
                }
            }
            System.out.println(min);
        }
    }
}

[SWEA] 1486. 장훈이의 높은 선반 D4 - PowerSet

제출일 : 2019-08-22

문제 풀이 시간 : 2H 30M

난이도 : ★★★

Problem

link : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

Input

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)가 공백으로 구분되어 주어진다.

S는 두 번째 줄에서 주어지는 점원들 키의 합이다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지며, 각 정수는 각 점원의 키 Hi (1 ≤ Hi ≤ 10,000)을 나타낸다.

Output

각 테스트 케이스마다 첫 번째 줄에는 ‘#t’(t는 테스트 케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 만들 수 있는 높이가 B 이상인 탑 중에서 탑의 높이와 B의 차이가 가장 작은 것을 출력한다.

Example

input

1
5 16
1 3 3 5 6

output

#1 1

Solution & Inpression

DFS로도 해결 할 수 있었지만 PowerSet(멱집합)을 이용하여 해결 하였다.

Code

언어 : JAVA

메모리 : 19,768 kb

실행시간 : 182 ms

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

public class Solution{
    public static int N, B, result;
    public static int[] high;

    public static void sol() {
        int i, j;
        for (i = 0; i < (1 << N); ++i) {
            int sum = 0;
            for (j = N - 1; j >= 0; --j) {
                // System.out.print(((i >> j) & 1));
                if (((i >> j) & 1) == 1)
                    sum += high[j];
            }
            // System.out.println();
            if (sum >= B)
                result = (result > sum) ? sum : result;
        }
    }

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

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

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // N, B(1 ≤ N ≤ 20, 1 ≤ B ≤ S)
            N = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());

            high = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++)
                high[i] = Integer.parseInt(st.nextToken());

            result = Integer.MAX_VALUE;
            sol();

            System.out.println("#" + tc + " " + (result - B));
        }
        br.close();
    }
}