본문 바로가기
알고리즘/알고리즘

[알고리즘] 시간이 없을 때

devWonny 2021. 9. 29. 11:55
해시
정렬
완전탐색
깊이/너비 우선탐색
문자열
맵

 

해시

1) 두개의 배열을 비교

해시맵에 배열1을 양수값 넣는다. 배열2도 음수값으로 넣는다. 값>0 보다 크면 키-값은 불일치하는 키-값이다.
hm.put(키, 값) // 키, 값 넣는다
hm.getOrDefault(키, 기본값) // 값 가져온다
hm.get(키) // 값 가져온다		 import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

        for (String key : hm.keySet()) {
            if (hm.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}
배열 1, 배열2를 오름차순으로 정렬한다.
두 배열 값을 비교한다. arr[i].equals(arr2[i]) 이 일치하지 않을때 배열을 반환한다.
내꺼랑.. 다른점
나는 contains로 확인해서 boolean으로 리턴 받고, 동명이인을 따로 처리해줘야했는데
이거의 경우에는 동명이인도 여러개가 표시되니 따로 작성할 필요가 없다.		 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];
    }
}
     
     

2) 배열 내 값을 비교

코딩테스트 연습
해시
전화번호 목록
https://programmers.co.kr/learn/courses/30/lessons/42577		 배열을 hashMap으로 데이터 변경
여러개가들어있음.containKey(찾고자하는글자)

찾고자하는 글자의 길이만큼



이상한거같은데

아. 자기 자신을 뺴려고 일부로 substring(0,j) 을 쓴거구나 1 11

9 97 976 9767 97674 976742 9767422

1 11 119 1195 11955
119552 1195524
11955244 119552442		 import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        HashMap<String, Integer> map = new HashMap<>();
        
        for(int i =0; i<phone_book.length; i++){
            map.put(phone_book[i],i);
        } // ("119", 0) ("97674223", 1) ("1195524421", 2)
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j < phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    answer = false;
                    return answer;
                }
            }
        }
        
        return answer;
    }
}
코딩테스트 연습
해시
전화번호 목록
https://programmers.co.kr/learn/courses/30/lessons/42577		 "안녕하세요"startsWith("안녕") class Solution {
    public boolean solution(String[] phoneBook) {
       for(int i=0; i<phoneBook.length-1; i++) {
            for(int j=i+1; j<phoneBook.length; j++) {
                if(phoneBook[i].startsWith(phoneBook[j])) {return false;}
                if(phoneBook[j].startsWith(phoneBook[i])) {return false;}
            }
        }
        return true;
    }
}
  String a = "안녕하세요";

System.out.println(a.startsWith("안녕"));// true

System.out.println(a.contains("안녕하"));// true

System.out.println(a.contains("하세"));// true		 import java.util.Arrays;

class Solution {
    public boolean solution(String[] phoneBook) {
        Arrays.sort(phoneBook);
        boolean result = true;
        for (int i=0; i<phoneBook.length-1; i++) {
            if (phoneBook[i+1].contains(phoneBook[i])) {
                result = false;
                break;
            }
        }
        return result;
    }
}
     

 

3) 이중배열

코딩테스트 연습
해시
위장
https://programmers.co.kr/learn/courses/30/lessons/42578		 배열에 있는 값을
map에 쌓아서 

숫자*숫자 -1 
해주면 됨		 import java.util.HashMap; import java.util.Iterator; 
class Solution {
    public int solution(String[][] clothes) {
        int answer = 1; 
        // 1. Create Hash Map 
        HashMap<String, Integer> map = new HashMap<>(); 
        
        // 2. Make count table of each clothing type 
        for(int i = 0; i < clothes.length; i++){
            String key = clothes[i][1]; 
            map.put(key, map.getOrDefault(key, 0) + 1 ); 
        }
        
        // 3. Iterate through all types of clothes and calculate combination 
        Iterator<Integer> it = map.values().iterator(); 
        while(it.hasNext()) {
            answer *= it.next().intValue()+1; 
        } 
        
        // 4. decrease 1 for no clothes case 
        return answer-1; 
    } 
}
코딩테스트 연습
해시
위장
https://programmers.co.kr/learn/courses/30/lessons/42578		 map의 값을 곱하려면
for문과
iterator이 있는데
iterator을 사용함		 import java.util.HashMap; import java.util.Iterator; 
class Solution {
    public int solution(String[][] clothes) {
        int answer =1;
            HashMap<String, Integer> hm = new HashMap<String, Integer>();
            for(int i=0; i<clothes.length; i++){
                String key = clothes[i][1];
                hm.put(key,hm.getOrDefault(key,1)+1);
            }
            //System.out.println(hm.entrySet());// 몇개 있는지 정리
            Iterator<Integer> iter = hm.values().iterator();
            while (iter.hasNext()){
                answer *= iter.next().intValue();
            }
            //System.out.println("result:   "+answer);
           return answer-1;
        }
    }
     
     
     
     
     

Map

코딩테스트 연습
해시
베스트앨범
https://programmers.co.kr/learn/courses/30/lessons/42579		 내가 한거
반복이 많아서 도중 포기

 package com.company;

import java.util.HashMap;
import java.util.Map;

public class programmers5 {

    public static void main(String[] args) {
     //https://programmers.co.kr/learn/courses/30/lessons/42576
        String[] participant = {"mislav", "stanko", "mislav", "ana"};
        String[] completion = {"stanko", "ana", "mislav"};
        String[][] clothes = {{"yellowhat", "headgear"}, {"bluesunglasses", "eyewear"}, {"green_turban", "headgear"}};
        String[] genres = {"classic", "pop", "classic", "classic", "pop"};
        int[] plays = {500, 600, 150, 800, 2500};
        int[] result = Solution.solution(genres, plays);
    }
    static class Solution {
        public static int[] solution(String[] genres, int[] plays) {
            int[] answer = {};
            Map<Integer, String > hm = new HashMap<Integer, String>();
            for(int i=0; i<plays.length; i++){
                hm.put(plays[i], genres[i]);
            }
            System.out.println(hm.entrySet());//[800=classic, 500=classic, 2500=pop, 150=classic, 600=pop]


            // 장르별 play수 합치기
            Map<String, Integer> hm2 = new HashMap<String, Integer>();
            for(int i=0; i<plays.length; i++){
                String key =genres[i];
                hm2.put(key, hm2.getOrDefault(key,0)+plays[i]);
            }
            System.out.println(hm2.entrySet());// [pop=3100, classic=1450]

            int max =0;
            for(int j=0; j<hm2.size(); j++){
                if(max == 0 ){
                    hm2.(j);
                }else if(max < hm2.get(j)){
                    max =hm2.get(j);
                }
            }
            System.out.println(max);



          return answer;
        }
    }
}

코딩테스트 연습
해시
베스트앨범
https://programmers.co.kr/learn/courses/30/lessons/42579		    
     
     

 

반복자

iterator  Iterator iter = list.iterator(); 선언

 while (iter.hasNext()){
체크

String str = iter.next();
값 가져오기		  List<String> list = new ArrayList<>();
 Iterator<String> keys = map.keySet().iterator();
        while( keys.hasNext() ){
            String key = keys.next();
            if(map.get(key) != 0) {
                for(int i = 0; i < map.get(key); i++) {
                    list.add(key);
                }
            } 
        }
 Iterator<String> iter = list.iterator();
        while (iter.hasNext()){
            String str = iter.next();//값 가져오기
            System.out.println(str);
        }
     
     
     

 

정렬


코딩테스트 연습
정렬
K번째수
https://programmers.co.kr/learn/courses/30/lessons/42748		 배열에서

배열 글씨를 자르고
Arrays.copyOfRange(array,start,end);

정렬 후
 Arrays.sort(parsingArray);

n번째 숫자 가져옴		 import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        for(int i=0; i<commands.length; i++){
            int[] temp = commands[i];
            int start = temp[0]-1;
            int end = temp[1];
            int search = temp[2]-1;
            int[] parsingArray = Arrays.copyOfRange(array,start,end);
            Arrays.sort(parsingArray);
            answer[i] = parsingArray[search];
        }
        return answer;
    }
}

코딩테스트 연습
정렬
가장 큰 수
https://programmers.co.kr/learn/courses/30/lessons/42746		 이건 실패

int 나 String은 -> 30, 3 임
그러나 문자를 붙이면
303 은 330보다 작음		 import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";
            String[] string_array = new String[numbers.length];

            for(int i=0; i<numbers.length; i++){
                string_array[i] = String.valueOf(numbers[i]);//int[] -> String[]
            }
            Arrays.sort(string_array, Collections.reverseOrder());//내림 정렬
            if(string_array[0].equals("0")){
                return "0";
            }
        
            for(String s: string_array) answer += s;
            return answer;
    }
}
코딩테스트 연습
정렬
가장 큰 수
https://programmers.co.kr/learn/courses/30/lessons/42746		 int 배열 -> String 배열
 String.valueOf(numbers[i]);


문자를 정렬해야함.
근데 숫자로 sort하는게 아니라
문자로 sort해야함
30, 3 을 sort() 내림차순 하면
int 나 String은 -> 30, 3 임
그러나 문자를 붙이면
303 은 330보다 작음

따라서 compare(a,b)를 오버라딩 한후

(b+a).compareTo(a+b)
기능을 return 하여 정렬해야함.

0이 올때 값을 0으로 해줘야함		 import java.util.*;
class Solution {
    public String solution(int[] numbers) {
        String answer = "";

        String[] str = new String[numbers.length];

        for(int i=0; i<numbers.length; i++){
            str[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(str, new Comparator<String>(){
           @Override
            public int compare(String a, String b){
                return (b+a).compareTo(a+b);
            }
        });

        if(str[0].equals("0")) return "0";

        for(String s :str) answer +=s;

        return answer;
    }
}
코딩테스트 연습
정렬
가장 큰 수
https://programmers.co.kr/learn/courses/30/lessons/42746		 ArrayList 사용

list.add

Collections.sort(list, 함수);

Integer.compare(Integer.parseInt(as + bs), Integer.parseInt(bs + as));
 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;
        }
    }
}
코딩테스트 연습
정렬
H-Index
https://programmers.co.kr/learn/courses/30/lessons/42747		  배열값

 import java.util.*;
class Solution {
    public int solution(int[] citations) {// [3, 0, 6, 1, 5]
        int answer = 0;
        Arrays.sort(citations);// [0, 1, 3, 5, 6]
        for(int i=0; i<citations.length; i++){
            int h = citations.length-i;// 전체길이보다는 작음
            if(citations[i]>=h){
                answer=h;
                break;
            }
        }
        return answer;
    }
}
코딩테스트 연습
정렬
H-Index
https://programmers.co.kr/learn/courses/30/lessons/42747		    

완전탐색

코딩테스트 연습
완전탐색
모의고사
https://programmers.co.kr/learn/courses/30/lessons/42840		 나머지를 사용.
Math.max 두번 사용

list 에 추가

list.get하기		 import java.util.ArrayList;
class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        int[] person1 = {1,2,3,4,5}; //이만큼씩 반복
        int[] person2 = {2,1,2,3,2,4,2,5};
        int[] person3 = {3,3,1,1,2,2,4,4,5,5};
        int answer1=0, answer2 =0, answer3 =0;
        
        for(int i =0; i<answers.length; i++){
            if(person1[i%person1.length] == answers[i]) answer1++;
            if(person2[i%person2.length] == answers[i]) answer2++;
            if(person3[i%person3.length] == answers[i]) answer3++;
        }
        int max = Math.max(Math.max(answer1, answer2),answer3); // max값 구하기
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(max==answer1) list.add(1); //max값이랑 같으면 넣는다.
        if(max==answer2) list.add(2);
        if(max==answer3) list.add(3);
        
        answer = new int[list.size()];
        
        for(int i =0; i<answer.length; i++) {
         answer[i] = list.get(i);
        }
        
        return answer;
    }
}
코딩테스트 연습
완전탐색
소수 찾기
https://programmers.co.kr/learn/courses/30/lessons/42839		    
코딩테스트 연습
완전탐색
카펫
https://programmers.co.kr/learn/courses/30/lessons/42842		 정사각형이라고 생각해

사각형 각 모서리 -4

바깥 사각형의 한줄의 -2 == 내부 사각형의 한줄		 import java.util.Arrays;
class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
            int area = brown+yellow;//10,2 -> 12
            for(int i=1; i<=area; i++){// brown으로 정사각형을 만든다고 생각해라
                // brwon 10개 - 모서리 4개 = 6개
                // 6개 / 사각형 4개의 줄 = 1.5개 가 있어야 정사각형이 됨
                // 한줄에는 1.5 + 2 = 3.5개가 있음 => 4
                int width = i; // 가로 >= 세로
                int height =0;
                if(area%width ==0 ){
                    height = area/width;
                }
                // 카펫 가로 >= 세로 이어야한다.
                if(width < height){
                    continue; //넘어가라
                }

                if((width-2) * (height-2) == yellow){
                    answer[0] = width;
                    answer[1] = height;
                    //System.out.println(Arrays.toString(answer));
                    return answer;
                }
                answer[0] = width;
                answer[1] = height;
            }//for i end
            return answer;
    }
}

코딩테스트 연습
깊이/너비 우선 탐색(DFS/BFS)
타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165		 함수 선언

class 클래스이름{
   static int 공통변수;
   
  public 타입 함수명(){
  }

  public 타입 제출함수명(){
     공통변수 =0;
     함수명();
     return 공통변수;
   }
}// class end

 class Solution {
    static int answer;
    
    // 3. dfs(numbers, target, idx:몇 번째 인덱스인지, sum: idx까지 누적된 값).
    public void dfs(int[] numbers,int target,int idx,int sum){
        // 4. 모든 정수를 탐색했을 때,
        if(idx == numbers.length){   
            // 5. 누적합이 target과 동일하면 answer++ 후 메소드 종료.
            if(sum == target) answer++;
            return;
        }
        
        // 6. 현재 인덱스의 정수를 +로 합해준다.
        sum+=numbers[idx];
        // 7. 다음 인덱스 dfs 수행.
        dfs(numbers,target,idx+1,sum);
        // 8. 6.의 값을 다시 빼준 뒤,
        sum-=numbers[idx];
        // 9. 현재 인덱스의 정수를 -로 합해준다.
        sum+=(-1 * numbers[idx]);
        // 10. 다시 다음 인덱스 dfs 수행.
        dfs(numbers,target,idx+1,sum);
        
    }
    
    public int solution(int[] numbers, int target) {
        // 1. answer은 전역변수로 선언.
        answer = 0;
        
        // 2. dfs수행.
        dfs(numbers,target,0,0);
        
        return answer;
    }
}
     
저작자표시

'알고리즘 > 알고리즘' 카테고리의 다른 글

[프로그래머스] 기능개발  (0) 2021.11.22
[백준] 팩토리얼  (0) 2021.10.14
[프로그래머스][정렬]가장 큰 수  (0) 2021.09.28
[프로그래머스][정렬][k번째 수]  (0) 2021.09.28
[프로그래머스][해시] 완주하지 못한 선수  (0) 2021.09.27

'알고리즘/알고리즘' Related Articles

티스토리툴바