앞만 보는 사람

내림차순은 b가 먼저, 오름차순은 a가 먼저

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        String[] str = {"30", "20", "10" };

        // 내림차순
        Arrays.sort(str, new Comparator<String>(){
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });

        for (String x : str) {
            System.out.print(x + " ");
        }


        // 오름차순
        System.out.println();
        Arrays.sort(str, new Comparator<String>() {
            public int compare(String a, String b) {
                return (a + b).compareTo(b + a);
            }
        });

        for (String x : str) {
            System.out.print(x + " ");
        }
    }

}

import java.util.ArrayList;

public class Main {

    private void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    // 삽입 정렬
    private int[] sortByInsertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            while (j >= 0 && tmp < arr[j]) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;
        }
        return arr;
    }

    // 선택정렬
    private int[] sortBySelectionSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIdx = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            swap(arr, minIdx, i);
        }
        return arr;
    }

    // 버블정렬
    private int[] sortByBubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j + 1);
                }
            }
        }

        return arr;
    }

    // 셸 정렬
    private int[] sortByShellSort(int[] arr) {
        for (int h = arr.length / 2; h > 0; h /= 2) {
            for (int i = h; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - h;
                while (j >= 0 && tmp < arr[j]) {
                    arr[j+h] = arr[j];
                    j = j - h;
                }
                arr[j + h] = tmp;
            }
        }

        return arr;
    }

    public static void main(String[] args) {

        int[] array = {5, 4, 1, 2, 3, 6, 8, 7, 9, 10};

        Main T = new Main();

        // 삽입정렬 N, N^2, N^2
        System.out.print("삽입 정렬 : ");
        for (int x : T.sortByInsertionSort(array)) {
            System.out.print(x + " ");
        }

        // 선택정렬 N^2, N^2, N^2
        System.out.print("\n" + "선택 정렬 : ");
        for (int x : T.sortBySelectionSort(array)) {
            System.out.print(x + " ");
        }

        // 버블 정렬 N^2, N^2, N^2
        System.out.print("\n" + "버블 정렬 : ");
        for (int x : T.sortByBubbleSort(array)) {
            System.out.print(x + " ");
        }


        // 버블 정렬 N^2, N^2, N^2
        System.out.print("\n" + "버블 정렬 : ");
        for (int x : T.sortByBubbleSort(array)) {
            System.out.print(x + " ");
        }

        // 셸 정렬 N, N^1.5, N^2
        System.out.print("\n" + "셸 정렬 : ");
        for (int x : T.sortByShellSort(array)) {
            System.out.print(x + " ");
        }
    }




}

레퍼런스

https://velog.io/@pppp0722/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-7%EA%B0%9C-%EC%A0%95%EB%A6%AC-Java#%ED%80%B5-%EC%A0%95%EB%A0%ACquick-sort

https://www.acmicpc.net/problem/11724

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

public class Main {

    static int N, M, answer = 0;
    static boolean[] visited;
    static boolean[][] graph;

    public static void dfs(int idx) {
        visited[idx] = true;

        for (int i = 1; i <= N; i++) {
            if (graph[idx][i] && !visited[i]) {
                dfs(i);
            }
        }
    }
    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());

        graph = new boolean[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u][v] = true;
            graph[v][u] = true;

        }

        for (int j = 1; j <= N; j++) {
            if(!visited[j]) {
                dfs(j);
                answer++;
            }
        }

        System.out.print(answer);
    }
}

핵심

1. DFS를 언제 수행할지

2. graph, 재귀

https://www.acmicpc.net/problem/1260

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, V;
    static boolean[] visited;
    static boolean[][] graph;
    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> q = new LinkedList<>();

    public static void bfs(int start) {
        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {

            start = q.poll();
            sb.append(start).append(" ");

            for (int i = 1; i <= N; i++) {
                if (graph[start][i] && !visited[i]) {
                        q.add(i);
                        visited[i] = true;
                }

            }
        }
    }

    public static void dfs(int start) {
        visited[start] = true;
        sb.append(start).append(" ");

        for (int i = 1; i <= N; i++) {
            if(graph[start][i] && !visited[i]) {
                dfs(i);
            }
        }

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

        // 1. 입력 먼저

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

        visited = new boolean[N + 10];
        graph = new boolean[N + 10][N + 10];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());

            graph[y][x] = true;
            graph[x][y] = true;
        }

        dfs(V);
        System.out.println(sb.toString());
        sb = new StringBuilder();
        visited = new boolean[N + 10];
        bfs(V);
        System.out.println(sb.toString());
    }
}

핵심

1. DFS는 재귀 / BFS는 Queue

2. graph, visited, Queue(BFS)를 활용

https://leetcode.com/problems/group-anagrams/

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters

풀이방법

입력값(str)의 길이가 10^4이니까, 시간복잡도는 O(n), O(nlogn)정도로 생각했다. 즉, for문 하나에, if문 정도.??

알고리즘이 익숙하지 않은 나에게, 이정도가 최선의 접근이다.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for(String s : strs) {
            // 키를 정렬 후 String 형태로 다시 변환
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);

            // 만약 key가 없으면 map key 추가, 있으면 value에 add
            if(!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

return answer.stream()
		.mapToInt(Integer::intValue)
		.toArray();

흠... 아직 자료구조와 스트림에 대한 공부가 더 필요한 것 같다.

import java.util.*;

class Main{
	public static void main(String args[]) {
		
		Map<String, Integer> map = new HashMap<>();
		map.put("일이삼", 123);
		map.put("사오육", 456);
		map.put("칠팔구", 789);
		
		// for Each
		map.forEach((key, value) -> {
			System.out.println(key + " " + value);
		});
	}		
}

java 8 이상 부터는, map을 for Each문을 사용하여 순외할 수 있다고 한다... 신기신기!

이제 굳이 System.out.print 다 써가면서 할 필요가 없다! 

https://www.acmicpc.net/problem/10811

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

접근 방법

* 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.

* 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

* 바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

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

public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        // 1. N+1 크기의 배열을 만든다. index를 다루기 편하게 하기 위함
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N+1];

        // 2. 각 배열의 초기값을 index값과 일치하게 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();

            while (i < j) {
                int temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }

        for (int answer : arr) {
            if(answer != 0)
                System.out.print(answer + " ");
        }

    }
}

정리

while문을 사용하여 양 끝단에서 한 칸씩 줄어들며 버블정렬을 하면 쉽게 풀 수 있는 문제이다.

회고

처음에 for 문 안에 i와 j 두 값을 한번에 바꿀 수 없을까?하는 생각에 잠겨서 30분 정도 고민했던 것 같다. 길을 잘못들어섰으면 빨리 뒤돌아서 다른 방법을 찾는 것도 하나의 방법!

https://www.acmicpc.net/problem/5597

문제

X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, 그 중에서 제출 안 한 학생 2명의 출석번호를 구하는 프로그램을 작성하시오.

입력

입력은 총 28줄로 각 제출자(학생)의 출석번호 n(1 ≤ n ≤ 30)가 한 줄에 하나씩 주어진다. 출석번호에 중복은 없다.

출력

출력은 2줄이다. 1번째 줄엔 제출하지 않은 학생의 출석번호 중 가장 작은 것을 출력하고, 2번째 줄에선 그 다음 출석번호를 출력한다. (예제 입력은 밑에 더 있다. 보기가 길어질까봐 잘랐음)

접근 방법

- 1차원 배열로 쉽게 풀 수 있는 문제이다. 그런데, list를 사용해서 sort를 해서 풀 수 있겠다는 생각이 들었고, 두 방법으로 모두 풀어보았다.

1. 1차원 배열을 사용한 풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int[] arr = new int[31];

        for (int i = 0; i < 28; i++) {
            int input = sc.nextInt();
            arr[input] = 1;
        }

        for (int j = 1; j < arr.length; j++) {
            if (arr[j] != 1) {
                System.out.println(j);
            }
        }

        sc.close();
    }
}

1차원 배열을 생성하여, for문을 28번 돌리며 각 시행마다 input값을 받아서 그것에 해당하는 배열 인덱스의 값을 1로 지정한다. 그리고 다음 번 for문에서 배열의 원소가 1이 아닌 값을 출력한다.

장점 : 1차원 배열을 사용했기 때문에 순서가 정해져있다. 즉, sort를 할 필요 없이 오름차순으로 출력할 수 있다.

단점 : 수행 시간이 조금 걸린다(근데 이 문제에서는 크게 신경안써도 될 듯..!)

2. ArrayList를 사용한 풀이

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<Integer> alist = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        
        for (int j = 0; j < 28; j++) {
            int numlist = Integer.parseInt(br.readLine());
            alist.add(numlist);
        }

        for (int i = 1; i <= 30; i++) {
            if (!alist.contains(i)) {
                list.add(i);
            }
        }
        // 정렬을 꼭 해줘야 함. list에 저장된 값이 무엇인지 모르기 때문에
        Collections.sort(list);
        for (int j : list) {
            System.out.println(j);
        }
    }
}

여기서 중요한 부분은, list를 꼭 sort해줘야 하는 것이다. 왜냐하면, 출력 방식이 오름차순이기 때문이다.

정리

코드 자체는 1차원 배열을 사용하는 것이 편하지만, 자료구조를 배우면 효율적인 코드를 짤 수 있다. 수행 시간도 줄일 수 있을 분더러, 메모리를 효율적으로 사용할 수 있다. 물론, 무조건 Collection class를 이용한다고 해서 더 좋다는 것은 아니다.

https://www.acmicpc.net/problem/2720

문제

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

접근 방법

- 우선 Greedy 문제인 것을 직감적으로 알 수 있다.
입력받은 센트를 쿼터(Quarter,$0.25)로 나눴을 때 몫을 따로 저장하고, 나머지는 다시 피제수(나눠지는 수)가 된다.
그 피제수(나눠지는 수)를 다시 다임(Dime, $0.10)으로 나누고, 몫을 따로 저장하고 나머지는 다시 니켈(Nickel, $0.05)로 나눈다. 마지막으로 페니(Penny, $0.01)로 같은 작업을 반복하여  몫을 LinkedList에 저장하고 출력하면 된다.

정리

1. 쿼터, 다임, 니켈, 페니를 각각 25, 10, 5, 1 센트 단위로 생각하여 num배열을 하나 만든다. 그리고 몇 번 반복할지 T 값을 받는다.

2. 접근 방법에 해당하는 알고리즘을 구현한다.

3. Iterator를 사용하여 LinkedList의 원소를 출력한다.

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

class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        int[] num = {25, 10, 5, 1};
        int T = sc.nextInt();

//        // 1. LinkedList를 T 크기 만큼 만든다.
        LinkedList<Integer> arr = new LinkedList<>();

        for (int i = 0; i < T; i++) {
            arr.add(sc.nextInt());
        }

        // 2. for문으로 각 값의 몫과 나머지를 구한다
        for (int i = 0; i < arr.size(); i++) {
            LinkedList<Integer> li = new LinkedList<>();
            for (int j = 0; j < num.length; j++) {
                // 몫 추가
                li.add(arr.get(i) / num[j]);
                // 나머지 처리
                arr.add(i, arr.get(i) % num[j]);
                arr.remove(i + 1);
            }

            Iterator<Integer> it = li.iterator();
            while (it.hasNext()) {
                System.out.print(it.next() + " ");
            }
            System.out.println();
        }
    }
}

회고

- 해당 코드에서 핵심은 몫과 나머지를 어떻게 처리하냐의 문제이다. 반복 횟수가 많지는 않은데, ArrayList와 LinkedList 중 어떤 것을 써야 더 효율적일까를 고민해보았고, 물리적으로 비연속적인 LinkedList가 삽입/삭제에 더 유리하기 때문에 LinkedList를 채택했다. 사실 ArrayList를 써도 되지만, 각각의 특징을 공부하고 나니까 간단한 문제에도 이렇게 고민을 하게 되는 것 같다. 

그리고, List형태를 출력할 때 for each문 보다 Iterator를 쓰는게 효율적이라는 것을 알게 되었다. for each문은 Map클래스를 출력할 때 용이하다.