[Submit] 6주차 과제

[Hwang-sebin]

Issue : ✅ Submit

6주차 과제
문제 풀이 - 더 나은 풀이 서칭 - 정리

✅ 완료한 사항

1. 백준 8단계
2. 책 4장 마무리 , DFS
3. BFS

✅ 문제 풀이 중 막혔던 문제

1. 백준 8-6번 (1193번) 실버5 분수 찾기 문제.

해당 문제를 직접 알고리즘을 구현해보고 싶어 도전하였으나 실패.
구글링을 통해 해당 문제 알고리즘을 쉽게 정리해 놓은 티스토리를 참고하여 풀었습니다.
https://st-lab.tistory.com/74

이용할 변수 :

1. 입력받을 X 값
2. 해당 범위의 대각선 칸 개수 ( cross_count )
3. 해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )

package study06;
import java.util.Scanner;

public class BOJ1193 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int X = in.nextInt();

        int cross_count = 1, prev_count_sum = 0;

        while (true) {

            // 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
            if (X <= prev_count_sum + cross_count) {

                if (cross_count % 2 == 1) {	// 대각선의 개수가 홀수라면
                    // 분자가 큰 수부터 시작
                    // 분자는 대각선상 내의 블럭 개수 - (X 번째 - 직전 대각선까지의 블럭 개수 - 1)
                    // 분모는 X 번째 - 직전 대각선까지의 블럭 개수
                    System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
                    break;
                }

                else {	// 대각선상의 블럭의 개수가 짝수라면
                    // 홀수일 때의 출력을 반대로
                    System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
                    break;
                }

            } else {
                prev_count_sum += cross_count;
                cross_count++;
            }
        }
    }
}

2. 책 22번 (10989번)

정렬 기법 사용하지 않고 Arrays.sort() 사용.
StringBuilder 를 이용하여 출력

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

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

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

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

        Arrays.sort(arr);

        for(int i = 0; i < N; i++){
            sb.append(arr[i]).append('\n');
        }

        System.out.println(sb);
    }
}

3. 책 23번 (11724번)

책에 나와 있는 슈도코드와 구현된 코드를 보고 풀이 하였음.

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

public class Main {
    static boolean visited[];
    static ArrayList<Integer>[] A;

    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());
        visited = new boolean[n + 1];
        A = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            A[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 시작점
            int e = Integer.parseInt(st.nextToken()); // 종료점
            A[s].add(e);
            A[e].add(s);
        }

        int count = 0;

        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                count++;
                DFS(i);
            }
        }

        System.out.println(count);
    }

    private static void DFS(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (int i : A[v]) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }
}

📎 ETC

🍖 후기

정처기 ㅎㅇㅌ