Henry's Algorithm

안녕하세요~~

알고리즘을 공부하는 개발자 Henry입니다ㅎㅎ

오늘도 21년 신년을 맞이하여 프로그래머스 문제를 한번 풀어보았습니다.

오늘은 문자열을 파싱하여 푸는 문제인데요, 문제는 아래와 같습니다.

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s         result

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다.
문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다.
문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다.
문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 풀이 방식:

문자열을 입력받았을 때,

앞에서부터 몇개의 단위로 압축을 하면 가장 압출률이 좋은지를 판단하는 문제입니다.

해당 문제는 문자열 파싱을 하는 능력과

이중 for문을 통해서 풀 수 있습니다.

정답 코드:

def solution(s):
    
    if len(s) == 1:
        return 1
    
    result = ""
    length = []
    cut = 1
    
    for i in range(1,len(s)//2+1):
        cnt = 1
        temp_str = s[:i]
        
        for j in range(i,len(s),i):
            if temp_str == s[j:j+i]:
                cnt += 1
            else:
                if cnt == 1:
                    cnt = ""
                result += str(cnt) + temp_str
                cnt = 1
                temp_str = s[j:j+i]
        if cnt == 1:
            cnt = ""
        result += str(cnt) + temp_str
        length.append(len(result))
        result = ""
    #print(length)
    return min(length)
        
        
        

문제는 푸는 방법을 잘 살펴보시면

따로 특별한 알고리즘일 있는 것이 아닌,

순차적으로 완전탐색하는 방법으로 풀어야 하는 것을 아실 수 있으실 거예여.

그래도 압축이라는 것이 전체 길이의 /2가 최대로 압축할 수 있는 가능성이 있기 때문에

그 때까지 단위를 올려가면서 압축률을 비교해보는 문제입니다.

아래는 저의 youtube 강의입니다.

혹시 푸시다가 어려우시면 언제든지 오셔서 시청해주세요~~

좋아요 구독도 눌려주세요!ㅎㅎ

www.youtube.com/watch?v=9bVloX96Dj4

자바 코드로 풀었다.

문제 설명

array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

제한사항

• arr은 자연수를 담은 배열입니다.
• 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
• divisor는 자연수입니다.
• array는 길이 1 이상인 배열입니다.

입출력 예

arr      divisor       return

입출력 예 설명

입출력 예#1
arr의 원소 중 5로 나누어 떨어지는 원소는 5와 10입니다. 따라서 [5, 10]을 리턴합니다.

입출력 예#2
arr의 모든 원소는 1으로 나누어 떨어집니다. 원소를 오름차순으로 정렬해 [1, 2, 3, 36]을 리턴합니다.

입출력 예#3
3, 2, 6은 10으로 나누어 떨어지지 않습니다. 나누어 떨어지는 원소가 없으므로 [-1]을 리턴합니다.

문제 푸는 방법:

완전 탐색으로 하나씩 divisor와 나누어주면 된다.

정렬할 때는

Collections.sort();를 쓰면 되고,

내림차순 정렬할 때는 Collections.sort(arr,Collections.reverseOrder()); 라고 하면 된다.

정답 코드는 아래와 같다.

import java.util.*;
    
class Solution {
    public int[] solution(int[] arr, int divisor) {
        int[] answer;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<arr.length; i++){
            if(arr[i]%divisor == 0){
                list.add(arr[i]);
            }
        }
        Collections.sort(list);
        answer = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        if(answer.length == 0){
            int[] answer2 = {-1};
            return answer2;
        }
        return answer;
    }
}

자바 코드로 풀어보았다~

문제 설명

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면,

• arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
• arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 arr의 크기 : 1,000,000 이하의 자연수
• 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수

입출력 예

arr       answer

입출력 예 설명

입출력 예 #1,2
문제의 예시와 같습니다.

문제 푸는 방법:

arr를 한번씩 돌면서 이전과 다를때 추가해주면 된다.

정답 코드

import java.util.*;

public class Solution {
    public int[] solution(int []arr) {
        int[] answer;
        ArrayList<Integer> list = new ArrayList<>();
        int cur = arr[0];
        for(int i=1; i<arr.length; i++){
            if(cur != arr[i]){
                list.add(cur);
                cur = arr[i];
            }
        }
        list.add(cur);
        answer = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            answer[i] = list.get(i);
        }
        
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("Hello Java");

        return answer;
    }
}

자바 코드로 풀었다!!

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예

n        result

입출력 예 설명

입출력 예 #1

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)      n (3진법)      앞뒤 반전(3진법)      10진법으로 표현

• 따라서 7을 return 해야 합니다.

입출력 예 #2

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)        n (3진법)       앞뒤 반전(3진법)      10진법으로 표현

• 따라서 229를 return 해야 합니다.

문제 푸는 방법:

int 로 계산하면 너무 큰 숫자에 대해서는 받아줄 수 없으므로,

Long으로 계산해준다.

그리고 char -> int로 바꾸어주는 Character.getNumericValue(c); 를 사용하는 것도 필요하다.

정답 코드는 아래와 같다.

import java.lang.Math;

class Solution {
    public int solution(int n) {
        int answer = 0;
        String str = Long.toString(Long.parseLong(convert(n)));
        int idx = 0;
        for(int i=str.length()-1; i>-1;i--){
            System.out.println("i:"+i);
            answer += Math.pow(3,i)*Character.getNumericValue(str.charAt(idx));
            idx++;
        }
        
        return answer;
    }
    
    public String convert(int num){
        if(num/3 == 0){
            return Integer.toString(num%3);
        }
        return Integer.toString(num%3) + convert(num/3);
    }
}

자바 코드로 풀기!

문제 설명

단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다.

재한사항

• s는 길이가 1 이상, 100이하인 스트링입니다.

입출력 예

s       return

문제 푸는 방법:

String의 길이는 s.length()로 메소드를 호출한다.

그리고 인덱스 접근하려면 charAt() 메소드로 접근할 수 있다.

그리고 /는 자동으로 int로 가져온다. %는 나머지이다.

String의 길이를 나누어서 짝수면 가운데 두개, 홀수면 가운데 하나를 가져온다.

정답 코드:

class Solution {
    public String solution(String s) {
        String answer = "";
        if(s.length()%2 == 0){
            answer += s.charAt(s.length()/2-1);
            answer += s.charAt(s.length()/2);
        }else{
            answer += s.charAt(s.length()/2);
        }
        return answer;
    }
}

자바코드로 풀어보았다.!

문제 설명

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일같은 날짜는 주어지지 않습니다)

입출력 예

a      b      result

문제 푸는 방법:

날짜를 다 더해서 7로 나누어주고 나머지에 해당하는 인덱스 0~6을 THU ~ WED로 출력해주면 된다.

배열 정적 할당할 때

String[] temp = {"abc","bcd"}; 이렇게 하면 되는것을 배움.

class Solution {
    public String solution(int a, int b) {
        String answer = "";
        String[] days = {"THU","FRI","SAT","SUN","MON","TUE","WED"};
        int month = 1;
        int day = 0;
        while(month <= a){
            if(month == a){
                day += b;
                //System.out.println(day);
                day %= 7;
                return days[day];
            }
            if(month == 1){
                day += 31;
            }else if(month == 2){
                day += 29;
            }else if(month == 3){
                day += 31;
            }else if(month == 4){
                day += 30;
            }else if(month == 5){
                day += 31;
            }else if(month == 6){
                day += 30;
            }else if(month == 7){
                day += 31;
            }else if(month == 8){
                day += 31;
            }else if(month == 9){
                day += 30;
            }else if(month == 10){
                day += 31;
            }else if(month == 11){
                day += 30;
            }else if(month == 12){
                day += 31;
            }
            month++;
        }
        
        return answer;
    }
}

자바 코드로 풀어보았다.

문제 설명

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

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

제한사항

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

입출력 예

participant        completion        return

입출력 예 설명

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

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

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

문제 푸는 방법:

java string을 비교할 때는 equals를 사용해야한다.

String a;

String b;

a==b <- 주소값끼리 비교

a.equals(b); <- 내용끼리 비교

문제 푸는 방법은 둘다 정렬하고 하나씩 탐색하면서 다르면 return 해주면 된다.

정답 코드:

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Arrays.sort(participant);
        Arrays.sort(completion);
        for(int i=0; i<completion.length; i++){
            //System.out.println("participant: "+ participant[i] + "||" + "completion: "+completion[i]);
            if(!participant[i].equals(completion[i])){
                return participant[i];
            }
        }
        return participant[participant.length-1];
    }
}

자바 코드로 풀어보았다.

문제 설명

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

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

제한사항

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

입출력 예

n       lost       reserve       return

입출력 예 설명

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

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

출처

※ 공지 - 2019년 2월 18일 지문이 리뉴얼되었습니다.
※ 공지 - 2019년 2월 27일, 28일 테스트케이스가 추가되었습니다.

문제 푸는 방법:

다양한 경우를 생각해주어야 한다.

실수할 수 있는 부분이, 뒷 번호 친구에게 빌리는데, 뒷 번호 친구가 잃어버린 친구라면 빌려줄 수 없는 상황이다.

그래서 그것을 고려해서 문제를 풀어주어야 한다.

정답 코드:

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        int answer = n-lost.length;
        int[] students = new int[n];
        Arrays.sort(reserve);
        Arrays.sort(lost);
        ArrayList<Integer> reserve_ = new ArrayList<>();
        ArrayList<Integer> lost_ = new ArrayList<>();
        for(int i: reserve){
            reserve_.add(i);
        }
        for(int i: lost){
            lost_.add(i);
        }
        for(int i=0; i< lost_.size(); i++){
            if(reserve_.contains(lost_.get(i))){
                reserve_.remove(reserve_.indexOf(lost_.get(i)));
                answer++;
            }else{
                if(reserve_.contains(lost_.get(i)-1)){
                    reserve_.remove(reserve_.indexOf(lost_.get(i)-1));
                    answer++;
                    continue;
                }else if(reserve_.contains(lost_.get(i)+1)){
                    if(lost_.contains(lost_.get(i)+1)){
                        continue;
                    }else{
                        reserve_.remove(reserve_.indexOf(lost_.get(i)+1));
                        answer++;
                        continue;
                    }
                }
            }
        }
        return answer;
    }
}