자몽 스토리

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]]);
        }
    }
}

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값으로 바꿔주고 값으로 찾을 수 있도록 하였다.

값이 떨어지지 않은 주식들을 모아 계산해야하기 때문에

Stack구조가 사용하기 적절하다고 생각하여 Stack구조를 이용해 문제를 풀어보았다.

1. 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0;i<prices.length;i++){
            while(!stack.isEmpty()){
                int peek = stack.peek();
                
                //스택에 있는 값이 더 클경우 값이 떨어진 것이므로
                if(prices[peek]>prices[i]){
                    stack.pop();//스택에서 빼주고
                    answer[peek]=i-peek;//answer에 idx차이만큼 값을 저장해준다.
                }else{
                    break;//값이 안떨어진 경우 다음 i 검사하도록 break
                }
                
            }
            stack.push(i);
        }
        
        //끝까지 가격이 안떨어진 주식들은 stack안에 계속 존재하므로 answer에 값 계산해서 넣어준다.
        while(!stack.isEmpty()){
            int pop = stack.pop();
            answer[pop]=prices.length-(pop+1);
        }
        return answer;
    }
}

Stack에 prices배열값을 계속 쌓고 값이 떨어지지 않은 주식의 인덱스값만을 저장해준다.

반복문을 돌려서 스택을 peek한 값과 배열값을 비교하여 peek한 값이 더 클 경우 주식의 값이 떨어진 것이므로,

스택에서 pop하여 꺼내주고 pop한 인덱스와 현재 인덱스의 차이만큼 answer배열에 저장해준다.

중간에 값이 떨어진 주식들은 위와 같은 방법으로 answer배열에 기록해주고,

끝까지 가격이 떨어지지 않은 주식들은 스택에 쌓아놨기때문에 마지막에 반복문을 이용하여 값을 계산하여 answer배열에 기록해준다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

+4+1-2+1 = 4
+4-1+2-1 = 4

주어진 숫자로 target 자연수를 표현할 수 있는 표현의 가지수를 return하는 문제이다.

모든 경우의 수를 다 검사해봐야하므로 dfs(깊이 우선탐색)을 이용하여 문제를 풀었다.

1. 코드

class Solution {
    int[] numbers;
    int target;
    int answer;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        this.numbers = numbers;
        this.target = target;
        
        dfs(0,0);
        
        return answer;
    }
    
    void dfs(int index, int sum){
        //1.탈출 조건
        if(index==numbers.length){
            if(sum==target)answer++;
            return;
        }
        
        //2.수행 동작
        dfs(index+1, sum+numbers[index]);
        dfs(index+1, sum-numbers[index]);
    }
}

dfs 함수를 만들어서 재귀적으로 다음인덱스를 호출하면서 모든 경우의 수를 검사하도록 하였다.

해당 코드에 대한 자세한 풀이는 아래 링크를 참고하기를 바란다.

-출처 : https://www.youtube.com/watch?v=S2JDw9oNNDk

자연수 n이 주어지고, 연속된 자연수들의 합으로 표현할 수 있는 가지수를 return 하는 문제이다.

이중 for문으로 모든경우를 탐색하는 방법을 사용하였다.

1. 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int sum = 0; 
        
        //1부터 n까지 검사
        for(int i=1;i<=n; i++){
            sum = i;
            //자기 자신이 합인 경우
            if(sum==n){
                answer++;
                break;
            }
            
            //연속한 다음수부터 더하기
            for(int j=i+1; j<=n; j++){
                sum += j;
                if(sum==n){
                    answer++;
                    break;
                }else if(sum>n){//합이 n을 넘을 경우 효율성을 위해 break
                    break;
                }
            }
        }
        return answer;
    }
}

이중 for문을 사용하였고, 첫번째 for문에서 시작점을 정하고 두번째  for문에서는 연속된 자연수의 합을 구하여야하므로

시작점의 다음 자연수부터 차례로 더하였다. 더하는 동안 n의 값과 일치하면 answer++을 해주는 방식으로 문제를 풀었다.

처음에 정확성 테스트는 다 통과하는데 효율성 테스트에서 통과하지 못해서(문제가 간단한만큼 효율성 체크 기준이 빡빡한 것 같았다)

else if문으로 sum>n을 넘는 경우 더이상 돌지 않고 바로 break로 반복문을 나오게끔 하니 효율성 테스트에도 모두 통과하였다.

()의 짝을 찾아 모든 괄호가 닫혀있으면 true를, 아니라면 false를 반환하는 문제이다.

1. 문제풀이

괄호의 짝을 찾아야 하므로, '('문자를 찾아와서 뒤의 문자 중 ')' 문자가 존재하는지 확인하는 방식으로 접근하였다.

이중 for문을 사용하였고, start, end 변수를 선언하여 짝이 지어진 '(', ')' 문자는 검사하지 않도록 제외하였다.

효율성을 위해  StringBuilder객체를 선언하여 sb 변수에 짝이 지어진 괄호는 공백으로 치환하게끔 하여

for문 다 돌고 나온 sb 문자에 공백이 아닌 값이 존재한다면 false값을 반환하도록 하였다.

2. 코드

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        StringBuilder sb = new StringBuilder(s); //효율성을 위해 StringBuilder로 선언
        int start = 0; //시작기준 인덱스
        int end = 0; //끝기준 인덱스
        
        //s 길이만큼 반복
        for(int i=0;i<s.length(); i++){
            char now = s.charAt(i); //문자하나씩 자름
            start = i;
            
            if(now=='('){
                start = i;
                //끝기준 인덱스 다음 문자부터 검사
                for(int j=end+1; j<s.length();j++){
                    char match = s.charAt(j);
                    //닫힌괄호면서, ')'의 순서가 찾은'('보다 뒤에 있는 경우
                    if(match==')'&& start<j){
                        sb.setCharAt(j,' ');//sb의 인덱스를 공백으로 치환
                        sb.setCharAt(start,' ');
                        end = j;//')'를 짝으로 사용했으므로 끝 인덱스 변경해줌
                        break;
                    }
                }
            }
        }
        
        //sb에 공백이 아닌값이 존재하면 짝없는 괄호가 존재하는것 이므로 false를 리턴
        for(int i=0;i<sb.length();i++){
            char now = sb.charAt(i);
            if(now!=' '){
                return false;
            }
        }

        return true;
    }
}

처음에 substring 함수를 사용하여 now, match 변수를 잘랐는데, 효율성 검사에서 통과하지 못하였다.

따라서 효율성을 높이기 위해 char 변수로 비교하도록 charAt 함수를 사용하고, now, match 변수 또한

char타입으로 선언해 주었다.

위와 같이 변경하니 효율성 테스트에도 통과하였다.

하지만, 위의 문제를 Stack구조를 사용하면

더 간단하게 풀 수 있다는 사실을 검색을 통해 알게되었다.

아래는 Stack 구조를 이용한 코드이다.

3. 개선된 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            //여는 괄호일 때
            if(c == '('){
                stack.push(c);
            }
            
            //닫는 괄호일 때
            if(c == ')'){
                if(stack.size() == 0){
                    return false;
                }
                else stack.pop();
            }
        }
        if(stack.size() != 0) answer = false;

        return answer;
    }
}

출처 : https://hyojun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%98%AC%EB%B0%94%EB%A5%B8-%EA%B4%84%ED%98%B8-Java