exp_blog

문제 설명

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 TUE를 반환하세요.

제한 조건

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

입출력 예

나의 코드

class Solution {
  public String solution(int a, int b) {
		String answer = "";
		int totalDay = 0; 
		int dayOfMonth = 0;
      
      //현재 월 이전까지의 총 일 수를 구함
		for(int i=1; i<a; i++) { 
			if(i == 1 || i == 3 || i == 5 || i == 7 || i == 8  || i == 10 || i == 12) dayOfMonth = 31;
			else if(i == 2) dayOfMonth = 29;
			else dayOfMonth = 30;
			
			totalDay += dayOfMonth; 
		}
      //현재 월의 일수를 더함
		totalDay += b;
		
        //1월1일은 금요일 / 7로 나눈 나머지가 1인 경우 금요일
		switch(totalDay % 7) {
		case 0:
			answer = "THU";
			break;
		case 1:
			answer = "FRI";
			break;
		case 2:
			answer = "SAT";
			break;
		case 3:
			answer = "SUN";
			break;
		case 4:
			answer = "MON";
			break;
		case 5:
			answer = "TUE";
			break;
		case 6:
			answer = "WED";
			break;
		
		}
		
		return answer;
	}
}

다른 사람 코드

라이브러리 사용하는거..신기방기..

// 문제가 개편 되었습니다. 이로 인해 함수 구성이 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
// 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
import java.util.*;

class TryHelloWorld
{
    public String getDayName(int month, int day)
    {
        Calendar cal = new Calendar.Builder().setCalendarType("iso8601")
                        .setDate(2016, month - 1, day).build();
        return cal.getDisplayName(Calendar.DAY_OF_WEEK, Calendar.SHORT, new Locale("ko-KR")).toUpperCase();
    }
    public static void main(String[] args)
    {
        TryHelloWorld test = new TryHelloWorld();
        int a=5, b=24;
        System.out.println(test.getDayName(a,b));
    }
}

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.
• numbers의 원소는 0 이상 1,000 이하입니다.
• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

Java Comparable, Comparator

Comparable, Comparator하면 '정렬'을 떠올려야하는 것이다.

우선 자바에서 객체를 정렬할 때 일정한 기준이 필요하다.

Comparable : 객체 간의 일반적인 정렬이 필요할 때, Comparable 인터페이스를 확장해서 정렬의 기준을 정의하는 compareTo() 메서드를 구현한다.

Comparator : 객체 간의 특정한 정렬이 필요할 때, Comparator 인터페이스를 확장해서 특정 기준을 정의하는 compare() 메서드를 구현한다.

공통점은 정렬의 기준을 정의한다는 것이고,

차이점은 정렬 기준이

-일반적이냐 일반적이지 않냐와

-compareTo(Object o) 메서드를 구현하느냐 compare(Object o1, Object o2) 메서드를 구현하느냐

Comparable 구현

Student Vo를 생성하여 Comparable 인터페이스를 구현하였다. Comparable 인터페이스를 구현하는 경우

public int compareTo(T) 메소드를 구현하고 내부에서 비교처리 후 int형 리턴으로 비교 결과를 리턴한다.

• 양수리턴 : this 오브젝트가 앞에 위치
• 음수리턴 : this 오브젝트가 뒤에 위치
• 0리턴 : 동일한 값으로 간주하고 입력 순서 유지

아래와 같이 테스트를 수행하는 경우

이렇게 이름순으로 먼저 정렬되고, 이름이 같은 경우 나이순으로 정렬된 결과를 얻는다.

이지수 30
이지수 31
홍길동 27

Comparator 구현

Comparator는 보통 다음과 같은 상황에서 사용된다.

1. JAVA에서 기본제공하는 Reference Type을 내가 원하는대로 정렬하고 싶을때 (예시 : String, Integer를 역순으로 정렬 혹은 특정추가 조건)
2. 기존에 구현된 Comparable의 정렬과는 다른 결과를 얻고 싶을 때

즉 기존에 구현되어 있는 Comparable 인터페이스 구현 대신에 다른 조건에 의해서 정렬하고자 하는 경우 사용된다.

Arrays.sort() 혹은 Collections.sort()에 두번째 인자로 Comparator 구현체를 전달하여 주면 된다.

홍길동 27
이지수 30
이지수 31

출처: https://javaplant.tistory.com/15 [자바공작소]

Comparator 함수를 찾아보다가 정리해본다.. 자바는 끝이없고..

내가 짠 코드

import java.util.*;


class Solution {
    public String solution(int[] numbers) {
        String answer = ""; // 리턴값 초기화
        String[] str_numbers = new String[numbers.length]; // 파라미터 numbers 배열의 길이와 같은 string 배열을 생성
        // int 배열인 numbers를 string배열인 str_numbers로 변환
        for (int i = 0 ; i < numbers.length ; i++) {
            str_numbers[i] = String.valueOf(numbers[i]);
        }
        // str_numbers를 Compare()에 정의된 방식으로 정렬
        Arrays.sort(str_numbers, new Compare());
        // 현재 str_numbers는 올림차순으로 정렬되어 있음
        // 따라서 가장 마지막 인덱스의 값이 max값이고, 이것이 반환값의 가장 앞에 올 숫자임
        // 반환값의 맨 앞 숫자가 0이면 answer=0 
        // 반환값의 맨 앞 숫자가 0이 아니면 내림차순으로(가장 큰 수부터) answer에 담음
        if (str_numbers[str_numbers.length - 1].equals("0")) {
            answer += "0";
        } else {
            for (int i = str_numbers.length - 1; i >= 0; i--) {
                // Compare 클래스에서 올림차순 정렬을 했다면 아래 코드 사용
                // for(int i = 0 ; i < str_numbers.length ; i++)
                answer += str_numbers[i];
            }
        }
        return answer;
    }
}
// Comparator 인터페이스를 오버라이딩하여 정렬 방식을 재정의하기
class Compare implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return (o1 + o2).compareTo(o2 + o1);// 올림차순 정렬
        
        // 내림차순 정렬은 아래와 같이 순서를 바꾸어주면 된다
        // return (o2 + o1).compareTo(o1 + o2);
    }
}

다른 사람이 짠 코드(콜렉션 함수 사용)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public String solution(int[] numbers) {
        String answer = "";

        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; i++) {
            list.add(numbers[i]);
        }
        Collections.sort(list, (a, b) -> {
            String as = String.valueOf(a), bs = String.valueOf(b);
            return -Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
        });
        StringBuilder sb = new StringBuilder();
        for(Integer i : list) {
            sb.append(i);
        }
        answer = sb.toString();
        if(answer.charAt(0) == '0') {
            return "0";
        }else {
            return answer;
        }
    }
}

문제 설명

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

입출력 예

입출력 설명
[1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.입출력 예 설명

[1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
[1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다.

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1. array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3. 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

내가 푼 코드

import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int[] tmp = {};
        
        for(int i = 0; i < commands.length; i++){
            tmp = Arrays.copyOfRange(array, commands[i][0]-1,  commands[i][1]);
            /*Arrays.copyOfRange(a,b,c) : arrays 에 들어있는 a[] 배열을 b부터 c까지 복사 하는 함수*/
            Arrays.sort(tmp);
            //tmp 에 옮겨진 부분에 대하여 정렬하고 k번째 숫자를 답으로 담음
            
            answer[i] = tmp[commands[i][2]-1];
            /*배열의 index가 0부터 시작하기 떄문에 -1을 해준다.*/
        }
        return answer;
    }
}

다른사람이 푼 코드(라이브러리 사용하지 않고 ... 대단..)

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int n = 0;
        int[] ret = new int[commands.length];

        while(n < commands.length){
            int m = commands[n][1] - commands[n][0] + 1;

            if(m == 1){
                ret[n] = array[commands[n++][0]-1];
                continue;
            }

            int[] a = new int[m];
            int j = 0;
            for(int i = commands[n][0]-1; i < commands[n][1]; i++)
                a[j++] = array[i];

            sort(a, 0, m-1);

            ret[n] = a[commands[n++][2]-1];
        }

        return ret;
    }

    void sort(int[] a, int left, int right){
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];

        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                int temp = a[pl];
                a[pl] = a[pr];
                a[pr] = temp;
                pl++;
                pr--;
            }
        }while(pl <= pr);

        if(left < pr) sort(a, left, pr);
        if(right > pl) sort(a, pl, right);
    }
}

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

탐욕법 알고리즘이란?

• 문제를 작은 단위로 쪼개고 반복적으로 진행하며 접근하는 방식은 완전탐색 등과 유사
• But, 탐욕법은 각 단계에서 그 시점에 가장 좋아 보이는 선택을 한다.
• 앞으로의 선택 혹은 최종 결과는 고려하지 않는다.
• 탐욕법의 해가 반드시 최적의 해라는 보장은 없다.

와 같은 특징을 갖고 있습니다. 탐욕법은 당장 앞에 보이는 가장 좋아보이는 선택을 하는 특징이 있는데, 이는 반드시 최적의 해임을 보장할 수는 없지만, 간단한 알고리즘문제의 경우  괜찮은 결과를 보여주기도 하는 풀이방법

1.해 선택(selection procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가

2.적절성 검사(feasibility check) : 새로운 부분해 집합이 적절한지 검사

3.해 검사(solution check) : 새로운 부분해 집합이 문제의 해가 되는지 검사 

                                         -> 아직 문제의 해가 완성되지 않았다면 1번 부터 다시 시작

<<생각해보자>>

• 안전빵으로 체육수업들을 수 있는 학생의 수가?

((전체 학생수 (n)에서 lost 배열의 길이(학생수) 만큼 뺀 수 

                                      +

여벌을 가져왔는데? 도둑맞은 사람의 수 아닌가?))

• 여분이 있는 학생의 값을 1씩 더하고 뺀 값이 lost 배열에 있는가?
• 검사해서 true -> true인 reverse 배열의 값을 임의의 음수로 설정하자
• 들을 수 있는 학생수를 ++하게 하고 다음 reverse를 진행하자 이러면되려나?

=> 여벌을 가져왔던 친구가 도난을 당하면 그 친구는 1벌을 갖게 된다 

=> 여벌이 도난당하므로 자신이 입을 체육복만 소지한 채 일반 학생이 되어 answer에 +1 해주어야 하지(잃어버리지도 여벌도 없으니)

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        int[] student = new int[n+1];
        //1 ~ 30이니까 그냥 n이라고 정의하고 시작하자
        
        //student 배열 초기화하자
        for(int i = 1; i <= n; i++)
            student[i] = 1;
        
        for(int l:lost){
            student[l]--;
        }
        for(int r:reserve){
            student[r]++;
        }
        
        //없는 친구끼리 빌려주자
        for(int i=1;i<=n;i++){
            if(student[i]==0){
                if(i+1<=n && student[i+1]==2){
                    student[i+1]--;
                    student[i]++;
                } else if(i-1>=1 && student[i-1]==2){
                    student[i-1]--;
                    student[i]++;
                }
            }
        }
        
     // 체육복을 1개이상 가지고 있으면 수업을 들을 수 있음
        for(int i=1;i<=n;i++){
            if(student[i]>=1)
                answer++;
        }
        
        return answer;
    }
}

<다른 사람이 푼 코드>

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = 0;
        answer = n;
        for(int i = 0; i < lost.length; i++) {
            boolean rent = false; //여분이 있는지 없는지 체크
            int j = 0;
            while(!rent) {
                if(j == reserve.length) //reserve마지막까지 돌면 while나오기
                    break;
                if(lost[i] == reserve[j])  //if와 else if로 lost와 reserve상쇄
                {
                    reserve[j] = -1; 
                    rent=true;
                }
                else if(lost[i] - reserve[j] == 1 )
                {
                    reserve[j] = -1; 
                    rent=true;
                }
                else if(lost[i] - reserve[j] == -1)
                {
                    reserve[j] = -1; 
                    rent=true;
                }
                else
                    j++;
            }
            if(!rent) //여분이 있어 true로 바꿨다면 수행하지 않지만 아닐경우엔 수행
                answer--;
        }
        return answer;
    }
}

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participantcompletionreturn

입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

##시간복잡도를 줄이기 위해 hashMap을 사용하여야 한다

-> HashMap은 Map을 구현한다. Key와 value를 묶어 하나의 entry로 저장한다는 특징을 갖는다. 그리고 hashing을 사용하기 때문에 많은양의 데이터를 검색하는데 뛰어난 성능을 보인다.

• Map 인터페이스의 한 종류로 ( "Key", value) 로 이뤄져 있다.
• key 값을 중복이 불가능 하고 value는 중복이 가능. value에 null값도 사용 가능하다.
• 멀티쓰레드에서 동시에 HashMap을 건드려 Key - value값을 사용하면 문제가 될 수 있다. 멀티쓰레드에서는 HashTable을 쓴다

. HashMap 생성자 / 메서드

출처: https://vaert.tistory.com/107 [Vaert Street]

<hash 사용>

import java.util.*; 
  
class Solution { 
    public String solution(String[] participant, String[] completion) { 
        Map<String, Integer> hash = new HashMap<>(); 
        for (String arg : participant) hash.put(arg, hash.getOrDefault(arg, 0) + 1); 
//getOrDefault를 넣어주지 않으면 중복 체크가 되지 않음 , HashMap의 put은 key가 존재하면 value를 새로운 값으로 바꿔주니까 / 이미 등록된 동명이인이 있다면 hm.getOrDefault로 인해서 2라는 값이 들어감

        for (String arg : completion) hash.put(arg, hash.get(arg) - 1); 
  
        for (String key : hash.keySet()) { 
            if (hash.get(key) != 0) return key; 
        } 
  
        return null; 
    } 
}

<다른 사람 답>

import java.util.*; 
class Solution { 
    public String solution(String[] participant, String[] completion) { 
        Arrays.sort(participant); 
        Arrays.sort(completion); 
        int i; 
        for ( i=0; i<completion.length; i++){ 

            if (!participant[i].equals(completion[i])){ 
                return participant[i]; 
            } 
        } 
        return participant[i]; 
    } 
}