[올리브씨의 알고리즘 입문] Day 9 - 수학, 문자열, 해시, 완전탐색, 조건문

033. 개미 군단 (난이도 : ★☆☆☆☆)

문제 설명.

  개미 군단이 사냥을 나가려고 합니다. 개미군단은 사냥감의 체력에 딱 맞는 병력을 데리고 나가려고 합니다. 장군개미는 5의 공격력을, 병정개미는 3의 공격력을 일개미는 1의 공격력을 가지고 있습니다. 예를 들어 체력 23의 여치를 사냥하려고 할 때, 일개미 23마리를 데리고 가도 되지만, 장군개미 네 마리와 병정개미 한 마리를 데리고 간다면 더 적은 병력으로 사냥할 수 있습니다. 사냥감의 체력 hp가 매개변수로 주어질 때, 사냥감의 체력에 딱 맞게 최소한의 병력을 구성하려면 몇 마리의 개미가 필요한지를 return하도록 solution 함수를 완성해주세요.

 

제한 사항.

• hp는 자연수입니다.
• 0 ≤ hp ≤ 1000

 

입출력 예.

hp	result
23	5
24	6
999	201

---

풀이.

class Solution {
    public int solution(int hp) {
        
        int[] remainArray = {0,1,2,1,2};
        return hp/5 + remainArray[hp%5];
    }
}

class Solution {
    public int solution(int hp) {
    
        // ph를 5로 나눈 나머지 최소 합산 개수는 몫 + {0,1,2,1,2} 가 반복됨
        int[] remainArray = {0,1,2,1,2};
        int answer = hp/5 + remainArray[hp%5];

        return answer;
    }
}

 

다른 풀이.

class Solution {
    public static int solution(int hp) {
        int result = 0;
        int[] ant = {5, 3, 1};
        for (int i = 0; i < ant.length; i++) {
            result += hp / ant[i];
            hp %= ant[i];
        }
        return result;
    }
}

 

MAIN POINTS.

핵심 개발 포인트 / 소감

반복 규칙을 발견하고 배열에 담아 코드를 간소화 한다.

---

034. 모스부호 (1) (난이도 : ★★☆☆☆)

문제 설명.

  머쓱이는 친구에게 모스부호를 이용한 편지를 받았습니다. 그냥은 읽을 수 없어 이를 해독하는 프로그램을 만들려고 합니다. 문자열 letter가 매개변수로 주어질 때, letter를 영어 소문자로 바꾼 문자열을 return 하도록 solution 함수를 완성해보세요.
모스부호는 다음과 같습니다.

morse = { 
    '.-':'a','-...':'b','-.-.':'c','-..':'d','.':'e','..-.':'f',
    '--.':'g','....':'h','..':'i','.---':'j','-.-':'k','.-..':'l',
    '--':'m','-.':'n','---':'o','.--.':'p','--.-':'q','.-.':'r',
    '...':'s','-':'t','..-':'u','...-':'v','.--':'w','-..-':'x',
    '-.--':'y','--..':'z'
}

 

제한 사항.

•   1 ≤ letter의 길이 ≤ 1,000
• return값은 소문자입니다.
• letter의 모스부호는 공백으로 나누어져 있습니다.
• letter에 공백은 연속으로 두 개 이상 존재하지 않습니다.
• 해독할 수 없는 편지는 주어지지 않습니다.
• 편지의 시작과 끝에는 공백이 없습니다.
• a ~ z에 해당하는 모스부호가 순서대로 담긴 배열입니다.
  {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}

 

입출력 예.

letter	result
".... . .-.. .-.. ---"	"hello"
".--. -.-- - .... --- -."	"python"

---

풀이.

import java.util.HashMap;

class Solution {
    public String solution(String letter) {
        
        String answer = "";
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        String[] letterArr = letter.split(" ");
        HashMap<String, Integer> alphabetMap = new HashMap<String, Integer>();
        
        //1.map에 모스부호와 아스키코드 번호 주입
        for(int i=0; i<morse.length ; i++){
            alphabetMap.put(morse[i], i+97);
        }
        
        //2. 매개변수 letter의 해독
        for(int i=0; i<letterArr.length; i++){
            answer += (char)(int)alphabetMap.get(letterArr[i]);
        }
        return answer;
    }
}

 

다른 풀이.

class Solution {
    public String solution(String letter) {
        String answer = "";
        String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        String[] word = letter.split(" ");

        for(int i=0;i<word.length;i++){
            for(int j=0;j<morse.length;j++){
                if(word[i].equals(morse[j])) answer+=(char)(j+97);
            }
        }

        return answer;
    }
}

 

MAIN POINTS.

핵심 개발 포인트 / 소감

---

035. 가위 바위 보 (난이도 : ★☆☆☆☆)

문제 설명.

  가위는 2 바위는 0 보는 5로 표현합니다. 가위 바위 보를 내는 순서대로 나타낸 문자열 rsp가 매개변수로 주어질 때, rsp에 저장된 가위 바위 보를 모두 이기는 경우를 순서대로 나타낸 문자열을 return하도록 solution 함수를 완성해보세요.

 

제한 사항.

• 0 < rsp의 길이 ≤ 100
• rsp와 길이가 같은 문자열을 return 합니다.
• rsp는 숫자 0, 2, 5로 이루어져 있습니다.

 

입출력 예.

rsp	result
"2"	"0"
"205"	"052"

---

풀이.

import java.util.HashMap;
class Solution {
    public String solution(String rsp) {

        String answer = "";

        HashMap<String, String> map = new HashMap<String, String>();
        map.put("2","0");
        map.put("0","5");
        map.put("5","2");

        String[] rspArr = rsp.split("");
        for(int i=0; i<rspArr.length; i++){
            answer += map.get(rspArr[i]);
        }
        return answer;
    }
}

 

다른 풀이.

import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
    public String solution(String rsp) {
        return Arrays.stream(rsp.split("")).map(s -> s.equals("2") ? "0" : s.equals("0") ? "5" : "2").collect(Collectors.joining());
    }
}

 

MAIN POINTS.

핵심 개발 포인트 / 소감
StringBuilder를 사용해서 해결하는 경우도 있음

---

036. 구슬을 나누는 경우의 수 (난이도 : ★★★★☆)

문제 설명.

  머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

 

제한 사항.

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

 

입출력 예.

balls	share	result
3	2	3
5	3	10

---

풀이.

import java.math.*;
class Solution {
    public BigInteger solution(int balls, int share) {
        BigInteger answer = BigInteger.ONE;

        BigInteger a = BigInteger.ONE; //분자 balls!
        BigInteger b = BigInteger.ONE; //분모1 (balls - share)!
        BigInteger c = BigInteger.ONE; //분모2 share!

        if (balls == share){
            return answer = BigInteger.ONE;
        } else {
            for(int i=1; i<=balls; i++){
                a = a.multiply(BigInteger.valueOf(i));
            }
            for(int i=1; i<=(balls-share); i++){
                b = b.multiply(BigInteger.valueOf(i));
            }
            for(int i=1; i<=share; i++){
                c = c.multiply(BigInteger.valueOf(i));
            }
        }
        return answer = a.divide(b.multiply(c));
    }
}

 

다른 풀이.

class Solution {
    public long solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0)
            return 1;

        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }
}

 

MAIN POINTS.

핵심 개발 포인트 / 소감

재귀함수 사용 / BigInteger / Long  등을 사용

 

BigInteger 의 사칙연산 함수

• A.add(B)              A + B       return BigInteger        
• A.substract(B)    A - B       return BigInteger    
• A.multiply(B)       A * B       return BigInteger
• A.divide(B)          A / B       return BigInteger
• A.mod(B)            A % B      return BigInteger 

int -> BigInteger

• 0 = BigInteger.ZERO; 
• 1 = BigInteger.ONE;

BigInteger package in Java

https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html

import java.math.BigInteger;

 

---

출처 :https://school.programmers.co.kr/ 입문 알고리즘

https://school.programmers.co.kr/learn/challenges/beginner?order=acceptance_desc&languages=java