Red Glitter Pointer

 

 

6236번: 용돈 관리

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로

www.acmicpc.net

 

 

 

👇 내가 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] account = new int[N];

        for(int i = 0; i < N; i++) {
            account[i] = Integer.parseInt(br.readLine());
        }

        int left = Arrays.stream(account).max().getAsInt(); // 모든 지출 중 최대값
        int right = Arrays.stream(account).sum(); // 모든 지출의 합
        int K = 0;

        while(left <= right) {
            int mid = (left + right) / 2; // 날짜 별 지출을 mid 금액으로 커버할 수 있는지 확인
            int sum = 0;
            int count = 1; // 인출 횟수

            for(int money : account) {
                // 현재까지의 sum에 다음 일자의 금액을 더했을 때, mid보다 크다면 재인출
                // 현재 인출한 금액으로는 다음 일자의 금액을 충당할 수 없다는 의미
                if(sum + money > mid) {
                    count++; // 재인출
                    sum = 0;
                }
                sum += money; // 현재일자 금액 더하기
            }

            // 인출 횟수가 M이하인지 검색하고 가능한 최소 금액 찾기
            // 인출 금액을 줄여볼 수 있는 여지가 있음
            if(count <= M) {
                right = mid - 1;
                K = mid;
            } else left = mid + 1;
            // count가 M보다 크다면, 인출 횟수가 너무 많다는 얘기. == mid 금액 증가
        }
        System.out.println(K);
    }
}

 

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을

www.acmicpc.net

 

 

👇 내가 제출한 코드

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

public class Main {
    static int N, M;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int[][] ocean;
    static boolean[][] visited;
    static List<int[]> icebergs = new ArrayList<>();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ocean = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                ocean[i][j] = Integer.parseInt(st.nextToken());
                if(ocean[i][j] > 0) {
                    icebergs.add(new int[] {i, j}); // 빙산 좌표 저장
                }
            }
        }

        int time = 0;
        while(!icebergs.isEmpty()){
            time++; // 빙산 분리되는 시간
            melting(); // 빙산 녹이기

            if(searchSplit()) {
                System.out.println(time);
                return;
            }
        }
        System.out.println(0);
    }
    public static void melting() {
        int[][] tempMap = new int[N][M];
        List<int[]> nextIcebergs = new ArrayList<>();

        // 빙산 좌표 돌면서 얼마나 녹일지 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            int melt = 0;
            for(int d = 0; d < 4; d++) {
                int nx = dr[d] + x;
                int ny = dc[d] + y;

                if(nx >= 0 && ny >= 0 && nx < N && ny < M && ocean[nx][ny] == 0) melt++;
            }
            // 녹인 후 빙산의 높이 임시배열에 저장해두기
            tempMap[x][y] = Math.max(0, ocean[x][y] - melt);
            // 다 녹지 않았다면 좌표 저장
            if(tempMap[x][y] > 0) nextIcebergs.add(new int[] {x, y});
        }

        icebergs = nextIcebergs; // 빙산 좌표 갱신
        // 임시배열 반영하기
        for(int i = 0; i < N; i++) {
            System.arraycopy(tempMap[i], 0, ocean[i], 0, M);
        }
    }

    public static boolean searchSplit() {
        int count = 0;
        for(boolean[] row : visited) Arrays.fill(row, false); // 방문 판별 배열 초기화

        // 빙산 좌표만 dfs 돌면서 분리된 덩어리 개수 확인하기
        for(int[] iceberg : icebergs) {
            int x = iceberg[0];
            int y = iceberg[1];

            if(!visited[x][y]) {
                dfs(x, y);
                count++; // 분리된 덩어리 개수
                if(count > 1) return true;
            }
        }
        return false;
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        for(int d = 0; d < 4; d++) {
            int nx = dr[d] + x;
            int ny = dc[d] + y;

            if(nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny] && ocean[nx][ny] > 0) {
                dfs(nx, ny);
            }
        }
    }
}

 

 

느낀 점 및 정리 ✍️

1. 처음에 작성했던 코드는 분리된 빙산의 개수를 찾을 때 배열의 처음부터 끝까지 돌면서 dfs로 확인했었다. 그래서인지 59%에서 자꾸 시간초과가 떴었던 것 같기도.... ㅠㅠ

2. System.arrayscopy 메소드 아직 익숙하지 않아서 찾아봐야겠다. 원래 clone()만 썼었는데 무슨 차이가 있는지도 확인해봐야겠다. 

 

 

 

 

 

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

 

 

👇 내가 작성한 코드

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

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

        while(tc-- > 0) {
            String answer = "YES";
            int N = Integer.parseInt(br.readLine());
            String[] phone_book = new String[N];
            for(int i = 0; i < N; i++) {
                phone_book[i] = br.readLine();
            }

            Arrays.sort(phone_book); // 접두어 판별을 더 빠르게 하기 위해 정렬

            for(int i = 0; i < phone_book.length - 1; i++) {
                if(phone_book[i + 1].startsWith(phone_book[i])) {
                    answer = "NO"; // 접두어라면 NO 출력 후 for문 빠져나가기
                    break;
                }
            }
            sb.append(answer).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

느낀 점 및 정리 ✍️

1. String으로 정렬하면 동일한 접두사를 더 빠르게 찾을 수 있어서 정렬하여 탐색하고, 접두어를 찾게되면 for문을 빠져나오도록 작성하였다. 

 

 

 

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

 

 

👇 내가 작성한 코드

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

public class Main {
    static int N, M;
    static int min = Integer.MAX_VALUE;
    static int[] selected;
    static List<int[]> house = new ArrayList<>();
    static List<int[]> chicken = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        selected = new int[M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int value = Integer.parseInt(st.nextToken());
                if(value == 1) house.add(new int[] {i, j}); // 집 좌표 저장
                else if(value == 2) chicken.add(new int[] {i, j}); // 치킨가게 좌표 저장
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    public static void dfs(int L, int start) {
        if(L == M) { // 유지하는 치킨집 M개 선택 완료되면 dist 메소드 실행
            dist();
            return;
        }

        // 유지할 치킨집 M개 조합하여 selected배열에 인덱스 저장
        for(int i = start; i < chicken.size(); i++) {
            selected[L] = i;
            dfs(L + 1, i + 1);
        }
    }

    public static void dist() {
        int sum = 0;
        for(int[] h : house) {
            int tempMin = Integer.MAX_VALUE;
            for(int idx : selected) { // 유지할 치킨집 M개의 인덱스가 담겨져있는 배열
                int[] hCur = chicken.get(idx);
                int distance = Math.abs(h[0] - hCur[0]) + Math.abs(h[1] - hCur[1]); // 거리 차이 구하기
                tempMin = Math.min(tempMin, distance); // 집에서 가장 가까운 치킨집 선택
            }
            sum += tempMin; // 선택한 치킨거리 누적합
        }
        min = Math.min(sum, min); // 치킨거리 최솟값 구하기
    }
}

 

 

느낀 점 및 정리 ✍️

1. dfs에서 조합 for문 돌릴 때 원하는 방식의 조합 조건이 바로바로 떠오르질 않는다 ㅠㅜ 문제 많이 풀면서 익혀야겠다

2. 거리를 구하는 문제라 어차피 좌표만 알면 돼서 2차원 배열에 별도로 저장하지 않았다

 

 

 

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크

www.acmicpc.net

 

 

 

👇내가 작성한 코드

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

public class Main {
    static int N, M;
    static int max = Integer.MIN_VALUE;
    static int[][] map;
    static int[][] copyMap;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static Queue<int[]> q = new LinkedList<>();

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

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

        map = new int[N][M];

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

        dfs(0);
        System.out.println(max);
    }

    // 벽 세우기
    public static void dfs(int wall) {
        // 벽이 3개 세워지면, 해당 map에서 bfs돌리며 바이러스 뿌리기
        if(wall == 3) {
            bfs();
            return;
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(wall + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    // 바이러스 뿌리는 메소드
    public static void bfs() {
        copyMap = new int[N][M];

        for(int i = 0; i < N; i++) {
            copyMap[i] = map[i].clone();
            for(int j = 0; j < M; j++) {
                if(map[i][j] == 2) q.add(new int[] {i, j});
            }
        }

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0];
            int y = cur[1];

            for(int d = 0; d < 4; d++) {
                int nr = dr[d] + x;
                int nc = dc[d] + y;

                if(nr >= 0 && nc >= 0 && nr < N && nc < M && copyMap[nr][nc] == 0) {
                    copyMap[nr][nc] = 2;
                    q.add(new int[] {nr, nc});
                }
            }
        }
        safeZone(copyMap);
    }

    // 안전한 공간(0)의 칸 세고 최댓값 갱신
    public static void safeZone(int[][] copyMap) {
        int cnt = 0;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(copyMap[i][j] == 0) cnt++;
            }
        }
        max = Math.max(max, cnt);
    }
}

 

 

느낀 점 및 정리 ✍️

1. DFS를 이용하여 벽 3군데 세운 뒤, 해당 2차원 배열을 BFS로 돌며 바이러스 뿌린다. 바이러스 뿌리는 배열은 clone해서 사용하였음. 다 뿌린 뒤 안전한 영역의 칸을 세고, 최댓값 갱신해주었다.

 

 

 

 

15565번: 귀여운 라이언

꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의

www.acmicpc.net

 

 

👇 내가 작성한 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] doll = new int[N];
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            doll[i] = Integer.parseInt(st.nextToken());
        }

        int left = 0, right = 0, count = 0, min = Integer.MAX_VALUE;

        while(right < N) {
            // 현재 위치에 라이언 인형이 있다면 라이언 개수 증가
            if(doll[right] == 1) count++;

            // 라이언 인형이 K개 이상이라면, 총 인형 개수의 최솟값 갱신
            // 왼쪽 포인터의 위치에 라이언 인형이 있다면 라이언 개수 감소
            // 왼쪽 포인터 오른쪽으로 이동
            while(count >= K) {
                min = Math.min(min, right - left + 1);
                if(doll[left] == 1) count--;
                left++;
            }
            // 오른쪽 포인터 증가
            right++;
        }

        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
}

 

 

느낀 점 및 정리 ✍️

1. 맨 처음 설계했던 코드는, 인형을 입력받을 때 Deque에 라이언 인형의 위치에 해당하는 인덱스들을 다 저장을 하고, removeFirst를 하여 left에 해당 인덱스를 넣어주며 진행하였다. 하지만 시간 초과나서 위와 같은 방식으로 변경했다.

2. 첫 설계도 투포인터로 시작하였으나.... 이것저것 추가되며 투 포인터의 장점을 살리지 못하게 된... ㅎㅎ ^^..;

3. 설계할 때 이런 저런 예외 사항이나 고려할 것들을 생각하다보면 점점 산으로 가는 것 같다. 생각보다 단순하게 접근해도 될 듯 ㅠ ㅠ

 

 

 

 

1972번: 놀라운 문자열

대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문

www.acmicpc.net

 

 

 

👇 내가 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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

        while(!(str = br.readLine()).equals("*")) {
            int result = 0;
            int num = 0;
            for(int i = 1; i < str.length(); i++) { // 놀라운 문자열일 경우 D-쌍의 개수
                num += i;
            }

            Set<String> set = new HashSet<>(); // 중복 제거를 위한 Set 선언

            if(str.length() <= 2) { // 1, 2글자일 경우 무조건 놀라운 문자열임
                System.out.println(str + " is surprising.");
            } else {
                for(int i = 1; i <= str.length() - 1; i++) {
                    for(int j = 0; j < str.length() - i; j++) {
                        String first = String.valueOf(str.charAt(j));
                        String second = String.valueOf(str.charAt(i + j));
                        set.add(first + second); // 조합한 두 문자를 set에 추가
                    }
                    result += set.size(); // set길이를 result 변수에 누적합
                    set.clear(); // set 초기화
                }
                if(result == num) System.out.println(str + " is surprising.");
                else System.out.println(str + " is NOT surprising.");
            }
        }
    }
}

 

 

느낀 점 및 정리 ✍️

1. set을 이용하여 중복 제거를 하였고, D-쌍마다 set의 크기를 result 변수에 더해주고 set을 초기화 시켜 놀라운 문자열일 경우의 문자열 개수와 일치하는지 판별해주었다. 

 

 

 

 

2210번: 숫자판 점프

111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

www.acmicpc.net

 

 

 

👇 내가 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
    static Set<String> set;
    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        map = new int[5][5];

        for(int i = 0; i < 5; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 5; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        set = new HashSet<>();
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 5; j++) {
                DFS(i, j, "", 0);
            }
        }
        System.out.println(set.size());
    }

    public static void DFS(int x, int y, String result, int count) {
        if(count == 6) {
            set.add(result);
            return;
        }

        for(int d = 0; d < 4; d++) {
            int nr = dr[d] + x;
            int nc = dc[d] + y;

            if(nr >= 0 && nc >= 0 && nr < 5 && nc < 5) {
                DFS(nr, nc, result + map[nr][nc], count + 1);
            }
        }
    }
}

 

 

 

느낀 점 및 정리 ✍️

1. Set을 이용하여 중복 제거

2. 동일한 곳을 재방문할 수 있기 때문에 visited 방문 배열을 별도로 사용하지 않았다.

3. 5글자가 만들어지면 return 되게끔 String과 count를 파라미터로 넘겨주었다.

 

 

+ Recent posts

loading