희연's 개발 일기장

https://www.hackerrank.com/challenges/big-sorting/problem?isFullScreen=true 

기존 풀이 방법

• String -> int 
• int -> String 하는 과정에서 시간초과로 실패 

    public static List<String> bigSorting(List<String> unsorted) {
        List<BigInteger> sorted = unsorted.stream()
                .map(BigInteger::new).sorted().collect(Collectors.toList());
        Collections.sort(sorted);
        List<String> answer = sorted.stream()
                .map(String::valueOf)
                .collect(Collectors.toList());
        return answer;
    }

새로운 풀이 방법

• compareTo를 통해서 자릿수를 비교해가면서 오름차순 정렬

    public static List<String> bigSorting(List<String> unsorted) {
        Collections.sort(unsorted, (x, y) -> {
            if(x.length() == y.length()){
                return x.compareTo(y);
            } else {
                return x.length() - y.length();
            }
        });
        return unsorted;
    }

문제 

- 임의의 N개의 숫자가 주어진다.

- 오름차순으로 정렬하고, M의 값이 주어진 상태에서 M이 몇 번째에 있는지 프로그램 작성

- 이분 탐색 사용

- lt와 rt를 생성 후, 왼쪽과 오른쪽의 위치가 바뀔 때까지 왼쪽와 오른쪽의 중간값을 M과 비교한다.

import java.util.Arrays;
import java.util.Scanner;
public class Solution {
    public static int solution(int n, int m, int[] arr){
        int answer = 0;
        Arrays.sort(arr);
        int lt = 0;
        int rt = n-1;

        while(lt<=rt){ // 왼쪽이 오른쪽으로 가면 해제
            int mid = (lt+rt)/2;
            if(arr[mid]==m){
                answer = mid+1;
                break;
            } else if(arr[mid]<m){ // 왼쪽
                lt = mid +1;
            } else if(arr[mid]>m){ // 오른쪽
                rt = mid -1;
            }
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 수 개수
        int m = sc.nextInt(); // 구하는 수
        int[] arr = new int[n];
        for(int i=0; i<n; i++){
            int num = sc.nextInt();
            arr[i] = num;
        }
        System.out.println(T.solution(n,m,arr));
    }
}

투포인터 문제 - 두 배열의 공통 원소 출력

- 공통 원소를 추출해서 오름차순 출력하기

- 배열들을 미리 오름차순 정렬한다.

- 같은 값일 경우 둘 중에 아무거나 값을 넣고 둘 다 포인터 index를 증가시킨다.

- 더 작은 배열의 포인터 index를 증가시킨다.

- 첫 번째 배열이 더 큰 경우에 두 번째 배열 포인터 index++

- 두 번째 배열이 더 큰 경우에 첫 번째 배열 포인터 index++

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static ArrayList<Integer> solution(int[] arr1, int[] arr2){
        ArrayList<Integer> answer = new ArrayList<>();

        Arrays.sort(arr1);
        Arrays.sort(arr2);

        int p1=0;
        int p2=0;
        int n = arr1.length;
        int m = arr2.length;

        while(p1<n && p2<m){
            if(arr1[p1]==arr2[p2]){ // 둘중에 값 아무거나 넣고, 둘다 idx증가
                answer.add(arr1[p1++]);
                p2++;
            } else if(arr1[p1]>arr2[p2]){ // 1번째 배열이 더 큰 경우 -> 작은 쪽을 증가 시키기
                p2++;
            } else {
                p1++;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr1 = {1,3,9,5,2};
        int[] arr2 = {3,2,5,7,8};
        System.out.println(T.solution(arr1,arr2));
    }
}

슬라이딩윈도우 문제 - 연속된 K일의 최대 매출 구하기문제

- 수열에서 연속된 K개를 합했을 때, 합의 최대 값 구하기

- 일단 첫 번째부터 K번째 까지 값들을 다 더해줘서 max 값으로 지정한다.

- 그 이후로 k번째부터 배열의 마지막까지 반복문을 실행한다.

- sum = sum + 현재값 - 첫번째값

- 현재의 총합과 이전의 총합 중에서 최대 값으로 저장해준다.

- 배열을 종료 했을 때 나오는 최대 값이 수열에서 연속된 K개의 값들 중 최대 값이된다. 

public class Solution {
    public static int solution(int[] arr, int k){
        int answer = 0;
        int sum = 0;

        // 일단 맨 첫번째부터 k번째 값들을 다 더해준다.
        for(int i=0; i<k; i++){
            sum += arr[i];
        }
        answer = sum;

        // k부터 배열의 마지막까지 계산해본다.
        for(int i=k; i<arr.length; i++){
            sum+=(arr[i]-arr[i-k]); // 현재 값을 더해주고 맨 앞의 값을 지워준다.
            answer = Math.max(answer, sum); // 이전의 총합과 현재의 총합을 비교해줘서 최대값을 저장
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {12,15,11,20,25,10,20,19,13,15};
        System.out.println(T.solution(arr, 3));
    }
}

복합적 문제 - 특정 숫자가 되는 경우의 수 구하기

- 투포인터는 O(N^2)에서 O(N)으로 개선 가능하다.

- N개의 수열에서 특정 숫자 M이 되는 경우의 수를 구해라

- N=8, M=6

- 수열 : 1 2 1 3 1 1 1 2

// sum이 M보다 크면 lt를 빼주고 lt++
// sum이 M보다 작으면 rt++

for(int rt=0; rt<N; rt++){ // 1. 증가
    sum+= arr[rt]; // 2. 더하기
    if(sum==M) answer++; // 3. 확인

    // sum이 M보다 커지면 삭제
    while(sum>=M){
        sum -= arr[lt++];
        if(sum==M){
            answer++;
        }
    }
}

복합적 문제 - 연속으로 1인 수열의 최대 길이 출력

public class Solution {
    public static int solution(int[] arr, int k){
        int N = arr.length; // 길이는 : rt - lt + 1
        int count = 0, lt=0;
        int answer = 0;

        for(int rt=0; rt<arr.length; rt++){
            if(arr[rt]==0) count++;
            while(count>k){
                if(arr[lt]==0) count--;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {1,1,0,0,1,1,0,1,1,0,1,1,0,1};
        System.out.println(T.solution(arr, 2));
    }
}

Hash + 슬라이딩 윈도우 - N일 중에서 K일 동안 벌어들일 수 있는 매출액의 종류를 각 구간별로 구하기

public class Solution {
    public static ArrayList<Integer> solution(int[] arr){
        int n = 7;
        int k = 4;
        ArrayList<Integer> answer = new ArrayList<>();
        HashMap<Integer, Integer> HM = new HashMap<>();

        for(int i=0; i<k-1; i++){
            HM.put(arr[i], HM.getOrDefault(arr[i],0)+1);
        }
        int lt = 0;
        for(int rt=k-1; rt<n; rt++){
            HM.put(arr[rt], HM.getOrDefault(arr[rt],0)+1);
            answer.add(HM.size());
            HM.put(arr[lt], HM.get(arr[lt])-1);
            if(HM.get(arr[lt])==0) {
                HM.remove(arr[lt]);
            }
            lt++;
        }
        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        int[] arr = {20,12,20,10,23,17,10};
        System.out.println(T.solution(arr));
    }
}

Hash + 슬라이딩 윈도우 - 모든 아나그램 찾기

import java.util.HashMap;

public class Solution {
    public static int solution(String s, String t){
        int answer = 0;
        HashMap<Character, Integer> am = new HashMap<>();
        HashMap<Character, Integer> bm = new HashMap<>();

        for(char x : t.toCharArray()) bm.put(x, bm.getOrDefault(x,0)+1);
        int L = t.length()-1;
        for(int i=0; i<L; i++) am.put(s.charAt(i), am.getOrDefault(s.charAt(i), 0)+1);
        int lt = 0;
        for(int rt=L; rt<s.length(); rt++){
            am.put(s.charAt(rt), am.getOrDefault(s.charAt(rt), 0)+1);
            if(am.equals(bm)) answer++;
            am.put(s.charAt(lt), am.get(s.charAt(lt))-1);
            if(am.get(s.charAt(lt))==0) am.remove(s.charAt(lt));
            lt++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        String s = "bacaAacbaa";
        String t = "abca";
        System.out.println(T.solution(s,t));
    }
}

문제

- 2차원 배열에서 자기 자신보다 상하좌우에서 높은 크기를 가지고 있는 값들이 있는 경우의 개수를 구하기

public class Main{
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    public static int solution(int[][] arr){
        int answer = 0;
        int n = arr.length;

        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr.length; j++){
                boolean flag = true;
                //int current = arr[i][j];
                for(int d=0; d<4; d++){
                    //int nx = arr[i][j]+dx[d];
                    //int ny = arr[i][j]+dy[d];

                    int nx = i+dx[d];
                    int ny = j+dy[d];

                    // 경계선 넘지 않게 체크 0~n-1
                    if(nx>=0 && nx<n && ny>=0 &&ny<n && arr[nx][ny]>=arr[i][j]) { // 현재위치보다 상하좌우가 큼
                       flag = false;
                       break;
                    }
                }
                if(flag){
                    answer++;
                }
            }
        }

        return answer;
    }

문제

- 방향 그래프에서 1번에서 N번 정점으로 가는 모든 경로의 가지 수 출력하기

- 이동할 수 있는 정점을 체크할 graph, 방문 했었던 위치를 체크하기 위한 배열 ch를 선언한다.

- 정점에서 이동할 수 있는 정점을 graph에 1을 저장해서 체크해준다.

- DFS를 1번부터 실행

- v(현재 정점)과 n(목적지 정점)이 같으면 경로의 수 + 1

- 아닐 경우, 1번~n번 정점으로 갈 수 있는지 체크(graph[x][y]=1 간선으로 이어져 있고 && ch[i] ==0 방문하지 않았던 곳)

- 방문할 수 있는 정점일 경우 방문 체크를 해주고 다음 정점으로 넘어가기 전에 스택 프레임에 D(v)를 넣고 DFS(다음 정점) 실행

- 앞의 과정을 반복해서 n번 정점에 도착하게 되면 다시 돌아와서 ch[i] = 0 방문 체크를 해제 해준다. 

public class Solution {
    static int n, m, answer = 0;
    static int[][] graph; // 정점 체크
    static int[] ch; // 방문 체크
    public void DFS(int v){
        if(v==n){
            answer++;
        } else {
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){ // v번 행에서 1~n까지 찾을 수 있는 정점 찾기
                    ch[i] = 1; // 방문 체크
                    DFS(i);
                    ch[i] = 0; // DFS 실행 후에 스택 프레임을 통해 다시 되돌아 올때 방문 풀어주기
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        n = 5; // 정점의 수
        m = 9; // 간선의 수
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}

DFS

- 자식이 2개가 아닌 경우에는 DFS에서 오류가 난다. 

- 연습용 코드

class Node {
    int data;
    Node rt;
    Node lt;

    public Node(int val) {
        data = val;
        rt = lt = null;
    }
}
public class Solution {
    Node root;
    public int DFS(int L, Node root){
        if(root.lt==null && root.rt==null){
            return L;
        } else {
            return Math.min(DFS(L+1,root.lt), DFS(L+1,root.rt));
            // 자식이 2개가 아니면 DFS 에서는 말단 노드가 아닌 것이 출력되는 오류가 난다.
        }
    }

BFS

class Node{
    int data;
    Node rt;
    Node lt;

    public Node(int val){
        data = val;
        rt = lt = null;
    }
}

public class Solution {
    Node root;
    public int BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root); // 큐에 루트 넣어준다.
        int L = 0; // 레벨은 0 부터
        while(!Q.isEmpty()){
            int len = Q.size(); // 레벨에 있는 원소 개수 = 큐의 사이즈
            for(int i=0; i<len; i++){
                Node current = Q.poll(); // 현재 (레벨) 큐에 있는 원소들
                if(current.lt==null && current.rt == null){
                    return L; // 말단노드의 경우 출력
                }
                // 자식 노드가 있는 경우 현재 노드의 자식 노드를 큐에 넣어준다.
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝남 = 레벨 증가
            L++;
        }
        return 0;
    }

문제

- 현수와 송아지의 위치가 주어질 때, 현수가 송아지의 위치로 갈 수 있는 최소의 점프 횟수를 구해라

- 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5 이동 가능하다.

레벨 0에서 루트 노드를 큐에 넣어주고, 방문 체크를 해준다.

while문에서 큐의 사이즈를 구해준다. // 큐의 사이즈 = 레벨에 있는 원소의 개수

큐의 사이즈 만큼 for문을 돌려준다. 

큐에서 원소들을 꺼내준다. // 레벨에 있는 원소들

원소들이 다음에 갈 수 있는 위치들을 계산해준다. 

다음 위치의 원소들이 범위에서 벗어나지 않고, 방문하지 않았던 곳만 큐에 넣어준다.

이때, 다음 레벨의 원소가 송아지의 위치일 경우 현재레벨+1을 return 해준다.

없을 경우, for문이 종료되고 해당 레벨의 순회는 종료되어 레벨을 +1 증가 시켜준다.

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int answer = 0;
    int[] dis = {1, -1, 5};
    int[] ch; // 체크 배열
    Queue<Integer> Q = new LinkedList<>();

    public int BFS(int s, int e){
        ch = new int[10001]; // 좌표는 1부터 10000까지
        ch[s] = 1; // 방문 체크
        Q.offer(s); // root 노드
        int L = 0; // 레벨 0에서 시작
        while(!Q.isEmpty()){
            int len = Q.size(); // 큐의 크기 = 레벨에 있는 원소
            for(int i=0; i<len; i++){
                int x = Q.poll(); // 레벨에 있는 노드 꺼내주기
                //if(x==e) return L; // 송아지 찾는 방법 1 : 레벨에 송아지의 위치가 존재하면 return
                for(int j=0; j<3; j++){ // 이동할 수 있는 3가지 경우의 수
                    int nx = x + dis[j]; // 현재노드 + 이동거리 = 이동한 노드의 위치
                    if(nx==e) return L+1; // 송아지 찾는 방법 2 : 다음 레벨에 송아지가 있다는 뜻
                    if(nx>=1 && nx<=10000 && ch[nx]==0){
                        // 범위에서 벗어나지 않고, 방문 체크 안한곳만
                        Q.offer(nx);
                    }
                }
            }
            // for문 종료되면 레벨 증가
            L++;
        }
        return 0;
    }

    public static void main(String[] args) {
        Solution T = new Solution();
        int s = 5;
        int e = 14;
        System.out.println(T.BFS(s, e));
    }
}

문제

- 이진트리 레벨 탐색하기

- 큐 사용

0레벨부터 N레벨까지 레벨 별로 탐색하기

- 일단 root노드를 0레벨에 만들고, 큐에 루트 노드를 넣는다.

- while문에서 큐에 원소가 없어질때까지 큐에 있는 원소 개수(레벨에 있는 원소 개수)만큼 출력해준다.

- queue에서 queue의 크기만큼 노드를 꺼내서 출력한다.

- 왼쪽과 오른쪽 자식이 있는 경우 현재 노드에서 왼쪽 자식과 오른쪽 자식 노드를 큐에 넣어준다.

if(current.lt!=null) if(current.rt!=null)

for이 종료되면 해당 레벨 탐색이 끝났다는 뜻으로, 레벨을 증가시킨다.

큐에 원소가 모두 제거되면 탐색을 종료한다.

class Node{
    int data;
    Node lt, rt;
    public Node(int val){
        data=val;
        lt=rt=null;
    }
}
public class Solution {
    Node root;
    public void BFS(Node root){
        Queue<Node> Q = new LinkedList<>();
        Q.offer(root);
        int L = 0; // root 노드 레벨은 0
        while(!Q.isEmpty()){
            int len = Q.size(); // Q의 원소의 개수
            System.out.print(L+" : "); // 해당 레벨의 원소들은 무엇이 있는지 출력
            for(int i=0; i<len; i++){ // 해당 레벨의 원소들이 모두 여기에서 나와야 함
                Node current = Q.poll(); // 노드 꺼내기
                System.out.print(current.data+" ");

                // 왼쪽, 오른쪽 자식을 queue에 넣어줘야 함
                if(current.lt!=null){
                    Q.offer(current.lt);
                }
                if(current.rt!=null){
                    Q.offer(current.rt);
                }
            }
            // for문이 끝나면 레벨 끝
            L++;
            System.out.println();
        }

    }
    public static void main(String[] args) {
        Solution tree = new Solution();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.BFS(tree.root);
    }
}