Red Glitter Pointer

 

 

16173번: 점프왕 쩰리 (Small)

쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로,  (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다.

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;
    static int[] dr = {1, 0};
    static int[] dc = {0, 1};
    static int[][] game;
    static boolean[][] visited;

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

        game = new int[N][N];
        visited = new boolean[N][N];

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

        BFS(0, 0);

        System.out.println(visited[N - 1][N - 1] == true ? "HaruHaru" : "Hing");
    }

    public static void BFS(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        visited[x][y] = true;
        q.offer(new int[]{x, y});

        if(x == N - 1 && y == N - 1) {
            visited[N - 1][N - 1] = true;
            return;
        }

        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];
            int jump = game[curX][curY];

            for(int d = 0; d < 2; d++) {
                int nx = curX + dr[d] * jump;
                int ny = curY + dc[d] * jump;

                if(nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

느낀 점 및 정리 ✍️

1. BFS를 이용하여 풀었다

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 1972번 / Java] BOJ 1972 : 놀라운 문자열  (0) 2024.03.26
[백준 2210번 / Java] BOJ 2210 : 숫자판 점프(DFS)  (0) 2024.03.24
[백준 2309번 / Java] BOJ 2309 : 일곱 난쟁이  (0) 2024.03.16
[백준 3649번 / Java] BOJ 3649 : 로봇 프로젝트(투 포인터)  (2) 2024.03.12
[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)  (0) 2024.03.10

 

 

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

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[] dwarf = new int[9];
        int sum = 0;

        for(int i = 0; i < 9; i++) {
            dwarf[i] = Integer.parseInt(br.readLine());
            sum += dwarf[i];
        }
        int num = sum; // for문 돌리면서 sum값을 초기화 시키기 위해 num 변수 선언

        outer:
        for(int i = 0; i < 8; i++) {
            for(int j = i + 1; j < 9; j++) {
                sum -= (dwarf[i] + dwarf[j]); // 9명에서 2명을 빼서 7명 키의 합을 구한다
                if(sum == 100) { // 100이 된다면 i와 j 난쟁이를 없애기
                    dwarf[i] = 0;
                    dwarf[j] = 0;
                    break outer;
                }
                sum = num; // sum값 초기화
            }
        }
        Arrays.sort(dwarf); // 오름차순 정렬
        StringBuilder sb = new StringBuilder();
        for(int i = 2; i < 9; i++) { // 0번, 1번 인덱스는 0일테니(없앤 난쟁이 자리) 2번부터 출력
            sb.append(dwarf[i]).append("\n");
        }
        System.out.println(sb);
    }
}

 

 

 

👇 제출한 코드

느낀 점 및 정리 ✍️

1. 처음에는 7명을 구하려고 하다가 메모리 초과가 났다. 그래서 주어지는 9명과 뽑아야하는 7명의 숫자는 고정되어있으니 2명만 찾아서 빼는 방식으로 구현하였다. 

2. 2중 for문을 돌리면서 i번째, j번째에 있는 난쟁이들을 없애보며 키의 합이 100이 될 때를 찾아냈다

 

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 2210번 / Java] BOJ 2210 : 숫자판 점프(DFS)  (0) 2024.03.24
[백준 16173번 / Java] BOJ 16173 : 점프왕 쩰리 (Small)  (0) 2024.03.24
[백준 3649번 / Java] BOJ 3649 : 로봇 프로젝트(투 포인터)  (2) 2024.03.12
[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)  (0) 2024.03.10
[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)  (0) 2024.03.09

 

 

 

3649번: 로봇 프로젝트

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에

www.acmicpc.net

 

 

 

👇 작성한 코드

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

public class Main {
    public String solution(int x, int n, int[] arr) {
        String answer = "danger";
        Arrays.sort(arr); // 투포인터 알고리즘을 사용하기 위해 정렬
        int lt = 0; // 왼쪽 포인터
        int rt = n - 1; // 오른쪽 포인터

        while(lt < rt) { // 왼쪽 포인터가 오른쪽 포인터보다 작을 때만 작동
            int sum = arr[lt] + arr[rt];

            // 더한 값이 찾으려는 x의 값과 일치하다면 yes 리턴,
            // 더한 값이 x보다 크다면 오른쪽 포인터(더 큰 수) 감소, x보다 작다면 왼쪽 포인터 증가(수 증가시키기)
            if(sum == x) return "yes " + arr[lt] + " " + arr[rt];
            else if(sum > x) rt--;
            else lt++;
        }

        return answer;
    }

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

        while ((str = br.readLine()) != null) { // 테스트 케이스의 수를 따로 주지 않음
            int x = Integer.parseInt(str);
            int n = Integer.parseInt(br.readLine());

            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(br.readLine());

            Main T = new Main();
            System.out.println(T.solution(x * 10000000, n, arr)); // 나노미터
        }
    }
}

 

 

느낀 점 및 정리 ✍️

1. 최근 풀었던 문제 중에 제일 !!!! 허탈했다 ㅜ 문제 읽자마자 [두 개의 숫자 + 정답이 여러 개일 경우 차이가 더 큰 값] 조건을 보고 투포인터 쓰면 바로 풀리겠다 싶어서 빠르게 로직 구현했는데, 25%에서 틀렸다는 문구가 계속 나와서 테스트 케이스 여러 개 만들어서 해보는데도 틀린 부분이 보이지 않았다 ㅠ 그러다가 발견한 "입력은 여러개의 테스트 케이스로 이루어져 있다" ...............ㅋㅎㅋㅎ ㅋ후쿠 ㅜㅜㅠㅠ 나는 왜 당연하게 1개의 테스트 케이스만 입력될 수 있게 구현했는가,,,,, ㅠ 풀이 시간은 5분? 밖에 안걸렸는데 이것 때문에 디버깅 시간이 ☠️☠️☠️☠️

2. 진~~~~~~~~~~~~~~짜 입출력 조건 + 문제 조건 🌟 무조건. 재확인 🌟 하고 따로 적어둔 다음에 설계 시작해야겠다 ㅜㅠ 

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 16173번 / Java] BOJ 16173 : 점프왕 쩰리 (Small)  (0) 2024.03.24
[백준 2309번 / Java] BOJ 2309 : 일곱 난쟁이  (0) 2024.03.16
[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)  (0) 2024.03.10
[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)  (0) 2024.03.09
[백준 15831번 / Java] BOJ 15831 : 준표의 조약돌(투 포인터)  (0) 2024.03.08

 

 

2343번: 기타 레슨

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경

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 int count(int[] arr, int possible) {
        int cnt = 1, sum = 0;
        // 배열을 돌면서 mid값을 초과하지 않을 정도로 sum에 숫자를 더해준다.
        for(int x : arr) {
            if(sum + x > possible) { // mid 값을 초과한다면, 블루레이 개수 추가
                cnt++;
                sum = x; // 블루레이에 저장할 크기 초기화
            } else sum += x; // mid 값을 초과하지 않는다면 블루레이에 저장
        }
        return cnt;
    }

    public int solution(int M, int[] arr) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt(); // arr 배열에서 최댓값 구하기
        int rt = Arrays.stream(arr).sum(); // arr 배열에 있는 모든 값 더하기

        // 이분 탐색 진행
        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(count(arr, mid) <= M) { // 블루레이 개수가 M개 이하라면 (정답 가능성 O)
                answer = mid; // 해당 값 저장
                rt = mid - 1; // 오른쪽 포인터를 mid 앞으로 옮기기
            } else lt = mid + 1; // M개를 초과한다면 왼쪽 포인터를 옮기기
        }
        return answer;
    }

    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[] arr = new int[N];

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

        Main T = new Main();
        System.out.println(T.solution(M, arr));
    }

}

 

 

느낀 점 및 정리 ✍️

1. 이분 탐색... 쉽지 않다 ... 고려할 내용들이 많아서 푸는 내내 헷갈렸다 ㅜ 설계를 조금 더 꼼꼼하게 하고 들어가야겠다

 

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 2309번 / Java] BOJ 2309 : 일곱 난쟁이  (0) 2024.03.16
[백준 3649번 / Java] BOJ 3649 : 로봇 프로젝트(투 포인터)  (2) 2024.03.12
[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)  (0) 2024.03.09
[백준 15831번 / Java] BOJ 15831 : 준표의 조약돌(투 포인터)  (0) 2024.03.08
[백준 15961번 / Java] BOJ 15961 : 회전 초밥(슬라이딩 윈도우, 원형 배열)  (0) 2024.03.07

 

 

 

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

www.acmicpc.net

 

 

 

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

public class Main {
    public int solution(int N, int K, int[] S) {
        int answer = 0, lt = 0, cnt = 0;
        // 오른쪽 포인터가 배열의 끝까지 갈때까지만 진행
        for(int rt = 0; rt < N; rt++) {
            if(S[rt] % 2 != 0) cnt++; // 홀수라면 삭제 횟수 증가
			// 삭제 가능한 횟수를 초과하면 왼쪽 포인터를 오른쪽으로 옮기기
            while(cnt > K) {
                if(S[lt] % 2 != 0) cnt--;
                lt++;
            }
            // rt와 lt의 간격을 계산하고, 삭제한 홀수의 개수만큼 빼주기
            answer = Math.max(answer, rt - lt + 1 - cnt);
        }
        return answer;
    }

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Main T = new Main();
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] S = new int[N];

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

        System.out.println(T.solution(N, K, S));
    }

}

 

 

느낀 점 및 정리 ✍️

1. 코테 대비로 요즘 알고리즘 문제 풀 때 solution 메소드를 따로 생성하여 풀고 있다

2. 투 포인터 알고리즘을 활용하여 풀었다

 

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 3649번 / Java] BOJ 3649 : 로봇 프로젝트(투 포인터)  (2) 2024.03.12
[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)  (0) 2024.03.10
[백준 15831번 / Java] BOJ 15831 : 준표의 조약돌(투 포인터)  (0) 2024.03.08
[백준 15961번 / Java] BOJ 15961 : 회전 초밥(슬라이딩 윈도우, 원형 배열)  (0) 2024.03.07
[백준 1735번 / Java] BOJ 1735 : 분수 합 (유클리드 호제법)  (0) 2024.03.02

 

 

15831번: 준표의 조약돌

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조

www.acmicpc.net

 

 

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

public class Main {
    public int solution(int N, int B, int W, char[] arr) {
        int lt = 0, rt = 0; // 왼쪽 포인터, 오른쪽 포인터
        int max = 0;
        int[] stone = new int[2]; // stone[0] = W의 개수, stone[1] = B의 개수

        while(rt < N) {
            // 현재 rt 위치의 돌 추가
            if(arr[rt] == 'B') stone[1]++;
            else stone[0]++;

            // B의 개수가 문제에서 입력받은 B개를 넘어서면
            // 가장 왼쪽에 있던 돌을 빼면서 왼쪽 포인터를 증가
            if(B < stone[1]) {
                if(arr[lt] == 'B') stone[1]--;
                else stone[0]--;
                lt++;
            }
            // W돌의 개수가 입력받은 W개 이상이 되면 최댓값 갱신 
            if(stone[0] >= W) max = Math.max(max, rt - lt + 1);
            rt++; // 오른쪽 포인터 이동
        }
        return max;
    }

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

        int N = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        char[] arr = br.readLine().toCharArray();

        System.out.println(T.solution(N, B, W, arr));
    }
}

 

 

느낀 점 및 정리 ✍️

1. 코딩테스트 대비하고자 프로그래머스 제출 형식에 맞춰 solution 메소드를 생성하여 코드를 작성했다.

2. 첫 제출에서는 14%에서 틀렸습니다가 떴었고 두 번째 제출에서 맞았다. 왜 처음부터 완벽하게 못맞추는거니............!!!!!!!!!!!!!!!!!!! 주어진 테스트 케이스 2개만 통과하면 그냥 제출해보는 안좋은.. 습관이 .. ^^ ㅎ 코테때 시간도 촉박할텐데 걱정이당 😓

3. 오른쪽 포인터를 증가시키면서 해당 자리에 있는 돌의 개수를 세어주었다. 그러다가 입력받은 B 숫자보다 검정돌이 많아질 경우, 가장 왼쪽에 있는 돌을 하나 빼고 왼쪽 포인터의 위치를 우측으로 옮겨준다. 가지고 있는 흰색 돌의 개수가 입력받은 W 숫자 이상일 경우, 최댓값을 갱신해주는 방식으로 풀었다.

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 2343번 / Java] BOJ 2343 : 기타 레슨(이분 탐색)  (0) 2024.03.10
[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)  (0) 2024.03.09
[백준 15961번 / Java] BOJ 15961 : 회전 초밥(슬라이딩 윈도우, 원형 배열)  (0) 2024.03.07
[백준 1735번 / Java] BOJ 1735 : 분수 합 (유클리드 호제법)  (0) 2024.03.02
[백준 5218번 / Java] BOJ 5218 : 알파벳 거리  (0) 2024.03.01

 

설계 시간: 10분

풀이 시간: 32분

디버깅 시간: 20분

 

 

15961번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2

www.acmicpc.net

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
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 d = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

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

        Map<Integer, Integer> map = new HashMap<>();
        map.put(c, 1);
        for(int i = 0; i < k; i++) {
            map.put(sushi[i], map.getOrDefault(sushi[i], 0) + 1);
        }
        int max = map.size();
        for(int i = k; i < N + k; i++) {
            map.put(sushi[i % N], map.getOrDefault(sushi[i % N], 0) + 1);
            map.put(sushi[(i - k) % N], map.getOrDefault(sushi[(i - k) % N], 0) - 1);
            if(map.get(sushi[i - k]) == 0) {
                map.remove(sushi[i - k]);
            }
            max = Math.max(max, map.size());
        }
        System.out.println(max);
    }
}

 

느낀 점 및 정리 ✍️

1. 처음 설계했을 땐 "회전"(배열의 시작과 끝이 이어져있음)의 특성을 고려하지 않아서 제출 후 10퍼센트 정도에서 틀렸다는 문구가 출력됐었다. 슬라이딩 윈도우 알고리즘을 사용해서 Sysout으로 한 문장씩 아무리 찍어봐도 왜 틀린건지 알 수가 없었는데, 생각해보니 N번만 돌릴게 아니라 N + k - 1까지 돌려서 확인해야했다. 

2. 배열의 인덱스를 계산할 때, 크기를 넘어가지 않도록 i % N 을 사용하여 배열의 시작으로 다시 돌아오도록 작성했다.

3. 설계할 때부터 회전을 고려하지 못했어서 ㅠ ,, 이건 많은 문제들을 접하다보면 자연스럽게 고려하게 되겠지.. 싶다...! 파이팅

 

 

 

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 22862번 / Java] BOJ 22862 : 가장 긴 짝수 연속한 부분 수열 (large) (투포인터)  (0) 2024.03.09
[백준 15831번 / Java] BOJ 15831 : 준표의 조약돌(투 포인터)  (0) 2024.03.08
[백준 1735번 / Java] BOJ 1735 : 분수 합 (유클리드 호제법)  (0) 2024.03.02
[백준 5218번 / Java] BOJ 5218 : 알파벳 거리  (0) 2024.03.01
[백준 5637번 / Java] BOJ 5637 : 가장 긴 단어  (0) 2024.02.28

 

 

1735번: 분수 합

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

www.acmicpc.net

 

 

 

작성한 코드 👇

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        int deno = b * d;
        int num = (a * d) + (b * c);

        int answer = gdc(Math.max(deno, num), Math.min(deno, num));
        System.out.println(num / answer + " " + deno / answer);
    }

    static int gdc(int a, int b) {
        if(b == 0) return a;
        return gdc(b, a % b);
    }
}

 

 

느낀 점 및 정리 ✍️

1. 유클리드 호제법 알고리즘으로 풀었다. 최대공약수 최소공배수 구해야 할 때 아주 편하다

 

 

 

 

💡 유클리드 호제법이란? 아래 링크 참고 ! 

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란

ko.wikipedia.org

 

'Algorithm & SQL > BOJ' 카테고리의 다른 글

[백준 15831번 / Java] BOJ 15831 : 준표의 조약돌(투 포인터)  (0) 2024.03.08
[백준 15961번 / Java] BOJ 15961 : 회전 초밥(슬라이딩 윈도우, 원형 배열)  (0) 2024.03.07
[백준 5218번 / Java] BOJ 5218 : 알파벳 거리  (0) 2024.03.01
[백준 5637번 / Java] BOJ 5637 : 가장 긴 단어  (0) 2024.02.28
[백준 17413번 / Java] BOJ 17413 : 단어 뒤집기 2  (0) 2024.02.28

+ Recent posts

loading

티스토리툴바