[Algorithm] 5월 31일 알고리즘 연습

Lv. 1 완주하지 못한 선수 - 오래 걸림 (여러 시행착오)

복습할 내용 :

HashMap 사용법 

• containsKey()
• keySet()
• get()
• put()

import java.io.*;
import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String,Integer> dupMap = new HashMap<String,Integer>();

        for(String st : participant){
            //동명이인이 이미 존재한다면
            int num = 0;
            if(dupMap.containsKey(st)){
                num = dupMap.get(st);
            }
            
            dupMap.put(st,num + 1);
        }
        //완주자들 명단 체크
        for(String comp : completion){
            int num = dupMap.get(comp);
            dupMap.put(comp ,num - 1);
        }
        
        for(String str : dupMap.keySet()){
            if(dupMap.get(str) >0){
                answer = str;
            }
        }
        
        return answer;
    }
}

class Runner{
    String name = "";
    public Runner(String myName){
        name = myName;
    }
}

 

 

Lv. 1 K번째수 - 성공

자른 후 정렬하는 것을 안 읽고 넘어감...

인덱스 때문에 많이 시간 까먹음.

import java.util.*;
import java.io.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        
        for(int i = 0; i < commands.length; i++){
            answer[i] = chooseK(array, commands[i]);
        }
        
        return answer;
    }
    
    public int chooseK(int[] arr, int[] order){
        int i = order[0]; //i번째부터 인덱스는 i-1
        int j = order[1]; //j번째까지
        int k = order[2];
        //int[] list = new int[j-i+1];
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for(int index = i-1; index <= j-1 ; index++ ){
            list.add(arr[index]);
        }
        
    
        Collections.sort(list); //뽑은 후 정렬

        return list.get(k-1);
    }
}

 

 

Lv. 1 체육복 - 실패 (탐욕법 문제유형 파악 후 다시 도전)

 

 

 

Lv. 1 [1차] 비밀지도 - 성공 (카카오)

answer 배열 크기 초기화 안 한 실수 주의

StringBuilder초기화 방법 => sb.setLength(0); 을사용

 

import java.util.*;
import java.io.*;

class Solution {
    static StringBuilder sb = new StringBuilder();
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        String[] map1 = new String[arr1.length];
        String[] map2 = new String[arr2.length];
        char[][] map3 = new char[n][n];
        //각 지도 배열 이진법으로 변환
        for(int i = 0 ; i< arr1.length ; i++){
            map1[i] = convertToBinary(n,arr1[i]);
        }
        for(int i = 0 ; i< arr2.length ; i++){
            map2[i] = convertToBinary(n,arr2[i]);
        }
        
        //변환 후
        // 두 맵을 겹쳐서 벽이 하나라도 있다면 1로 변환
        for(int i = 0; i < n; i++){
            for(int j = 0 ; j < n ; j++){
                boolean isWall = false;
                if(j != n-1) {
                    isWall =  map1[i].substring(j, j+1).equals("1") 
                    || map2[i].substring(j, j+1).equals("1");
                }else{// substring이 맨 끝 인덱스인경우 초과하는 예외처리
                    isWall =  map1[i].substring(j).equals("1") 
                    || map2[i].substring(j).equals("1");
                }
                
                char cand = ' ';
                if(isWall) cand = '#'; else cand = ' '; 
                map3[i][j] = cand ; //벽이 있다면 #, 없다면 공백
                
            }
        }
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < n; j++){
                sb.append(map3[i][j]);
            }
            answer[i] = sb.toString();
            sb.setLength(0);
            // sb.append("\n");
        }
        
        
        
        return answer;
    }
    //10진법 -> 2진법 변환
    public String convertToBinary(int n,int num){
        //String s = String.valueOf(num);
        String s = Integer.toBinaryString(num);
        //앞에 0 붙여주기
        while(s.length()<n){
            s = "0"+ s;
        }
        return s;
    }
}

 

 

Lv. 1 [1차] 다트 게임 -실패

 

참고한 풀이

class Solution {
    public int solution(String dartResult) {
        int answer = 0;
        
        String temp = ""; // 문자열 내 1번의 점수 저장 변수
        int arr[] = new int[3]; // 3번의 점수를 저장할 배열
        int idx = 0; // 배열을 참조하기 위한 idx
        
        // 1. dartResult 문자열 탐색.
        for(int i = 0;i<dartResult.length();i++){
            // 1-1. 문자열의 각 문자에 따라 조건 처리.
            switch(dartResult.charAt(i)){
                // 1-2. *인 경우는 자신과 이전의 점수 *2, idx는 S,D,T 처리 후 증가하기 때문에 idx-1, idx-2 후 *2    
                case '*':
                    arr[idx-1]*=2;
                    if(idx >1) arr[idx-2]*=2;
                    break;
                // 1-3. #은 자신의 점수를 음수로 만든다.                 
                case '#':
                    arr[idx-1]*=-1;
                    break;
                // 1-4. S는 1제곱, 다음 점수를 위해 idx를 증가시키고 정수를 저장하는 temp를 초기화.    
                case 'S':
                    arr[idx] = (int)Math.pow(Integer.parseInt(temp),1);
                    idx++;
                    temp ="";
                    break;
                // 1-5. D는 2제곱, 다음 점수를 위해 idx를 증가시키고 정수를 저장하는 temp를 초기화.    
                case 'D':
                    arr[idx] = (int)Math.pow(Integer.parseInt(temp),2);
                    idx++;
                    temp ="";
                    break;
                // 1-6. T는 3제곱, 다음 점수를 위해 idx를 증가시키고 정수를 저장하는 temp를 초기화.                   
                case 'T':
                    arr[idx] = (int)Math.pow(Integer.parseInt(temp),3);
                    idx++;
                    temp ="";
                    break;
                // 1-7. 그 외의 정수들은 temp 변수에 저장해 둔다.    
                default:
                    temp+=String.valueOf(dartResult.charAt(i));
                    break;                    
            } 
        }
        
        // 2. 위 과정을 통해 구한 각 횟수의 점수를 모두 더하면 정답.
        for(int i =0;i<arr.length;i++){
            answer+=arr[i];
        }
        
        return answer;
    }
}

 

 

https://fbtmdwhd33.tistory.com/216

[프로그래머스,Level 1] 다트 게임(JAVA 구현)

 

 

Lv. 1 실패율(카카오)

 

복습할 내용 :

객체를 정렬하는 법.(comparable)

other.객체 - 객체 -> 내림차.

객체- other.객체 -> 오름차.

Double 비교 compare(d1, d2)

if (Double.compare(d1, d2) == 0) {
    System.out.println("d1 == d2");

} else if (Double.compare(d1, d2) > 0) {
    System.out.println("d1 > d2");

} else {
    System.out.println("d1 < d2");

}

 

정확도 70%에서 멈춰있었는데 원인은 아래와 같음.

import java.util.*;
import java.io.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        
        int memberSize = stages.length;
        int[] challengeCount = new int[N+2]; //각 1~N단계 도전한 사람.
        double[] failPro = new double[N+2]; //1단계~ N단계,그리고 완주(N+1)까지 각 실패횟수
        for(int i = 0; i < memberSize ; i++){
            failPro[stages[i]]++;
            for(int j = 1; j <= stages[i]; j++){ 
                
                challengeCount[j]++;
                
            }
        }
        
        for(int i = 1; i < N+1; i++){
            double failCount = failPro[i];
            //정확도 70% 원인 분모가 0인경우를 생각 안 함. 도전을 한 번도 못한경우.
            if(challengeCount[i] == 0){
                failPro[i] = 0; 
                continue;
            }
            failPro[i] = failCount/challengeCount[i];
        }
 
        //failPro가 높을 수록 실패율이 높다.(x)-> 도전한 사람들로 나누어주어야함.
        //실패율이 높은 것부터 나열(내림차)
        
        //어떻게 정렬하지? -> 객체로 만들어서 정렬
        StageFail[] arr = new StageFail[N]; //1~N단계까지의 실패기록 객체
        for(int i = 0; i < N ; i++){
            arr[i] = new StageFail(i+1, failPro[i+1]); //i+1단계, 실패 카운트
            
        }
        Arrays.sort(arr);
        for(int i = 0; i < N ; i++){
            answer[i] = arr[i].stageNumber;
        }
        
        
        return answer;
    }
}

class StageFail implements Comparable<StageFail>{
    public double failCount;
    public int stageNumber;
    
    public StageFail(int sn,double fc){
        failCount = fc;
        stageNumber = sn;
    }
    
    @Override
    public int compareTo(StageFail other){
        if( other.failCount != failCount)
        return Double.compare(other.failCount, failCount); //내림차
        if(other.failCount == failCount){
            return stageNumber - other.stageNumber; 
        }
        return 0;
    }
    
}