자몽 스토리

https://school.programmers.co.kr/learn/courses/30/lessons/138476

## 문제 풀이법

주어진 배열 중 많이 존재하는 수의 갯수를 세야 하므로,

각 숫자의 갯수를 세기위해 가장 먼저 HashMap을 떠올렸다.

HashMap을 갯수가 많은 수대로 정렬해야 하는데 HashMap은 정렬이 불가능하므로,

List로 변환 후, 반복문을 돌면서

주어진 K에서 가장 많이 존재하는 수의 갯수를 빼면서 0이 되거나 음수가 나올 때 해당 값을 리턴한다.

로직을 간단하게 요약하자면 아래와 같다.

1. HashMap으로 주어진 배열의 수들의 갯수를 세어 저장한다.
2. 정렬을 위해 List로 변환
3. List의 반복문을 돌면서
  3-1. value값을 꺼내 주어진 k에서 뺀다.
  3-2. answer(종류의 수)를 +1
  3-2. 뺄셈을 한 값이 양수면 계속 반복문 진행
  3-3. 0이거나 음수이면 break 후 그 값을 리턴

## 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        // HashMap으로 숫자의 개수를 저장한다
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num: tangerine){
            if(!map.containsKey(num)){
                map.put(num,1);
            }else{
                map.put(num, map.get(num) + 1);
            }
        }

        // Stream을 사용하여 value 기준 내림차순 정렬
        List<Map.Entry<Integer, Integer>> sortedEntries = map.entrySet()
            .stream()
            .sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed())
            .collect(Collectors.toList());

        // 값을 빼면서 k의 값이 음수가 될때 answer값을 리턴한다.
        for(Map.Entry<Integer, Integer> entry: sortedEntries){
            int num = entry.getValue();
            k -= num;
            answer++;
            if(k<=0){
                break;
            }
        }
        return answer;
    }
}

## 여담

1 ≤ tangerine의 원소 ≤ 10,000,000  와 같은 조건이 있어서 n2의 풀이로는 풀 수 없는 문제였다.

다른 사람들의 풀이와 비교했을 때 유사하게 푼 듯하다. 

https://school.programmers.co.kr/learn/courses/30/lessons/155651

## 문제 풀이법

내가 푼 문제 풀이법을 요약하자면

1. 시작시간을 기준으로 오름차순 정렬
2. 가장 빠른 시작 시간의 예약은 방 1개 줌
3. 다음 시작 시간부터 비교(청소시간 +10분) - 배열만큼 반복문 수행
  3-1. 가장 빨리 끝나는 방의 종료시간이 다음 예약의 시작 시간 이전이거나 같으면 종료시간을 다음 예약의 종료 시간으로 업데이트  
  3-2. 위의 경우가 아닐 경우 사용 가능한 방이 없으므로 방+1
  3-3. 종료시간을 저장한 리스트를 가장 빨리끝나는 종료시간 순으로 정렬
4. 최종 리스트의 사이즈가 방의 갯수

위의 풀이에서 주의 해야 할 것은 나는 문제의 입력값인 String[][]값을 시간 데이터로 변환하기 위해

Java의 LocalTime 형타입을 썼는데, 이 때 청소시간 10분을 더한 값을 list에 넣어버리면 

자정에 거의 가까운 시간들은 0시로 넘어가 버리기때문에 list에 저장하는 값들은 endTime 그대로 저장하고,

비교할 때 10분을 더해서 비교하게끔 하였다. 

ex) 12:58 -> 00:08 가 되고, 가장 이른 시간 순으로 배열을 정렬하기 때문에 실패하는 케이스 발생

## 코드

import java.util.ArrayList;
import java.time.LocalTime;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Collections;

class Solution {
	public int solution(String[][] book_time) {
		int answer = 1;
		ArrayList<LocalTime> rooms = new ArrayList<>();
		//시작시간에 따라 정렬
		Arrays.sort(book_time, new Comparator<String[]>() {
			@Override
			public int compare(String[] row1, String[] row2) {
				LocalTime time1 = LocalTime.parse(row1[0]);
				LocalTime time2 = LocalTime.parse(row2[0]);
				return time1.compareTo(time2);
			}
		});

		for(String[] row : book_time){
			LocalTime startTime = LocalTime.parse(row[0]);
			LocalTime endTime = LocalTime.parse(row[1]);
			//가장 빠른 시작 시간의 예약 - 방 사용
			if(rooms.isEmpty()){
				rooms.add(endTime);
				continue;
			}

			//ArrayList에 LocalTime + 10분 한 값 넣을 시 자정이 넘어가 버리므로 비교할때 10분을 더한다.
			LocalTime compareTime = rooms.get(0).plusMinutes(10);
			//방이 사용가능하면 방을 넘겨주고 끝나는 시간 업데이트
			if(compareTime.isBefore(startTime) || compareTime.equals(startTime)){
				rooms.remove(rooms.get(0));
				rooms.add(endTime);
			//방이 사용가능하지 않으면 새로운 방 리스트를 저장한뒤, 끝나는 시간을 기록한다.
			}else{
				rooms.add(endTime);
			}
			//저장한 값들을 끝나는 시간 우선으로 오게끔 정렬
			Collections.sort(rooms);

		}
		//루프가 끝난뒤 배열의 사이즈가 사용하는 방의 갯수
		answer = rooms.size();
		return answer;
	}
}

## 여담

풀이 후 다른 사람들의 풀이를 보니, 우선순위큐를 이용해서 많이들 풀었다.

우선순위큐로 방의 갯수를 관리하고, 퇴실 시간 기준으로 정렬을 유지한다.

내가 짠 로직 자체는 일반적으로 푼 풀이와 비슷한 것 같아 보인다.

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

그림을 그려 점화식을 찾아 풀이하였다.

이차원배열에 값을 저장하고, 해당 층의 값을 출력해주었다.

그림으로 그리면 아래와 같이 설명할 수 있다.

- 코드

import java.util.*;

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

        int[][] aparts = new int[15][15];
        int[][] info = new int[T][2];

        for(int i=0;i<aparts.length;i++){
            aparts[i][1]=1;
            aparts[0][i]=i;
        }

        for(int i=1;i<15;i++){
            for(int j=2;j<15;j++){
                aparts[i][j] = aparts[i-1][j]+aparts[i][j-1];
            }
        }

        for(int i=0;i<T;i++){
            int floor = sc.nextInt();
            int ho = sc.nextInt();
            info[i][0] = floor;
            info[i][1] = ho; 
        }

        for(int i=0;i<T;i++){
            System.out.println(aparts[info[i][0]][info[i][1]]);
        }
    }
}

백준 2252번: 줄 세우기 문제를 풀다가 위상 정렬 알고리즘에 대해 알게 되었다.

위상정렬 알고리즘의 개념에 대해서 포스팅을 해보았다.

1. 위상 정렬 알고리즘이란?

순서가 정해져 있는 작업을 차례대로 사용해야 할 때 사용하는 알고리즘.

- 사용조건

1) 단방향 그래프여야함.

2) 그래프끼리의 Cycle이 생기지 않아야함.

2. 알고리즘 간략 설명

1) 단방향그래프로 노드 저장

2) 노드를 저장할때 edgeCount값도 같이 저장해준다.(여기서 edgeCount는 노드를 가리키고 있는 간선의 수를 뜻한다.)

3) edgeCount값이 0인 것들을 먼저 큐에 넣고 노드를 방문하면서 edgeCount를 방문할때마다 -1을 해준다.

4) edgeCount값이 0이 되면 큐에 넣는다.

5) 큐에 값이 없을때까지 순회한다.

ex) 예시

[4,2],[4,2],[2,1]의 데이터가 들어올 경우 아래처럼 그래프가 그려진다.

3. 위상정렬을 이용한 대표적인 문제

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

위의 문제는 단방향 그래프에, 키를 비교한 값이기 때문에 서로 사이클이 생기지 않으므로

위상정렬의 알고리즘 조건에 부합한다.

아래는 나의 코드이다.

- 내 풀이

import java.util.*;

public class Main {
    static ArrayList<Integer> list = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] edgeCount;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();//노드 수
        int M = sc.nextInt();//줄 수
        Queue<Integer> queue =new LinkedList<>();

        int[][] arr= new int[M][2];
        for(int i=0;i<M;i++){
            arr[i][0]= sc.nextInt();
            arr[i][1]= sc.nextInt();
        }
        edgeCount =new int[N + 1];

        //행마다 arraylist 생성
        for(int i=0;i<N+1;i++)  graph.add(new ArrayList<>());

        for(int i=0;i<arr.length;i++){
            putGraph(arr[i][0],arr[i][1]);
        }

        for(int i=1;i<N+1;i++){
            if(edgeCount[i]==0){//count값이 0인값 먼저 큐에 넣어준다.
                queue.add(i);
            }
        }

        while (!queue.isEmpty()){
            int idx = queue.remove();
            System.out.print(idx+" ");
            ArrayList<Integer> node = graph.get(idx);
            for(int i=0;i<node.size();i++){
                int next = node.get(i);
                edgeCount[next]--;
                if(edgeCount[next]==0){
                    queue.add(next);
                }
            }
        }
    }

    public static void putGraph(int x,int y){
        //포함하고 있지 않다면
        if(!graph.get(x).contains(y)) {
            graph.get(x).add(y);//단방향 그래프에 추가
            edgeCount[y]++;//간선수 카운트 +1
        }
    }
}

1. 조합이란?

조합이란 n개의 숫자에서 r개의 수를 순서 없이 뽑는 경우의 수를 말한다.

예를 들어 1,2,3 에서 2개의 수를 순서없이 뽑는다면 

[1,2], [1,3], [2,3] 3가지의 경우가 나온다.

2. 조합 구현

백트래킹과 재귀로 구현할 수 있는데 백트래킹으로 구현해 보았다.

static void comb1(int[] arr, boolean[] visited, int start, int n, int r) {
	if(r == 0) {
		print(arr, visited, n);
		return;
	} else {
		for(int i = start; i < n; i++) {
			visited[i] = true;
			comb1(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}
}

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

9명의 난쟁이 중에서 키의 합이 100이 되는 진짜 일곱난쟁이를 찾는 문제이다.

나는 9명의 키의 다 더해서 총합을 구하고 arraylist의 값 중 2개의 값을 삭제하는 방식으로 문제를 풀었다. 

- 코드

import java.util.*;
import java.io.*;
import java.util.stream.IntStream;

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

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

        ArrayList<Integer> list = new ArrayList<>();
        int tot = IntStream.of(arr).sum();//난쟁이의 키의 합을 더한다.
        for(int a : arr){
            list.add(a);
        }

        int target= tot-100;//100을 빼서 타겟 넘버를 저장

        for(int i=0;i<arr.length;i++){
          int now = arr[i];
          int want= target-now;
          list.remove(Integer.valueOf(now));
          if(list.contains(want)) {//리스트에 찾는 값이 있는지 검사
              list.remove(Integer.valueOf(want));//있으면 삭제하고
              break;//반복문 탈출
          }
          list.add(now);
        }

        Collections.sort(list);//오름차순으로 정렬
        for(int a: list){
            System.out.println(a);
        }
    }
}

- 설명

1) IntStream.of(arr).sum() 

arr배열의 값을 모두 더함.

2) list.remove(Integer.valueOf(now))

list.remove(20); 이라고 쓸 경우, 20이 값인 게 아니라 리스트 인덱스 20인 값이 삭제되게 된다.

따라서 valueOf로 String값으로 바꿔주고 값으로 찾을 수 있도록 하였다.

1. 슬라이딩 윈도우 알고리즘

창문을 왼쪽부터 오른쪽으로 밀어오면서 창문안에 있는 값들을 부분배열로 조건에 맞는 경우를 찾는 알고리즘.

문자열에서 어떤 조건을 찾을때 완전탐색기법을 이용하면 이중포문을 사용하면 되는데 최악의 경우 O(n2)의 시간복잡도를 가지는데, 슬라이딩 윈도우 알고리즘을 사용할 경우 O(n)만큼 시간을 단축할 수 있다.

슬라이딩 윈도우는 고정된 일정한 사이즈로 앞부분과 뒷부분만 변경해주는 기법이다. 이는 구간이 일정하기 때문에 시작점을 알면 끝점을 알수 있어서 투포인터와 달리 굳이 2개가 필요하지 않다. 예를 들어 길이가 4라고 고정되었을 때 다음과 같이 구간을 탐색하게 된다.

• start = 0, 🟦🟦🟦🟦⬜️⬜️⬜️
• start = 1, ⬜️🟦🟦🟦🟦⬜️⬜️
• start = 2, ⬜️⬜️🟦🟦🟦🟦⬜️
• ...

예제 문제)

백준 1593번: 문자 해독

package com.company;

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

public class CharDecode {
    public static void main(String[] args) {
        int wlen,slen;
        String w, s;
        int[] wArr = new int[52];
        int[] sArr = new int[52];

        Scanner scan = new Scanner(System.in);
        System.out.print("문자열 길이?");
        wlen = Integer.parseInt(scan.next());
        slen = Integer.parseInt(scan.next());

        //버퍼 초기화
        scan.nextLine();
        System.out.print("W문자?");
        w = scan.nextLine();

        System.out.print("S문자?");
        s = scan.nextLine();

        //wArr 배열 셋팅
        for(char c: w.toCharArray()){
            putWord(c, wArr, 1);
        }

        int start=0;
        int cnt=0;
        int size=0;

        for(int i=0;i<s.length();i++){
            char sc = s.charAt(i);
            putWord(sc,sArr,1);
            size++;

            if(size==w.length()){
                if(Arrays.equals(wArr, sArr)){
                    cnt++;
                }
                putWord(s.charAt(start), sArr, -1);
                start++;
                size--;
            }
        }
        System.out.println(cnt);
    }

    static void putWord(char word, int[] arr, int dif){
        //'A'는 아스키코드값 65, 'a'는 97
        if('a'<= word && word<='z'){
            arr[word-'a']+=dif;
        }else{
            arr[word-'A'+26]+=dif;
        }
    }
}

O(n^2)의 시간복잡도를 갖는 알고리즘(버블정렬, 선택정렬, 삽입정렬) 들과

그보다 좀 더 빠르고 효율적인 O(n logn)의복잡도를 갖는 알고리즘(병합정렬, 퀵정렬, 트리정렬)이 있다.

1. Bubble Sort(버블 정렬)

바로 그 다음 노드와 비교해가면서 가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬한다.

버블 정렬은 정렬 방식이 마치 물 속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다.

- 장점

구현이 간단하다.

데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

- 단점

데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸린다.

- 소스코드

public class BubbleSort {
    public int[] sol(int[] arr){
        int k= arr.length;//배열의 길이

        for(int i=0;i<k-1;i++){
            for(int j=0;j<k-1-i;j++){
                int temp;
                if(arr[j]>arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        return arr;
    }
}

2. 선택 정렬

선택정렬은 앞쪽부터 정렬하는 방식이다.

주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다.

배열에서 최소값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환횟수가 적다는 것이 특징이다.

- 장점

구현이 간단하다

비교하는 횟수에 비해 교환하는 횟수가 적다.

-단점

데이터를 하나씩 비교하기때문에 시간이 오래 걸린다.

정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.

- 소스코드

public class SelectionSort {
    public int[] sol(int[] arr){

        int k= arr.length;//배열의 길이

        for(int i=0;i<k-1;i++){
            int temp, minIdx = i;
            for(int j=i+1;j<k;j++){
                if(arr[minIdx]>arr[j]){
                    minIdx = j;
                }
            }
            temp=arr[i];
            arr[i]=arr[minIdx];
            arr[minIdx]=temp;
        }
        return arr;
    }
}

3. 삽입 정렬

삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법이다.

두번째 인덱스부터 시작해서 자신의 앞에 있는 값들과 비교하여 적절한 위치를 찾아 넣어주는 형식으로 진행된다.

정렬을 위해 비교하는 범위 자체가 훨씩 적고, 이미정렬되어 있는 경우 앞에 노드보다 큰지 한번씩 밖에 비교를 하지 않아

시간 복잡도는 O(n)까지 줄어든다.

- 장점

입력으로 들어오는 배열의 원소가 정렬되어 있을수록 속도가 빠르다.

정렬된 값은 교환이 일어나지 않는다.

- 단점

삽입을 구현해야하므로 속도가 자료구조의 영향을 많이 받는다.

입력으로 들어오는 배열이 역순으로 정렬된 경우 성능이 굉장히 좋지 않다.

public class InsertSort {
    public int[] sol(int[] arr){
        int k=arr.length;
        for(int i=1;i<k;i++){
            int temp;
            for(int j=i;j>0;j--){
                if(arr[j-1]>arr[j]){
                    temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        return arr;
    }
}

*위의 세 정렬에 대한 성능표

반복문을 도는 횟수는 Bubble=Selection>=Insert

- 정리

버블정렬과 선택정렬은 단순하고 직관적이며, 구현이 쉽지만, 비효율적이므로 잘 사용하지 않는다.

삽입정렬은 정렬이 어느정도 되어있는 경우에 최소한의 비교와 연산이 이루어지므로, 성능이 좋아 사용된다.

- 프로그래머스 정렬 문제 [ H-Index ]

https://school.programmers.co.kr/learn/courses/30/lessons/42747