12시간제를 24시간제로 시간증가하여 변환

목표

자연수 N을 오름차순과 내림차순으로 각각 정렬하여 두 값을 합산한 결과를 반환하시요

조건

• time의 값은 오전과 오후가 각각 “AM”, “PM” 으로 표시하며 12시간제로 “시:분:초” 의 형태를 가짐
• 시분초는 한자리 수라도 두자리로 표시
• N <= 200,000

예시

time	n	result
AM 12:01:00	1	00:01:01
PM 12:01:00	2	12:01:02
PM 09:01:40	50	21:02:10
AM 11:01:00	3700	00:02:40

코드

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Solution {
    //p = 시간 , n = 증가할 sec
 public String solution(String time, int n) throws IllegalArgumentException {

  String answer = null;
        Matcher matcher = Pattern.compile("(\\w+) (\\d+):(\\d+):(\\d+)").matcher(time);
        
        if(matcher.find()){
            boolean isPm = matcher.group(1).toUpperCase().equals("PM");
            int hour = Integer.parseInt(matcher.group(2));
            int min = Integer.parseInt(matcher.group(3));
            int sec = Integer.parseInt(matcher.group(4)) + n;
            
            min += sec/60;
            sec %= 60;
            
            hour += min/60;
            min %= 60;
            
            if(isPm && hour!=12){
                hour += 12;
                if(hour > 24){
                    hour %= 24;
                }
            }
            if(!isPm && hour==12){
                hour -= 12;
            }
            
            answer = String.format("%02d:%02d:%02d",hour,min,sec);
      return answer;
        }
        
        throw new IllegalArgumentException("time format is illegal");
 }
}

Read more →

숫자를 정렬,역정렬하여 합산

목표

자연수 N을 오름차순과 내림차순으로 각각 정렬하여 두 값을 합산한 결과를 반환하시요

조건

• N >= 1 || N <= 1,000,000,000

예시

N	process	result
2613	1236 + 6321	7557
33285	23358 + 85332	108690

코드

import java.util.*;

public class Solution {
 public int solution(int N) {
  int answer = -1;
        
        
        char[] splitNum = String.valueOf(N).toCharArray();
        Arrays.sort(splitNum);
        answer = Integer.parseInt(new String(splitNum));
        
        String reverseNum = "";
        for(int i=splitNum.length-1; i>=0; i--){
            reverseNum += splitNum[i];
        }
        
        answer += Integer.parseInt(reverseNum);
  return answer;
 }
}

Read more →

쌍이 아닌 배열값 검사

목표

cards 배열에서 쌍이 아닌 개체값 을 반환하시요.

조건

• cards.length = N * 2 - 1
• N >= 1,000,000
• cards 개체값 >= 100,000,000

예시

cards	answer
[1,3,2,2,5,5,1]	3
[7,2,3,9,1,2,5,3,9,7,1]	5

코드

import java.util.*;
import java.util.Arrays;

class Solution {
 public int solution(int[] cards) throws NoSuchElementException{
        
        // cards.length = 짝수
        // cards = 쌍으로 값이 존재
        Map<Integer,Integer> checkMap = new HashMap<>();
        
        for(int i=0;cards.length>i; i++){
            if(checkMap.containsKey(cards[i])){
                checkMap.put(cards[i],2);
            }else{
                checkMap.put(cards[i],1);
            }
        }
        
        for (Integer card : checkMap.keySet()){
            if (checkMap.get(card).equals(1)) {
                return card;
            }
        }
  
        throw new NoSuchElementException("not found unpaired card");
 }
}

Read more →

프로그래머스 알고리즘, 가장 큰 수

목표 (문제)

주어진 배열의 수를 조합하여 가장 큰 수를 만든다.

조건

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

잡설

생각한 과정에서 문제가 생겨 더이상 진행하지 못하고 다른 풀이를 보았는데 comparator를 사용한걸 알게되었다. 해당 comparator에 대해 기록해봐야겠다.

코드

 public static String solution(int[] numbers) {

    String answer ="";
    List<String> list = new ArrayList<>();
    int length = numbers.length;

    for(int i=0; i<length; i++){
        list.add(Integer.toString(numbers[i]));
    }

    int size = list.size();
    Collections.sort(list, new Comparator<String>(){
        @Override
        public int compare(String num1,String num2){
            return (num2+num1).compareTo(num1+num2);
        }
    });
    if(list.get(0).equals("0")){
        return "0";
    }

    for(int i=0; i<size; i++){
        answer = answer + list.get(i);
    }
    return answer;
}

참조

잘못된 시도

잡설

처음 구조를 작성할때 Collections.sort를 string 일때 정렬하면 자리값 별로 비교하던것에 꽂혀서 구성을 했던것이 문제였던 것 같다. 비교하는 과정이 올바르지 않았기에 발생한 문제인것으로 생각한다.

코드

public static String solution(int[] numbers) {
 // int[0~9][0~n] 2차배열 생성
 List<LinkedList<String>> numberGroup = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     numberGroup.add(new LinkedList<>());
 }

 // 맨앞자리 숫자값으로 분류하여 배열 삽입
 for (int num : numbers) {
     String temp = Integer.toString(num);
     int numIndex = Integer.parseInt(temp.substring(0, 1));// 앞부분 때기
     numberGroup.get(numIndex).add(temp);
 }

 // 배열 정렬
 for (LinkedList<String> numberList : numberGroup) {
        Collections.sort(numberList, Collections.reverseOrder());
 }

 // 문자열 병합
 StringBuilder result = new StringBuilder();
 for (int i = numberGroup.size() - 1; i >= 0; i--) {
     System.out.println(numberGroup.get(i));
     for (String number : numberGroup.get(i)) {
         result.append(number);
     }
 }
 return result.toString();
}

참조 - https://n1tjrgns.tistory.com/139

Read more →

프로그래머스 알고리즘, 모의고사

목표 (문제)

1~5까지를 일정한 패턴으로 반복할때, 그 값들을 주어진 answers와 비교하여 일치하는 값의 갯수들을 배열로 반환하시요.

조건

• answers 의 길이는 최대 10,000 입니다.
• 배열값은 반드시 1, 2, 3, 4, 5 중 하나입니다.
• 일치하는 개수가 동일할 경우, Index를 기준으로 오름차순 정렬해주세요.
• 일치하는 값이 모두 없을때, 두 반환합니다.

코드

public class Main {

    public static void main(String[] args) {
//        int[] answers = { 1, 2, 3, 4, 5 };
//        int[] answers = { 1,3,2,4,2 };
        int[] answers = { 3, 1, 1 };
//        int[] answers = { 4, 4 };

        for (int val : solution(numbers)) {
            System.out.print(val + ",");
        }
    }

    public static int[] solution(int[] answers) {
        int persons[][] = { { 1, 2, 3, 4, 5 }, { 2, 1, 2, 3, 2, 4, 2, 5 }, { 3, 3, 1, 1, 2, 2, 4, 4, 5, 5 } };
        int result[][] = new int[persons.length][2];

  // 결과값 구조 초기화
        for (int i = 0, len = result.length; i < len; i++) {
            result[i][0] = i + 1;
            result[i][1] = 0;
        }
  
  // 패턴대로 순환하며 일치 개수 체크
        for (int i = 0, len = answers.length; i < len; i++) {
            for (int j = 0; j < persons.length; j++) {
                if (persons[j][i % persons[j].length] == answers[i])
                    result[j][1]++;
            }
        }

  // 일치개수 기반하여 정렬
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] back, int[] front) {
                return front[1] - back[1];
            }
        });

  // 출력할 길이 지정하여 반환값 설정
        int length = result[0][1] == 0 ? result.length : 1;
        int[] answer = new int[length];
        for (int i = 0; i < length; i++) {
            answer[i] = result[i][0];
        }

        return answer;
    }
}

Read more →

프로그래머스 알고리즘, 소수찾기2

목표 (문제)

주어진 numbers의 각각 숫자들을 조합하여 만들 수 있는 모든 소수의 수를 반환하세요.

조건

• numbers는 길이가 1 ~ 7 인 문자열입니다.
• numbers는 0~9 까지 숫자값만으로 이루어져 있습니다.
• 013은 0, 1, 3 숫자로 조합하면 됩니다.
• 11과 011은 같은 숫자로 취급합니다.

코드

동작

오류 발생

Set<Integer> lhs = new LinkedHashSet<Integer>();

public int solution(String numbers) {
    makeCombination("", numbers);
    return getPrimeCount(new LinkedList<Integer>(lhs));
}

public int getPrimeCount(LinkedList<Integer> numbers) {
    for (int prime : new int[] { 2, 3, 5, 7 }) {
        for (int i = 0; i < numbers.size(); i++) {
            int number = numbers.get(i);
            if (number < 2 || (number % prime == 0 && number != prime)) {
                numbers.remove(i--);
            }
        }
    }
    return numbers.size();
}

public void makeCombination(String s, String number) {
    if (number.length() == 0) {
        if (!s.equals("")) {
            lhs.add(Integer.parseInt(s));
        }
    } else {
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s + number.charAt(i), number.substring(0, i) + number.substring(i + 1, number.length()));
        }
        for (int i = 0; i < number.length(); i++) {
            makeCombination(s, number.substring(0, i) + number.substring(i + 1, number.length()));
        }
    }
}

잡설

소수 구하는건 생각해냈지만 숫자조합을 도저히 생각해낼 수 없었기에 결국 찾아보게 되었다. 이곳 에서

Read more →

프로그래머스 알고리즘, H-index

목표 (문제)

int 배열값 들을 H라고 하고 전체 배열에서 조건에 해당되는 배열값의 갯수가 n이라고 할때, n값의 최대를 구하시요.

조건

• H는 n 이상
• n의 값은 1 ~ 1,000
• H의 값은 0 ~ 10,000

코드

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

public class Main {

    public static void main(String[] args) {
//        int[] numbers = { 3, 0, 6, 1, 5 };
//        int[] numbers = { 0, 0, 0 };
        int[] numbers = { 22, 42 };

        System.out.println(solution(numbers));
    }

    public static int[] solution(int[] citations) {
        int answer = 0;

        //정렬위해 List 변환
        List<Integer> list = Arrays.stream(citations).boxed().collect(Collectors.toList());
        //정렬
        Collections.sort(list, Collections.reverseOrder());
        
        //X의 값이 H를 넘지않는 범위에서 순회
        for(Integer citation : list) {
            if (answer < citation) {
                answer++;
            } else {
                break;
            }
        }
        
        return answer;
    }
}

잡설

 boxed() 메서드는 int, long, double 요소를 Integer, Long, Double 요소로 변환하여 저장

Read more →

프로그래머스 알고리즘, K번째 수

목표 (문제)

2차배열인 commands 의 값마다 [i][0]과 [i][1]번을 시작과 끝으로 array 배열에서 분리 후,
오름차순 정렬 하여 command[i][2]의 index에 해당하는 값들을 return 한다.

조건

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

코드

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

public class Main {

    public static void main(String[] args) {
        int[] array = { 1, 5, 2, 6, 3, 7, 4 };
        int[][] commands = { { 2, 5, 3 }, { 4, 4, 1 }, { 1, 7, 3 } };

        for (int val : solution(a, b)) {
            System.out.print(val + ",");
        }
    }

    public static int[] solution(int[] array, int[][] commands) {
        List<Integer> answer = new ArrayList<>();

        for (int cmdIndex = 0; cmdIndex < commands.length; cmdIndex++) {
            int from = --commands[cmdIndex][0];
            int to = commands[cmdIndex][1];

            int[] splitArray = Arrays.copyOfRange(array, from, to);
            Arrays.sort(splitArray);

            int selectedIndex = commands[cmdIndex][2] - 1;
            answer.add(splitArray[selectedIndex]);
        }

        return answer.stream().mapToInt(i -> i).toArray();
    }
}

Read more →

Bucket Sort

버킷 정렬(bucket sort)

인터넷 자료를 보던중 컴퓨터의 세계 밖에서 발견한 O(n) 소팅 이란 게시글을 보게되었다.
보통 정렬 알고리즘은 O(nlogn) 정도가 제일 빠른것으로 표를 통해 보았는데
댓글중 버킷 정렬에 대한 댓글로 버킷정렬에 대해 얘기가 나와 궁금해졌다.

절차

코드

public void bucketSort(int[] numbers) {
 // int[0~9][0~n] 2차배열 생성
 List<LinkedList<String>> numberGroup = new ArrayList<>();
 for (int i = 0; i < 10; i++) {
     numberGroup.add(new LinkedList<>());
 }

 // 맨앞자리 숫자값으로 분류하여 배열 삽입
 for (int num : numbers) {
     String temp = Integer.toString(num);
     int numIndex = Integer.parseInt(temp.substring(0, 1));
     numberGroup.get(numIndex).add(temp);
 }

 // 배열 정렬
 for (LinkedList<String> numberList : numberGroup) {
        Collections.sort(numberList, Collections.reverseOrder());
 }

잡설

처음에 버킷정렬만 들었을 땐 감이 안왔는데 구조를 보자마자 생각난게
알고리즘 풀이 시도중 K번째 수에 사용한 코드가 떠올랐다.
버킷정렬을 고려하고 짠건 아닌데 이런 형태의 정렬구조가 있었음을 알았다.
코드는 해당 풀이에서 가져왔는데 아마 더 나은 예시코드 가 있지않을까?
사실 알게 모르게 다양한 정렬을 쓰고있을 것 이다.

Read more →

프로그래머스 알고리즘, 완주하지 못한 선수

목표 (문제)

completion 배열에서 participant 배열 중 제외된 대상 값을 return

조건

• participant 배열 속 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 선수명이 같은 경우가 있을 수 있습니다.

코드

public String solution(String[] participant, String[] completion) {
    HashMap<String, Integer> start = new HashMap<String, Integer>();
    for (String item : participant) {
        Integer hashItem = start.get(item);
        if (hashItem == null) {
            start.put(item, 1);
        } else {
            start.put(item, hashItem + 1);
        }
    }

    HashMap<String, Integer> retire = (HashMap) start.clone();
    for (String item : completion) {
        retire.put(item, retire.get(item) - 1);
    }
    
    for(String item : retire.keySet()) {
        if(retire.get(item)> 0) {
            return item;
        }
    }
    return null;
}

Read more →

프로그래머스 알고리즘, 베스트 앨범

목표 (문제)

1. 같은 장르가 많은 노래 그룹을 먼저 수록합니다.
2. 같은 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

조건

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

잡설

domain 구성하면 복잡하지 않게 해결될거같긴 한데 다른방법도 해보고 싶어서
나름 구성해보았으나… 저 sort 메서드를 합칠 방법이 뭐가 있을까?
분명히 저렇게 중복되는걸 자료형 선택해서 하나의 메서드로 합쳐 처리하는 방법이 있을텐데
그걸 모르겠네

코드

import java.util.*;
import java.util.Map.Entry;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, HashMap<Integer, Integer>> music = new HashMap<>();
        HashMap<String, Integer> total = new HashMap<>();

        for (int index = 0, maxIndex = plays.length; index < maxIndex; index++) {
            HashMap<Integer, Integer> item;
            if (music.containsKey(genres[index])) {
                item = music.get(genres[index]);
                total.put(genres[index], total.get(genres[index]) + plays[index]);
            } else {
                item = new HashMap<>();
                total.put(genres[index], plays[index]);
            }
            item.put(index, plays[index]);
            music.put(genres[index], item);
        }

        List<Integer> answer = new ArrayList<>();
        for (String item : sortTotal(total).keySet()) {
            Set<Integer> sortedMusic = sortMusic(music.get(item)).keySet();
            int index = 0;
            for (Integer item2 : sortedMusic) {
                if (index++ > 1 ) {
                    break;
                }
                answer.add(item2);
            }
        }
        return answer.stream().mapToInt(i->i).toArray();
    }

    public LinkedHashMap<String, Integer> sortTotal(HashMap<String, Integer> total) {
        List<Entry<String, Integer>> list = new ArrayList<>(total.entrySet());
        list.sort(Entry.comparingByValue(Comparator.reverseOrder()));

        LinkedHashMap<String, Integer> sortedTotal = new LinkedHashMap<>();
        for (Entry<String, Integer> entry : list) {
            sortedTotal.put(entry.getKey(), entry.getValue());
        }

        return sortedTotal;
    }

    public LinkedHashMap<Integer, Integer> sortMusic(HashMap<Integer, Integer> music) {
        List<Entry<Integer, Integer>> list = new ArrayList<>(music.entrySet());
        list.sort(Entry.comparingByValue(Comparator.reverseOrder()));

        LinkedHashMap<Integer, Integer> sortedMusic = new LinkedHashMap<>();
        for (Entry<Integer, Integer> entry : list) {
            sortedMusic.put(entry.getKey(), entry.getValue());
        }

        return sortedMusic;
    }
}

Read more →

Comparable, Comparator

핵심

객체가 정렬될때, 사용자의 의도에 따라 정렬 구조를 변경할 수 있도록 지원되는 인터페이스

기본 코드

public static void main(String[] args) {
    List<Player> footballTeam = new ArrayList<>();
    Player player1 = new Player(59, "John", 20);
    Player player2 = new Player(67, "Roger", 22);
    Player player3 = new Player(45, "Steven", 24);
    footballTeam.add(player1);
    footballTeam.add(player2);
    footballTeam.add(player3);
 
    System.out.println("Before Sorting : " + footballTeam);
    Collections.sort(footballTeam);
    System.out.println("After Sorting : " + footballTeam);
}

public class Player {
    private int ranking;
    private String name;
    private int age;  
    Player(int ranking, String name, int age){
     // constructor
    }
    // getters, setters  
}

Comparable

정의

구현되는 클래스의 기본 정렬기준을 별도로 구현
정렬 기준을 변경하기 위해 정렬대상에게 Comparable 인터페이스의 compareTo(Object obj) 를 구현한다. 해당 메서드에서 비교 대상의 개체가 인수로 전달되는 개체보다 작거나 같은지 또는 큰지 여부를 나타내는 숫자로 반환한다.

코드

public class Player implements Comparable<Player> {
    @Override
    public int compareTo(Player otherPlayer) {
     // ranking 값이 작은 순으로 정렬
        return (this.getRanking() - otherPlayer.getRanking());
    }
}

Before Sorting : [John, Roger, Steven]
After Sorting : [Steven, John, Roger]

Comparator

정의

기존에 Comparable의 compareTo로 구현된 것이 아닌 별도의 정렬기준을 적용할때

코드

익명 클래스로 선언하여 사용편리

Collections.sort(playerList, new Comparator<Player>(){
    @Override
    public int compare(Player firstPlayer,Player secondPlayer){
        return (firstPlayer.getRanking() - secondPlayer.getRanking());
    }
});

Lambda 사용시

Collections.sort(playerList,(firstPlayer, secondPlayer) -> firstPlayer.getRanking() - secondPlayer.getRanking());

참조

• https://www.baeldung.com/java-comparator-comparable
• https://cwondev.tistory.com/15

Read more →