상근이는 소프트웨어 회사에서 일하는데, 회사의 특징 중 하나는 자유로운 출퇴근 시간입니다. 그래서 직원들은 언제든지 회사에 출근하고 퇴근할 수 있습니다. 상근이는 회사의 출입 로그를 분석하여 현재 회사에 있는 직원들을 찾고자 합니다.

입력

주어진 로그에는 각 직원의 이름과 출입 여부가 기록되어 있습니다. "enter"인 경우는 출근이고 "leave"인 경우는 퇴근입니다.

출력

주어진 로그를 기반으로 현재 회사에 있는 직원들을 사전 순으로 역순으로 출력합니다.

알고리즘 설계

1. 각 직원의 출입 여부를 추적하기 위해 맵을 사용합니다. 맵의 키는 직원의 이름이고 값은 현재 회사에 있는지 여부입니다.
2. 주어진 로그를 순회하면서 맵을 업데이트합니다.
3. 맵을 순회하여 현재 회사에 있는 직원들을 찾습니다.
4. 찾은 직원들을 사전 순으로 역순으로 정렬하여 출력합니다.

   예제 입력

4 Baha enter Askar enter Baha leave Artem enter

예제 출력

Copy code Askar Artem

소스 코드

import java.util.*;

public class CurrentEmployees {
    public static List<String> getCurrentEmployees(List<String> logs) {
        Map<String, Boolean> employees = new HashMap<>(); // 직원의 출입 여부를 저장하는 맵

        for (String log : logs) {
            String[] parts = log.split(" "); // 로그에서 이름과 출입 행동을 추출
            String name = parts[0];
            String action = parts[1];

            if (action.equals("enter")) {
                employees.put(name, true); // 출근한 경우 맵에 이름과 true로 설정
            } else if (action.equals("leave")) {
                employees.put(name, false); // 퇴근한 경우 맵에 이름과 false로 설정
            }
        }

        List<String> currentEmployees = new ArrayList<>();
        for (Map.Entry<String, Boolean> entry : employees.entrySet()) {
            if (entry.getValue()) { // 현재 회사에 있는 직원을 찾음
                currentEmployees.add(entry.getKey());
            }
        }

        Collections.sort(currentEmployees, Collections.reverseOrder()); // 사전 순으로 역순으로 정렬
        return currentEmployees;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 로그 수
        scanner.nextLine(); // 개행 문자 처리

        List<String> logs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            logs.add(scanner.nextLine()); // 출입 로그 추가
        }

        List<String> result = getCurrentEmployees(logs);

        for (String employee : result) {
            System.out.println(employee);
        }
    }
}

코드 분석

1. 로그 분석:

getCurrentEmployees 메서드에서는 각 직원의 출입 상태를 저장하기 위해 Map<String, Boolean> 타입의 맵을 선언합니다.

2. 로그 순회:

for 반복문을 통해 주어진 로그를 순회합니다. 각 로그는 공백을 기준으로 분리되어 직원의 이름과 출입 상태로 나뉘어집니다. 해당 정보를 맵에 저장합니다. 출근 상태인 경우에는 true, 퇴근 상태인 경우에는 false로 기록됩니다.

3. 직원 탐색:

맵을 순회하여 현재 회사에 있는 직원들을 찾습니다. 출근 상태인 직원들을 리스트에 추가합니다.

4. 정렬:

찾은 직원들을 사전 순으로 역순으로 정렬합니다. 이후, 결과 리스트를 반환합니다.

5. 메인 메서드:

입력을 받고, 주어진 로그를 리스트에 추가합니다. getCurrentEmployees 메서드를 호출하여 결과를 받고, 출력합니다.

나무 자르기 문제는 전기톱을 이용하여 나무를 자를 때 발생하는 충전 비용의 최솟값을 구하는 문제입니다. 이를 해결하기 위해서는 주어진 조건에 따라 전기톱을 사용하는 방법을 결정해야 합니다.

1. 문제 해결 방법

주어진 조건에 따라 전기톱을 사용하여 나무를 자르는 경우를 고려해야 합니다. 나무의 높이가 작은 순서대로 전기톱을 사용하는 것이 합리적입니다. 왜냐하면 높은 나무를 먼저 자를 경우에 비용이 더 많이 들기 때문입니다.

알고리즘 설계

1. 입력으로 주어진 나무의 높이와 충전 비용을 배열에 저장합니다.

2. 이전까지의 나무 중에서 가장 높은 나무의 높이를 기록하는 변수를 선언합니다. 처음에는 0으로 초기화합니다.

3. 각 나무를 순회하면서 다음을 수행합니다:

4. 현재 나무의 높이가 이전까지의 가장 높은 나무의 높이보다 높으면, 가장 높은 나무의 높이를 갱신합니다.

5. 현재 나무를 자를 때 발생하는 충전 비용은 현재 나무의 높이와 해당 나무를 자를 때의 충전 비용을 곱한 값입니다. 이 값을 전체 충전 비용에 더합니다.

6. 모든 나무를 순회한 후에는 총 충전 비용을 출력합니다.

   2. 코드 설계

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long[] treeHeights = new long[n];
        long[] chargingCosts = new long[n];

        // 나무 높이 입력
        for (int i = 0; i < n; i++) {
            treeHeights[i] = scanner.nextLong();
        }

        // 전기톱 충전 비용 입력
        for (int i = 0; i < n; i++) {
            chargingCosts[i] = scanner.nextLong();
        }

        // 충전 비용의 최솟값 계산
        long totalCost = calculateTotalChargingCost(n, treeHeights, chargingCosts);
        System.out.println(totalCost);
    }

    // 충전 비용의 최솟값 계산하는 함수
    private static long calculateTotalChargingCost(int n, long[] treeHeights, long[] chargingCosts) {
        long totalCost = 0;
        long maxTreeHeight = 0;

        for (int i = 0; i < n; i++) {
            if (treeHeights[i] > maxTreeHeight) {
                maxTreeHeight = treeHeights[i];
            }
            totalCost += maxTreeHeight * chargingCosts[i];
        }

        return totalCost;
    }
}

4. 코드 실행 예시

입력:

5 1 2 3 4 5 5 4 3 2 0

출력:

25

5. 마무리

위 코드를 통해 나무 자르기 문제를 해결할 수 있습니다. 주어진 조건에 따라 전기톱을 사용하는 순서를 고려하여 최소 충전 비용을 계산합니다. 수많은 실패를 거듭...

집합 S: 총 N개의 문자열로 이루어진 문자열 집합. 검사 문자열: 총 M개의 문자열로 이루어진 검사해야 하는 문자열 집합. 집합 S에 포함된 문자열 중 검사 문자열에 포함된 문자열이 몇 개나 있는지를 구해야 합니다.

알고리즘 설계

1. 집합 S에 포함된 문자열을 저장하기 위해 HashSet을 활용합니다.
2. 집합 S에 속하는 문자열을 입력받고 HashSet에 저장합니다.
3. 검사 문자열을 입력받으면서 HashSet에 해당 문자열이 포함되어 있는지 확인합니다.
4. 포함되어 있다면 카운트를 증가시킵니다.
5. 최종적으로 카운트된 값을 출력합니다.

   소스코드 구현하기

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 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 집합 S에 속하는 문자열을 저장할 Set 자료구조를 생성합니다.
        Set<String> stringSet = new HashSet<>();

        // 문자열의 개수 N과 검사해야 하는 문자열의 개수 M을 입력받습니다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 집합 S에 포함되어 있는 문자열을 입력받고, Set에 저장합니다.
        for (int i = 0; i < N; i++) {
            stringSet.add(br.readLine());
        }

        // 집합 S에 포함되어 있는 문자열 중에서 입력으로 주어진 문자열들이 몇 개나 포함되는지를 카운트합니다.
        int count = 0;
        for (int i = 0; i < M; i++) {
            String testString = br.readLine();
            if (stringSet.contains(testString)) {
                count++;
            }
        }

        // 결과를 출력합니다.
        System.out.println(count);
    }
}

테스트 케이스 예시

**입력:**
5 11
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
codeplus
codeminus
startlink
starlink
sundaycoding
codingsh
codinghs
sondaycoding
startrink
icerink

출력:

4

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 문자열의 개수를 N, 검사해야 하는 문자열의 개수를 M이라고 할 때 O(N + M)입니다.

주어진 숫자 카드 중에 특정 숫자가 적혀 있는지 확인하는 프로그램을 작성해야 합니다. 각 숫자 카드에는 하나의 정수가 적혀 있으며, 상근이는 N개의 숫자 카드를 가지고 있습니다. 이후 M개의 정수가 주어지고, 각 정수가 상근이가 가지고 있는 숫자 카드 중에 존재하는지 확인해야 합니다.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N이 주어집니다. (1 ≤ N ≤ 500,000) 둘째 줄에는 상근이가 가지고 있는 숫자 카드에 적혀 있는 정수 N개가 주어집니다. 각 정수는 공백으로 구분되어 있습니다. (-10,000,000 ≤ 정수 ≤ 10,000,000) 셋째 줄에는 확인해야 할 숫자의 개수 M이 주어집니다. (1 ≤ M ≤ 500,000) 넷째 줄에는 확인해야 할 M개의 정수가 주어지며, 각 정수는 공백으로 구분되어 있습니다. (-10,000,000 ≤ 정수 ≤ 10,000,000)

출력

입력으로 주어진 M개의 수에 대해, 각 숫자가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분하여 출력합니다.

예제 입력 1

5 6 3 2 10 -10 8 10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

소스 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 숫자 카드의 개수 입력
        Set<Integer> cards = new HashSet<>();

        // 상근이가 가지고 있는 숫자 카드를 집합에 저장
        for (int i = 0; i < N; i++) {
            cards.add(scanner.nextInt());
        }

        int M = scanner.nextInt(); // 확인해야 할 숫자의 개수 입력
        StringBuilder result = new StringBuilder();

        // 숫자 카드 확인
        for (int i = 0; i < M; i++) {
            int num = scanner.nextInt();
            result.append(cards.contains(num) ? "1 " : "0 ");
        }

        System.out.println(result.toString().trim());
    }
}

소스 코드 설명

먼저, 상근이가 가지고 있는 숫자 카드를 입력받아 HashSet에 저장합니다. 이를 통해 중복된 숫자는 제거됩니다. 확인해야 할 숫자의 개수와 각 숫자들을 입력받습니다. 각 숫자가 HashSet에 존재하는지 확인하여 있으면 1을, 없으면 0을 결과 문자열에 추가합니다. 마지막으로 결과 문자열을 출력합니다.

1. Arrays 클래스를 활용한 배열 정렬

Arrays 클래스는 배열에 관련된 다양한 유틸리티 메서드를 제공합니다. 배열의 정렬에는 sort() 메서드를 주로 사용합니다.

예제:

int[] arr = {3, 1, 4, 2};
Arrays.sort(arr); // 오름차순 정렬

2. Collections 클래스를 활용한 컬렉션 정렬

Collections 클래스는 컬렉션 프레임워크에 관련된 유틸리티 메서드를 제공합니다. 리스트의 정렬에는 sort() 메서드를 사용합니다.

예제:

List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(4);
list.add(2);
Collections.sort(list); // 오름차순 정렬

3. Comparable 인터페이스와 Comparator 인터페이스

Comparable 인터페이스: 객체의 자연 순서(기본 정렬 순서)를 정의할 때 사용됩니다. 클래스가 Comparable 인터페이스를 구현하면 compareTo() 메서드를 오버라이딩하여 정렬 순서를 지정할 수 있습니다.

Comparator 인터페이스: 객체의 비교자를 정의할 때 사용됩니다. 별도의 비교자 클래스를 구현하거나 익명 클래스를 활용하여 정렬 순서를 지정할 수 있습니다.

4. 주요 정렬 알고리즘

1. 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다.

2. 선택 정렬 (Selection Sort): 가장 작은 요소를 선택하여 정렬하는 알고리즘으로, 실행 시간이 길어 실제로는 잘 사용되지 않습니다.

3. 삽입 정렬 (Insertion Sort): 요소를 하나씩 적절한 위치에 삽입하여 정렬하는 알고리즘입니다.

4. 병합 정렬 (Merge Sort): 분할 정복 알고리즘을 사용하여 배열을 분할하고 정렬한 후 병합하여 정렬하는 알고리즘입니다.

5. 퀵 정렬 (Quick Sort): 분할 정복 알고리즘을 사용하여 배열을 분할하고 정렬하는 알고리즘으로, 평균적으로 가장 빠른 실행 시간을 가집니다.

5. 자바의 기본 정렬 알고리즘

자바의 기본 정렬 알고리즘은 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)을 혼합한 TimSort 알고리즘입니다. 이 알고리즘은 대부분의 경우에 매우 효율적이며, 이미 정렬된 배열에 대해서도 빠른 속도를 보장합니다.

정리

자바에서는 기본적으로 배열과 컬렉션을 정렬하기 위한 표준 라이브러리를 제공하며, 개발자가 필요에 따라 Comparable 인터페이스와 Comparator 인터페이스를 구현하여 정렬 순서를 지정할 수 있습니다. 또한, 자바의 기본 정렬 알고리즘은 TimSort 알고리즘이며, 대부분의 상황에서 효율적으로 동작합니다.

주어진 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있습니다. 이 좌표에 좌표 압축을 적용하려고 합니다. 좌표 압축을 적용한 결과 X'i의 값은 Xi보다 큰 다른 좌표의 개수와 같아야 합니다. 주어진 좌표를 압축한 결과를 출력해야 합니다.

알고리즘 설계

1. 먼저, 입력으로 주어진 좌표들을 배열에 저장합니다.
2. 중복을 제거하고 정렬한 새로운 리스트를 만듭니다.
3. 각 좌표의 압축된 값을 저장할 맵을 생성합니다.
4. 좌표를 순회하면서 압축된 값을 출력합니다.

   소스 코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 좌표의 개수 입력
        int[] X = new int[N]; // 좌표를 저장할 배열

        // 좌표들을 배열에 저장
        for (int i = 0; i < N; i++) {
            X[i] = scanner.nextInt();
        }

        // 중복을 제거하고 정렬한 새로운 리스트를 만듦
        Set<Integer> sortedXSet = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            sortedXSet.add(X[i]);
        }

        List<Integer> sortedXList = new ArrayList<>(sortedXSet);

        // 각 좌표의 압축된 값을 저장할 맵 생성
        Map<Integer, Integer> compressedXMap = new HashMap<>();
        for (int i = 0; i < sortedXList.size(); i++) {
            compressedXMap.put(sortedXList.get(i), i);
        }

        // 좌표를 순회하면서 압축된 값을 출력
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < N; i++) {
            result.append(compressedXMap.get(X[i])).append(" ");
        }

        System.out.println(result.toString());
    }
}

소스 코드 분석

이 코드는 주어진 수직선 상의 좌표들을 압축하는 기능을 수행합니다.

1. 입력 받기 및 좌표 저장:

   프로그램은 먼저 좌표의 개수(N)를 입력받습니다. 그 후에 N개의 좌표를 입력받아 배열에 저장합니다.

2. 좌표 압축:

   중복을 제거하고 정렬한 새로운 리스트를 만들기 위해 TreeSet을 사용합니다. 이 리스트에는 중복을 제거하고 정렬된 좌표가 저장됩니다. 그 다음 리스트를 순회하면서 각 좌표에 대해 압축된 값을 저장하기 위해 HashMap을 사용합니다. 이를 통해 각 좌표의 압축된 값을 맵에 저장합니다.

3. 압축된 좌표 출력:

   원래의 좌표 배열을 순회하면서 각 좌표의 압축된 값을 출력합니다. 이를 통해 좌표 압축된 결과를 출력합니다.

코드의 시간 복잡도는 좌표의 개수(N)에 비례합니다. TreeSet과 HashMap의 삽입 및 조회 작업은 대부분 O(logN) 또는 O(1)에 수행되므로 전체적으로 O(NlogN) 또는 O(N)의 시간 복잡도를 가집니다.

주어진 온라인 저지 회원의 수 N과 각 회원의 나이와 이름이 주어집니다. 이때, 회원들을 나이가 증가하는 순으로 정렬하되, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성해야 합니다.

알고리즘 설계

1. 주어진 회원 정보를 객체로 표현하기 위해 Member 클래스를 생성합니다. 이 클래스에는 나이(age)와 이름(name)을 저장할 수 있는 필드를 정의합니다.

2. 회원 정보를 담을 ArrayList를 생성하고, 입력을 받아서 각 회원을 Member 객체로 만들어 ArrayList에 저장합니다.

3. Comparator를 사용하여 회원을 정렬합니다. 먼저 나이를 기준으로 오름차순으로 정렬하되, 나이가 같은 경우에는 입력 순서대로 정렬합니다.

4. 정렬된 회원 정보를 출력합니다.

   소스 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Member {
    int age;
    String name;

    public Member(int age, String name) {
        this.age = age;
        this.name = name;
    }
}

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

        int N = Integer.parseInt(br.readLine());
        ArrayList<Member> members = new ArrayList<>();

        // 회원 정보 입력
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int age = Integer.parseInt(input[0]);
            String name = input[1];
            members.add(new Member(age, name));
        }

        // Comparator를 이용하여 회원을 정렬
        Collections.sort(members, new Comparator<Member>() {
            @Override
            public int compare(Member m1, Member m2) {
                if (m1.age == m2.age) {
                    return 0; // 나이가 같으면 순서 유지
                }
                return Integer.compare(m1.age, m2.age); // 나이 오름차순 정렬
            }
        });

        // 정렬된 회원 정보 출력
        for (Member member : members) {
            System.out.println(member.age + " " + member.name);
        }
    }
}

소스 분석

이 코드는 주어진 회원 정보를 나이가 증가하는 순으로 정렬하되, 나이가 같은 경우에는 입력 순서대로 정렬하는 기능을 수행합니다. 회원 정보를 객체로 표현하기 위해 Member 클래스를 정의하고, Comparator를 사용하여 회원을 정렬합니다. 최종적으로 정렬된 회원 정보를 출력합니다.

주어진 알파벳 소문자로 이루어진 N개의 단어를 다음의 조건에 따라 정렬하는 프로그램을 작성해야 합니다

1. 길이가 짧은 단어부터 정렬합니다.

2. 길이가 같은 경우에는 사전 순으로 정렬합니다.

3. 중복된 단어는 하나만 남기고 제거합니다.

   알고리즘 설계

4. 주어진 N개의 단어를 ArrayList에 저장합니다.

5. Comparator를 사용하여 단어들을 길이 순으로 정렬합니다.

6. 길이가 같은 경우에는 compareTo() 메서드를 이용하여 사전 순으로 정렬합니다.

7. 정렬된 단어들을 중복을 제거하면서 출력합니다.

   소스 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;

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

        int N = Integer.parseInt(br.readLine());
        ArrayList<String> words = new ArrayList<>();

        // 단어를 ArrayList에 저장
        for (int i = 0; i < N; i++) {
            words.add(br.readLine());
        }

        // Comparator를 이용하여 정렬
        Collections.sort(words, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                if (s1.length() == s2.length()) {
                    return s1.compareTo(s2);
                }
                return Integer.compare(s1.length(), s2.length());
            }
        });

        // 중복 제거를 위해 HashSet을 이용하여 정렬된 단어들을 저장
        HashSet<String> uniqueWords = new HashSet<>(words);

        // 정렬된 단어들을 출력
        for (String word : words) {
            if (uniqueWords.contains(word)) {
                System.out.println(word);
                uniqueWords.remove(word); // 중복 제거
            }
        }
    }
}

소스 분석

이 코드는 주어진 N개의 단어를 조건에 맞게 정렬하는 기능을 수행합니다. 먼저 입력된 단어들을 ArrayList에 저장하고, Comparator를 이용하여 정렬을 수행합니다. 길이가 같은 경우에는 compareTo() 메서드를 이용하여 사전 순으로 정렬합니다. 그 후, 중복을 제거하면서 정렬된 단어들을 출력합니다.

2차원 평면 위의 점 N개가 주어졌을 때, 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬하여 출력하는 문제입니다.

알고리즘 설계

1. 주어진 점들을 Point 객체로 표현합니다. 이 때, Point 클래스는 x좌표와 y좌표를 멤버 변수로 가집니다.
2. Comparator 인터페이스를 구현하여 y좌표를 기준으로 정렬합니다. y좌표가 같은 경우 x좌표로 오름차순으로 정렬합니다.
3. Arrays.sort() 메서드를 이용하여 정렬을 수행합니다. 정렬된 결과를 출력합니다.

   소스 코드 구현

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

class Point {
    int x, y;

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

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

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

        // 점들을 Point 객체로 생성하여 배열에 저장
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            points[i] = new Point(x, y);
        }

        // Comparator를 이용한 정렬
        Arrays.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.y == p2.y) {
                    return Integer.compare(p1.x, p2.x);
                }
                return Integer.compare(p1.y, p2.y);
            }
        });

        // 정렬된 점들을 출력
        for (Point point : points) {
            System.out.println(point.x + " " + point.y);
        }
    }
}

소스 분석

이 코드는 주어진 점들을 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬하는 기능을 수행합니다. 먼저 입력된 점들을 Point 객체로 생성하여 배열에 저장합니다. 그 후, Comparator를 이용하여 정렬을 수행합니다. Comparator는 y좌표를 기준으로 비교하며, y좌표가 같은 경우 x좌표를 비교하여 정렬합니다. 이렇게 정렬된 점들을 출력하여 문제의 조건에 맞는 결과를 얻습니다.

주어진 점들을 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬하는 문제입니다.

알고리즘 설계

1. 주어진 점들을 Point 객체로 표현합니다. 이 때, Point 클래스는 x좌표와 y좌표를 멤버 변수로 가집니다.
2. Comparator 인터페이스를 구현하여 x좌표를 기준으로 정렬합니다. x좌표가 같은 경우 y좌표로 오름차순으로 정렬합니다.
3. Arrays.sort() 메서드를 이용하여 정렬을 수행합니다. 정렬된 결과를 출력합니다.

   소스 코드 구현

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

class Point {
    int x, y;

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

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

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

        // 점들을 Point 객체로 생성하여 배열에 저장
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            points[i] = new Point(x, y);
        }

        // Comparator를 이용한 정렬
        Arrays.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point p1, Point p2) {
                if (p1.x == p2.x) {
                    return Integer.compare(p1.y, p2.y);
                }
                return Integer.compare(p1.x, p2.x);
            }
        });

        // 정렬된 점들을 출력
        for (Point point : points) {
            System.out.println(point.x + " " + point.y);
        }
    }
}

소스 분석

이 코드는 주어진 점들을 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬하는 기능을 수행합니다. 먼저 입력된 점들을 Point 객체로 생성하여 배열에 저장합니다. 그 후, Comparator를 이용하여 정렬을 수행합니다. Comparator는 x좌표를 기준으로 비교하며, x좌표가 같은 경우 y좌표를 비교하여 정렬합니다. 이렇게 정렬된 점들을 출력하여 문제의 조건에 맞는 결과를 얻습니다.

주어진 수의 각 자리수를 내림차순으로 정렬하는 문제입니다.

알고리즘 설계

1. 입력된 수를 문자열로 변환하여 각 자리수를 쉽게 접근할 수 있도록 합니다.
2. 문자열로 변환된 수를 내림차순으로 정렬합니다.
3. 정렬된 문자열을 다시 정수형으로 변환하여 출력합니다.

   소스 코드 구현

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

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

        String number = br.readLine();
        Integer[] digits = new Integer[number.length()];

        // 문자열을 정수형 배열로 변환
        for (int i = 0; i < number.length(); i++) {
            digits[i] = number.charAt(i) - '0';
        }

        // 내림차순으로 정렬
        Arrays.sort(digits, Collections.reverseOrder());

        // 정렬된 배열을 문자열로 변환
        StringBuilder result = new StringBuilder();
        for (int digit : digits) {
            result.append(digit);
        }

        System.out.println(result);
    }
}

소스 분석

이 코드는 주어진 수를 문자열로 변환하여 각 자리수를 내림차순으로 정렬하는 기능을 수행합니다. 우선 입력된 수를 문자열로 변환하고, 각 자리수를 정수 배열에 저장합니다. 그 다음 내림차순으로 정렬된 정수 배열을 다시 문자열로 변환하여 출력합니다. 이를 통해 입력된 수의 자리수를 내림차순으로 정렬하는 문제를 해결할 수 있습니다.

주어진 입력에서는 첫 번째 줄에는 수의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 주어집니다. 이 수를 오름차순으로 정렬하여 출력해야 합니다.

알고리즘 설계

1. 입력을 받아오기 위해 BufferedReader를 사용합니다.
2. 첫 번째 줄에서 수의 개수 N을 읽어옵니다.
3. N개의 수를 담을 배열을 생성합니다.
4. 반복문을 사용하여 N개의 수를 배열에 저장합니다.
5. Arrays.sort()를 사용하여 배열을 오름차순으로 정렬합니다.
6. 정렬된 배열을 순회하며 각 수를 출력합니다.

   소스 코드 구현

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 N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];

        // 수를 배열에 저장
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        // 배열을 오름차순으로 정렬
        Arrays.sort(numbers);

        // 정렬된 배열을 출력
        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            sb.append(num).append("\n");
        }
        System.out.print(sb);
    }
}

소스 분석

이 코드는 주어진 N개의 수를 배열에 저장한 후, 배열을 오름차순으로 정렬하여 출력하는 기능을 수행합니다. 이를 통해 입력된 수를 정렬된 상태로 출력함으로써, 문제에서 요구하는 수를 오름차순으로 정렬하는 것을 해결합니다. 이 코드의 시간 복잡도는 입력된 수의 개수에 따라 O(NlogN)입니다. 따라서 대량의 입력에도 빠르게 동작할 수 있는 효율적인 알고리즘이라고 할 수 있습니다.

주어진 입력에서는 첫 번째 줄에는 수의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 주어집니다. 이 수를 오름차순으로 정렬하여 출력해야 합니다.

알고리즘 설계

1. 입력을 받아오기 위해 BufferedReader를 사용합니다.
2. 첫 번째 줄에서 수의 개수 N을 읽어옵니다.
3. N개의 수를 담을 배열을 생성합니다.
4. 반복문을 사용하여 N개의 수를 배열에 저장합니다.
5. Arrays.sort()를 사용하여 배열을 오름차순으로 정렬합니다.
6. 정렬된 배열을 순회하며 각 수를 출력합니다.

   소스 코드 구현

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 N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];

        // 수를 배열에 저장
        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        // 배열을 오름차순으로 정렬
        Arrays.sort(numbers);

        // 정렬된 배열을 출력
        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            sb.append(num).append("\n");
        }
        System.out.print(sb);
    }
}

소스 분석

이 코드는 주어진 N개의 수를 배열에 저장한 후, 배열을 오름차순으로 정렬하여 출력하는 기능을 수행합니다. 이를 통해 입력된 수를 정렬된 상태로 출력함으로써, 문제에서 요구하는 수를 오름차순으로 정렬하는 것을 해결합니다. 이 코드의 시간 복잡도는 입력된 수의 개수에 따라 O(NlogN)입니다. 따라서 대량의 입력에도 빠르게 동작할 수 있는 효율적인 알고리즘이라고 할 수 있습니다.

주어진 시험 점수에서 상을 받는 사람 수에 따라 커트라인을 구하는 문제입니다.

알고리즘 설계

1. 입력을 받아오기 위해 Scanner를 사용합니다.
2. 응시자 수와 상을 받는 사람 수를 입력받습니다.
3. 각 학생의 점수를 배열에 저장합니다.
4. 배열을 오름차순으로 정렬합니다.
5. 상을 받는 사람 중 가장 낮은 점수를 출력합니다.

   소스 코드 분석

   배열을 정렬한 후, 상을 받는 사람 중 가장 낮은 점수를 선택합니다.

   소스 코드 구현

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); 
        int k = scanner.nextInt(); 

        int[] scores = new int[N];
        for (int i = 0; i < N; i++) {
            scores[i] = scanner.nextInt();
        }

        Arrays.sort(scores);
        int cutlineScore = scores[N - k]; 

        System.out.println(cutlineScore);

        scanner.close();
    }
}

결과 및 분석

이 코드를 실행하면 응시자들의 점수를 입력받은 후, 상을 받는 사람 중 가장 낮은 점수인 커트라인을 출력합니다.

Arrays.sort(scores); 코드는 scores 배열을 오름차순으로 정렬합니다. int cutlineScore = scores[N - k]; 코드는 상을 받는 사람 중 가장 낮은 점수를 선택하는데, 이때 N - k 인덱스의 점수가 커트라인이 됩니다.

문제 이해

주어진 다섯 개의 자연수를 이용하여 평균과 중앙값을 구하는 문제입니다.

알고리즘 설계

1. Scanner를 이용하여 다섯 개의 자연수를 입력받습니다.
2. 입력받은 자연수들의 합을 구합니다.
3. 평균은 합을 자연수의 개수로 나눈 값이므로, 합을 다섯으로 나눈 값을 구합니다.
4. 중앙값을 구하기 위해 입력받은 자연수들을 정렬한 후, 가운데에 위치한 값을 선택합니다.
5. 구한 평균과 중앙값을 출력합니다.

소스 코드 구현

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] numbers = new int[5];
        int sum = 0;

        // 입력 받기 및 합 구하기
        for (int i = 0; i < 5; i++) {
            numbers[i] = scanner.nextInt();
            sum += numbers[i];
        }

        // 평균 구하기
        int average = sum / 5;

        // 중앙값 구하기
        Arrays.sort(numbers);
        int median = numbers[2];

        // 결과 출력
        System.out.println(average);
        System.out.println(median);

        scanner.close();
    }
}

소스 코드 분석

주어진 다섯 개의 자연수를 배열에 저장하여 처리합니다. Arrays.sort()를 사용하여 배열을 정렬한 후, 중앙값을 선택합니다.

결론

입력받은 다섯 개의 자연수를 배열에 저장하고, 배열을 정렬하여 중앙값을 선택하는 방법을 이용했습니다. 이를 통해 평균과 중앙값을 효과적으로 구할 수 있습니다.

문제 이해

주어진 입력에서는 첫 번째 줄에는 수의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 주어집니다. 이 수를 오름차순으로 정렬하여 출력해야 합니다.

알고리즘 설계

1. 입력을 받아오기 위해 BufferedReader를 사용합니다.
2. 첫 번째 줄에서 수의 개수 N을 읽어옵니다.
3. N개의 수를 담을 배열을 생성합니다.
4. 반복문을 사용하여 N개의 수를 배열에 저장합니다.
5. Arrays.sort()를 사용하여 배열을 오름차순으로 정렬합니다.
6. 정렬된 배열을 순회하며 각 수를 출력합니다.

   소스 코드 구현

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 N = Integer.parseInt(br.readLine());
        int[] numbers = new int[N];

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

        Arrays.sort(numbers);

        for (int num : numbers) {
            System.out.println(num);
        }
    }```

결론

Arrays.sort() 메소드를 사용하여 시간 복잡도는 O(NlogN)입니다.

브루트 포스 알고리즘은 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 방법입니다. 이 방법은 단순하고 직관적이지만, 경우의 수가 많아질수록 시간이 많이 소요될 수 있습니다.

구현 방법

문제의 가능한 모든 경우의 수를 나열합니다. 각 경우에 대해 조건을 만족하는지 확인합니다. 조건을 만족하는 경우의 수를 찾아냅니다.

예시 문제

1. 설탕 배달

문제: 주어진 설탕 무게를 3킬로그램 봉지와 5킬로그램 봉지로 나누어야 합니다. 가장 적은 개수의 봉지를 사용해야 합니다.

구현: 모든 경우의 수를 탐색하여 조건을 만족하는 경우를 찾습니다.

2. 종말의 숫자

문제: 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 종말의 수라고 합니다. 주어진 순서에서 N번째 종말의 수를 찾아야 합니다. 구현: 가능한 모든 숫자를 탐색하여 종말의 수를 찾습니다.

3. 체스판 다시 칠하기

문제: 주어진 보드에서 8×8 크기의 체스판으로 잘라내어야 합니다. 이때, 체스판은 검은색과 흰색이 번갈아가며 칠해져야 합니다. 구현: 모든 가능한 경우의 수를 탐색하여 가장 적은 개수의 정사각형을 다시 칠해야 하는 경우를 찾습니다.

팁 및 TMI

브루트 포스 알고리즘은 단순하지만 경우의 수가 많아질수록 시간이 오래 걸릴 수 있습니다. 따라서 문제의 크기에 따라 실행 시간을 고려해야 합니다. 문제 해결을 위해 가능한 모든 경우의 수를 고려할 때, 시간 복잡도를 줄이기 위해 불필요한 계산을 피하는 것이 중요합니다.

경우의 수를 나열할 때, 경우의 수가 중복되지 않도록 주의해야 합니다. 중복된 경우를 처리하면서 시간을 절약할 수 있습니다.

브루트 포스 알고리즘은 간단하고 직관적이기 때문에 입문자에게 좋은 연습이 될 수 있습니다. 하지만 실제로 문제를 해결할 때에는 문제의 특성을 고려하여 효율적인 알고리즘을 선택하는 것이 좋습니다.

결론

브루트 포스 알고리즘은 가능한 모든 경우의 수를 탐색하여 문제를 해결하는 방법입니다. 경우의 수를 고려할 때 시간 복잡도를 고려하여 효율적인 알고리즘을 선택해야 합니다. 이 알고리즘을 통해 문제 해결 능력을 향상시키고 다양한 알고리즘에 대한 이해를 높일 수 있습니다.

666은 종말을 나타내는 수라고 합니다. 많은 블록버스터 영화에서는 666이 들어간 제목을 사용합니다. 영화감독 숌은 "세상의 종말"이라는 시리즈 영화의 감독입니다. 조지 루카스는 스타워즈를 만들 때, "스타워즈 1", "스타워즈 2", "스타워즈 3", "스타워즈 4", "스타워즈 5", "스타워즈 6"과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, "반지의 제왕 1", "반지의 제왕 2", "반지의 제왕 3"과 같이 영화 제목을 지었습니다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했습니다.

종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말합니다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, ... 입니다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것입니다. 일반화해서 생각하면, N번째 영화의 제목은 "세상의 종말"과 (N번째로 작은 종말의 수)와 같습니다.

숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하세요. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않습니다.

입력

첫째 줄에 N이 주어집니다. N은 10,000보다 작거나 같은 자연수입니다.

출력

첫째 줄에 N번째 영화의 제목에 들어간 수를 출력합니다.

예제 입력 및 출력

입력

2

출력

1666

코드 구현

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.close();

        int count = 0;
        int num = 666;

        while (true) {
            if (String.valueOf(num).contains("666")) {
                count++;
            }
            if (count == N) {
                System.out.println(num);
                break;
            }
            num++;
        }
    }
}

설명

주어진 자연수 N에 해당하는 숫자를 찾기 위해 반복문을 사용하여 숫자를 증가시키면서, 각 숫자가 "666"을 포함하는지 확인합니다. "666"을 포함하고 있다면 카운트를 증가시킵니다. 카운트가 N과 같아지면 해당 숫자를 출력하고 반복문을 종료합니다.

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았습니다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있습니다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 합니다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 합니다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 합니다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐입니다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우입니다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했습니다. 당연히 8*8 크기는 아무데서나 골라도 됩니다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하세요.

입력

첫째 줄에 N과 M이 주어집니다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수입니다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어집니다. B는 검은색이며, W는 흰색입니다.

출력

지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력합니다.

예제 입력 및 출력

입력

8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW

출력

1

코드 구현

코드를 입력하세요
```java
Copy code
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        scanner.nextLine(); 

        char[][] board = new char[N][M];
        for (int i = 0; i < N; i++) {
            String row = scanner.nextLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = row.charAt(j);
            }
        }
        scanner.close();

        int minChanges = countMinChanges(board);
        System.out.println(minChanges);
    }


    public static int countMinChanges(char[][] board) {
        int minChanges = Integer.MAX_VALUE;


        for (int i = 0; i <= board.length - 8; i++) {
            for (int j = 0; j <= board[0].length - 8; j++) {
                int changes1 = countChanges(board, i, j, 'W');  
                int changes2 = countChanges(board, i, j, 'B'); 
                minChanges = Math.min(minChanges, Math.min(changes1, changes2));
            }
        }

        return minChanges;
    }


    public static int countChanges(char[][] board, int startX, int startY, char startColor) {
        int changes = 0;
        char currentColor = startColor;

        for (int i = startX; i < startX + 8; i++) {
            for (int j = startY; j < startY + 8; j++) {
                if (board[i][j] != currentColor) {
                    changes++;
                }

                currentColor = (currentColor == 'W') ? 'B' : 'W';
            }

            currentColor = (currentColor == 'W') ? 'B' : 'W';
        }

        return changes;
    }
}```
코드를 입력하세요

설명

주어진 보드에서 가능한 모든 8x8 체스판의 경우를 탐색하면서, 맨 왼쪽 위 칸이 흰색인 경우와 검은색인 경우 각각에 대해 변경해야 하는 정사각형 개수를 계산합니다. 이때, 최소 변경 횟수를 구해야 하므로, 두 경우 중에서 더 작은 값을 선택하여 출력합니다.

4차 산업혁명 시대에 살고 있는 수현이는 버추얼 학교에서 수업을 듣고 있습니다. 수현이의 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 숙제로 다음과 같은 문제를 내주었습니다.

다음 연립방정식에서 x와 y의 값을 계산하시오.

ax + by = c
dx + ey = f

수현이는 바쁜 나날을 보내고 있어 이런 문제를 풀 시간이 없었습니다. 하지만 인터넷 창의 빈 칸에 수를 입력하는 것은 그렇게 어렵지 않으니 도와주면 좋겠다고 생각했습니다.

입력

정수 a, b, c, d, e, f가 공백으로 구분되어 차례대로 주어집니다. (-999 ≤ a, b, c, d, e, f ≤ 999)

출력

주어진 방정식을 만족하는 (x, y) 값 중 유일한 해인 경우에 대해 x와 y 값을 출력합니다.

예제 입력 및 출력

입력 1

1 3 -1 4 1 7

출력 1

2 -1

입력 2

2 5 8 3 -4 -11

출력 2

-1 2

코드 구현

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


        int x = (c * e - b * f) / (a * e - b * d);
        int y = (c * d - a * f) / (b * d - a * e);

        System.out.println(x + " " + y);
    }
}```

설명

주어진 연립방정식의 해를 계산하여 출력하는 프로그램입니다. 주어진 방정식에서 x와 y를 각각 구하는 공식을 사용하여 계산하고 결과를 출력합니다.

백준