개발자로 살아남기

오른쪽으로 가는것을 기준으로 잡고 풀었다. 좌, 우 이동만 가지고 얘기하자면, 현재 위치를 기준으로 왼쪽/오른쪽 거리를 계산했을 때, 한 번이라도 왼쪽 거리가 짧을 경우 name의 끝에서부터 빼면서 계산했다. 다른 사람의 풀이를 보면 엄청 쉽게 구현하던데 신기하다...

탐욕법은 매 순간마다 최적의 값을 찾는다. 탐욕법은 탐욕스러운 선택 조건과 최적 부분 구조 조건을 가지는 특징이 있는데, 탐욕스러운 선택 조건은 앞에서 내가 선택한 것이 이후의 선택에 어떠한 영향을 미치지 않는다는 조건이고 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다는 특징이 있다. 

이 문제에서는 인덱스 0 위치에서 왼쪽으로 갈 경우 문자열의 끝에 갈 수 있지만 문자열의 끝에서 오른쪽으로 갈 경우 인덱스 0위치로 갈 수 없다. 그래서 아래와 같은 결과가 나오게 된다.

ABAAAABAAAAAAAAAAAAB => 최적해 (13) / 실제 계산한 해 (19)

탐욕법 자체가 이미 지나온 길을 되돌아갈 수 없다고 하면 탐욕법이 맞는거 같기도하고.. 아리송하다.

public int solution(String name) {
    int answer = 0;
    int notA_Count = 0;
    int curCount = 0;
    int lastIndex = 0;
    char curChar = 'A';
    boolean leftSmallerThanRight = false;

    // A가 아닌 개수 및 A가 아닌 마지막 인덱스 구하기
    for(int i=0; i<name.length(); i++){
        if (name.charAt(i) != 'A'){
            lastIndex = i;
            notA_Count++;
        }
    }

    // 오른쪽으로 갈 수 있는 최대 구하기
    // 인덱스 0을 기준으로 왼쪽으로 갔을 때 몇번째 값이 A가 아닌지 확인 (0의 위치에서 왼쪽으로 갈 경우 거리값이 +1이 되어야 함)
    int leftCount = name.length() - lastIndex;
    int rightCount = 0;
    int curPos = 0;
    int upDownCount = 0;
    for(int i=0; i<name.length(); i++){
        curChar = name.charAt(i);
        if (curChar == 'A'){
            continue;
        }

        // i 위치에서 현재 위치를 빼면 오른쪽으로 몇 번 가야 A가 아닌 문자가 나오는지 알 수 있음
        rightCount = i - curPos;

        // A가 아닌 문자를 만나기 위해 오른쪽으로 간 횟수와 왼쪽으로 간 횟수를 비교
        // 왼쪽으로 간 횟수가 더 적을 경우 빠져나와 맨 오른쪽에서 왼쪽으로 진행하기 위해 빠져나옴
        if (rightCount > leftCount + curPos){
            leftSmallerThanRight = true;
            break;
        }
        else{
            answer += rightCount;
        }

        // 알파벳 구하기
        upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
        answer += upDownCount;

        // 현재 위치를 i번째로 옮김
        curPos = i;
        rightCount = 0;
        curCount++;
    }

    // 현재 위치에서 왼쪽으로 가는게 더 빠른 경우가 있을 때
    // 현재 위치부터 왼쪽으로 구해야 하니까 leftCount는 curPos 값으로 변경
    leftCount = curPos;
    if (leftSmallerThanRight){
        for(int i=name.length() - 1; i>=0; i--){
            if (notA_Count == curCount){
                break;
            }

            curChar = name.charAt(i);
            // A면 한 칸 이동
            if (curChar == 'A'){
                leftCount++;
                continue;
            }
            leftCount++;

            upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
            answer += upDownCount;
            answer += leftCount;
            leftCount = 0;
            curCount++;
        }
    }

    return answer;
}

프로그래머스 Level 2의 전화번호 목록을 풀었다. Hash를 이용하라는데, 아무리봐도 안될 것 같아 그냥 이중 for문으로 작성했다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=i + 1; j<phone_book.length; j++){
                if (phone_book[j].indexOf(phone_book[i]) == 0){
                    return false;
                }
                else{
                    break;
                }
            }
        }

        return true;
    }
}

Arrays.sort 를 한 이유는 String을 정렬하면 사전순으로 정렬되기 때문이다. 생각해보니 for문 한 번으로도 될 것 같다. 위와 같이 풀었을 때의 테스트 결과이다.

다른 사람들의 풀이를 보니까 나처럼 푼 사람도 있었고 문제에서 얘기한 HashMap을 사용한 사람도 있었다. 아래는 HashMap을 사용한 사람의 코드이다. 

public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashMap<String,Integer> h =new HashMap<>();
        for(String s : phone_book) {
            h.put(s, h.getOrDefault(s,0)+1);
        }

        for(String s : phone_book) {
            for(int j=1; j<s.length(); j++) {
                if(h.containsKey(s.substring(0,j))) {
                   answer = false; 
                   break;
                }              
            }
        }    



        return answer;
    }

phone_book 배열에서 문자열을 가져와 하나씩 잘라가면서 HashMap에 잘라진 문자열이 키로 존재하는지 확인하고 있다면 false를 반환하는 코드이다. 아래는 위 코드로 실행했을 때의 테스트 결과이다.

확실히 글자수가 적거나 개수가 적을 경우에는 HashMap을 이용하면 상당히 빠른 것 같다. 그런데 굳이 HashMap을 사용할 필요가 있을까 싶은 문제였다..

이 문제를 푸는데 시간이 좀 걸렸다. 

문제는 위와 같은데 단순히 10진수를 124 나라에서 사용하는 숫자로 바꾸는 문제이다. 1,2,4 세 개만 사용한다 했으니 10진수를 3진법으로 변환해봤다. 

그리고 3진법과 124나라의 숫자를 비교해봤다.

10진수 6을 3진법으로 변환 시 20이 되는데 이 20는 결국 124 나라의 14라는 숫자가 되어야 한다. 3진법에 의해 10진수 6이 3진수 20이 되었으니 결국 3진법으로 표현하면 13이 될 수 있다는 뜻이다. (3진수 13은 결국 3진수 20이 되므로) 이렇게 되면 3진수 20에서 2는 1이 되어야 하므로 -1 해주고 0은 3으로 바꿔야 한다. 하지만 124 나라에서는 1, 2, 4만 사용하기 때문에 결국 0은 4로 바꿔줘야 124 나라의 숫자가 된다. 

풀이순서

 1. 전달받은 숫자를 3으로 나눈다.

 2. 나머지가 0일 경우 4로 치환하고 몫을 -1 하고 나머지 값을 추가한다.

   2-1. 나머지가 0이 아닐 경우 그대로 값을 추가한다.

 3. 1번과 2번을 반복해서 숫자가 0이 될 때까지 반복한다. 

public String solution(int n) {
    StringBuilder sb = new StringBuilder();
    int rest = 0;

    while(n > 0){
        rest = n % 3;
        n /= 3;
        if (rest == 0){
            n -= 1;
            rest = 4;
        }

        sb.insert(0, rest);
    }

    return sb.toString();
}

해당 문제를 푸는데 좀 많은 시간이 소요되었다. 먼저 문제를 살펴보면 아래와 같다.

즉, 8 x 12에서 흰색칸을 모두 지운 80이라는 값이 반환이 되어야 한다.

먼저 아래처럼 패턴을 나누었다. 패턴을 나누는 기준은 연속되지 않은 흰색 칸을 기준으로 했다.

그럼 패턴이 총 4개가 나오게 된다. 패턴의 길이는 가로 2, 세로 3인데, 이 값들은 가로와 세로를 각각 4로 나눈값이 된다. 하나 더 예시로 작성해 보았다. 

사용 못하는 칸이 모두 연속되어 있으므로 패턴이 1개이고 패턴의 길이는 가로 4, 세로 3이 된다. 패턴의 길이와 총 길이가 같으므로 패턴의 가로와 세로는 각각 1로 나눈 값과 동일하다. 이렇게 5x3, 6x4 등등의 길이의 종이를 위와 같은 방법으로 구해보았다. 

그 결과, 각 패턴의 길이는 종이의 가로, 세로값을 최대공약수로 나눈 값이 되며 패턴의 개수는 최대공약수의 값과 동일하다는 결론이 나왔다. 다시 위에 문제로 돌아가 패턴을 살펴보면,

패턴의 가로는 2, 세로는 3이 되는데 여기서 사용할 수 없는 칸은 총 4칸이다. 이 값 또한 가로와 세로를 더한 후 -1을 해주면 된다. 그 이유는 아래와 같다.

그림에서 볼 수 있듯이 3번을 위로, 4번을 왼쪽으로 붙이게 되면 패턴의 가로 + 세로 - 1 이 되기 때문에 사용하지 못하는 개수는 총 4개이다. 위에서 4x3 패턴의 예시도 동일하게 아래 그림처럼 가능하다. 

3, 5번을 왼쪽으로 붙이고 4, 6번을 위로 붙이게 되면 4 + 3 - 1 만큼의 개수를 사용하지 못하게 된다. 

위 내용을 코드로 작성하여 제출했다.

https://github.com/banjjak2/Programmers/blob/main/Level2/%EB%A9%80%EC%A9%A1%ED%95%9C_%EC%82%AC%EA%B0%81%ED%98%95.java

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        long totalCount = (long)w * h;
        // 패턴 총 개수
        int patternCount = gcd(w, h);

        // 1패턴당 가로 개수
        int widthPerPattern = w / patternCount;
        // 1패턴당 세로 개수
        int heightPerPattern = h / patternCount;
        // 1패턴당 못쓰는 개수
        int unusedCountPerPattern = widthPerPattern + heightPerPattern - 1;

        // 총개수 - (1패턴당 못쓰는 개수 * 패턴 총 개수);
        answer = totalCount - (unusedCountPerPattern * patternCount);
        return answer;
    }

    // 최대공약수 구하기
    public int gcd(int n, int m){
        // 나머지가 0이면
        if (m == 0){
            // 나눈값 반환
            return n;
        }

        // 나눈 수, 나머지 값
        return gcd(m, n % m);
    }
}

[Level 2] 단체사진 찍기 (Java)

프로그래머스의 Level2 문제인 단체사진 찍기를 풀었다. 나같은 경우 해당 문제를 아래와 같이 풀었었다.

1. 알파벳 8자리에서 나올 수 있는 모든 경우의 수를 모두 구한다. (8! = 40320)
2. 구한 경우의 수들을 조건에 맞는지 확인 후 조건에 만족할 경우 +1 해준다.

import java.util.*;

public class 단체사진_찍기 {
    public static void main(String[] args) {
        int n = 0;
        // String[] data = {
        //     "N~F=0", 
        //     "R~T>2"
        // };

        String[] data = {
            "M~C<2", 
            "C~M>1"
        };

        System.out.println(solution(n, data));
    }

    
    static char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public static int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0);
        for (String cs : createFriendsRowList) {
            if (checkCondition(cs, data)){
                answer++;
            }
        }
        return answer;
    }

    static boolean[] visited = new boolean[8];
    static List<String> createFriendsRowList = new ArrayList<String>();
    static char[] createFriendsRowArray = new char[8];
    public static void createAllFriendsRow(int index){
        if (index == visited.length){
            createFriendsRowList.add(String.valueOf(createFriendsRowArray));
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1);
                    visited[i] = false;
                }
            }
        }
    }

    public static boolean checkCondition(String friendsArray, String[] data){
        String[] splits;
        String startFriend, endFriend;
        String condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            splits = c.split("");

            startFriend = splits[0];
            endFriend = splits[2];
            condition = splits[3];
            gap = Integer.parseInt(splits[4]);

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case "=":
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case ">":
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case "<":
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

그 결과...

8.6초라는 어마어마한 성능을 가지고 있었다;

8! 만큼 2번 (프렌즈의 모든 경우의 수 구할 때, 조건에 맞는지 구할 때)을 돌아서 성능이 저렇게 나온건지 해서 아래와 같이 수정했었다.

1. 모든 경우의 수를 구함과 동시에 조건에 맞는지 확인한다.
2. 조건에 맞다면 +1 해준다.

위와 같이 작성해봐도 동일하게 8초 이상이 출력되었다. 그래서 다시 확인한 결과 checkCondition 함수에서 split 메소드로 문자열을 자르는 부분이 있었는데, 이 부분을 split 대신 charAt 메소드를 사용하여 구현해 보았다.

class Solution {
    char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0, data);
        answer = correctCount;
        return answer;
    }

    boolean[] visited = new boolean[8];
    char[] createFriendsRowArray = new char[8];
    int correctCount = 0;
    public void createAllFriendsRow(int index, String[] data){
        if (index == visited.length){
            if (checkCondition(String.valueOf(createFriendsRowArray), data)){
                correctCount++;
            }
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1, data);
                    visited[i] = false;
                }
            }
        }
    }

    public boolean checkCondition(String friendsArray, String[] data){
        char startFriend, endFriend;
        char condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            startFriend = c.charAt(0);
            endFriend = c.charAt(2);
            condition = c.charAt(3);
            gap = c.charAt(4) - '0';

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case '=':
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case '>':
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case '<':
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

위와 같이 작성 한 후 다시 제출했더니 아래와 같은 결과가 나왔다.

속도와 메모리가 9배 이상 차이가 남을 확인할 수 있었다. 

결론.

  - split 대신 charAt을 사용할 수 있는 경우 charAt을 사용하는 것이 성능상에 유리하다. 

# Programmers

알고리즘 문제풀이

# LEVEL 1

신규아이디추천 (21. 07. 13)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%8B%A0%EA%B7%9C%EC%95%84%EC%9D%B4%EB%94%94%EC%B6%94%EC%B2%9C.java

- 정규표현식 이용해서 각 스텝별로 구현

(https://banjjak1.tistory.com/8)

------------------------------------------------------------------------------------------

키패드누르기 (21. 07. 18)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%82%A4%ED%8C%A8%EB%93%9C%EB%88%84%EB%A5%B4%EA%B8%B0.java

- 키패드 위치를 class로 추출하여 관리 및 알기 쉽게 작성

- 두 점 사이의 거리 구하기 공식을 이용하여 최단거리 구현

(https://banjjak1.tistory.com/9)

------------------------------------------------------------------------------------------

음양더하기 (21. 07. 25)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9D%8C%EC%96%91%EB%8D%94%ED%95%98%EA%B8%B0.java

- 음수의 경우 절대값을 취해 결과값 반환

------------------------------------------------------------------------------------------

완주하지못한선수 (21. 07. 31)

https://banjjak1.tistory.com/12

sort 메소드 이용 : https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_sort.java

- Arrays.sort 메소드를 이용해 String 배열을 정렬 후 비교

- Arrays.sort 메소드에서 String 정렬 시 알파벳 순으로 정렬하기 때문

HashMap 이용 : https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_hash.java

- sort 메소드를 이용했을 때 속도가 느려진 관계로 hash로 구현해서 테스트 진행

- HashMap을 이용하여 각 선수들의 이름을 Key로 두고 참가자라면 +1, 참가자 중 완주자라면 -1을 하여

0이 아닌 선수가 있을 경우 entrySet 메소드를 이용해 해당 (미완주자)Key 값을 반환

sort 메소드의 경우 내부적으로 TimSort 알고리즘을 사용하는데 Merge Sort 알고리즘을 기반으로 작성되었고,

Insertion Sort와 merge Sort 알고리즘의 결합 형태라고 한다.

HashMap의 경우 키 값을 알면 바로 Value 값을 알 수 있기 때문에 속도면에서 빠르다.

------------------------------------------------------------------------------------------

위클리챌린지_1주차 (21. 08. 03)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9C%84%ED%81%B4%EB%A6%AC%EC%B1%8C%EB%A6%B0%EC%A7%80_1%EC%A3%BC%EC%B0%A8.java

- 모자른 돈을 구하는 문제인데, 결과값이 음수가 나올 경우 모자른 돈이 되므로 *-1 을 취해 양수로 만들어 반환

------------------------------------------------------------------------------------------

위클리챌린지_2주차 (21. 08. 10)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9C%84%ED%81%B4%EB%A6%AC%EC%B1%8C%EB%A6%B0%EC%A7%80_2%EC%A3%BC%EC%B0%A8.java

- 학점을 계산하는 문제로, 유일한 값인지 판별 후 점수 계산 및 학점 계산

- String을 이용하여 단순히 연결했지만 성능상 문제가 있어 StringBuilder로 변경 후 테스트 진행

- 빈번한 문자열 연결시 StringBuilder나 StringBuffer를 이용해야 함

https://banjjak1.tistory.com/15

------------------------------------------------------------------------------------------

체육복 (21. 08. 14)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%B2%B4%EC%9C%A1%EB%B3%B5.java

- 탐욕 알고리즘을 이용한 문제 (현재 상황에서 제일 최선의 선택을 하는 알고리즘)

- 도난당한 사람의 번호와 여분을 가지고 있는 사람의 번호를 정렬

- 여벌 체육복을 가져온 학생이 도난당할 경우를 먼저 계산

- 여분 체육복을 가지고 있는 사람의 앞/뒤 번호가 도난당했는지 확인 후 계산

------------------------------------------------------------------------------------------

K번째 수 (21. 08. 14)

sort 메소드 사용 : https://github.com/banjjak2/Programmers/blob/main/Level1/K%EB%B2%88%EC%A7%B8%EC%88%98_sort%EB%A9%94%EC%86%8C%EB%93%9C%EC%9D%B4%EC%9A%A9.java

sort 메소드 구현 : X

Arrays.sort 메소드 사용 시 성능이 저하되는 문제가 있음. sort 방법을 변경해서 테스트 예정

------------------------------------------------------------------------------------------

숫자 문자열과 영단어 (21. 08. 14)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%88%AB%EC%9E%90_%EB%AC%B8%EC%9E%90%EC%97%B4%EA%B3%BC_%EC%98%81%EB%8B%A8%EC%96%B4.java

- HashMap을 이용하여 Key, Value로 문제풀이 진행

------------------------------------------------------------------------------------------

로또의 최고 순위와 최저 순위 (21. 08. 15)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%A1%9C%EB%98%90%EC%9D%98_%EC%B5%9C%EA%B3%A0_%EC%88%9C%EC%9C%84%EC%99%80_%EC%B5%9C%EC%A0%80_%EC%88%9C%EC%9C%84.java

- 전달받은 lottos 배열에서 0(알 수 없는 번호)일 경우 카운트 증가

- win_nums 배열에 있는 값이 lottos 배열에 있다면 correctCount 증가

- 최고 순위는 알 수 없는 번호 모두 당첨번호일 때 이므로 correctCount 값에 + 0일 경우의 카운트 값

- 최저 순위는 알 수 없느 번호 모두 낙첨번호일 때 이므로 correctCount 값

- correctCount 값으로 순위 반환

------------------------------------------------------------------------------------------

크레인 인형뽑기 게임 (21. 08. 16)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%81%AC%EB%A0%88%EC%9D%B8_%EC%9D%B8%ED%98%95%EB%BD%91%EA%B8%B0_%EA%B2%8C%EC%9E%84.java

- 크레인이 잡아서 뽑을 경우 Stack에 데이터 push

- 방금 뽑은 카카오 캐릭터가 제일 마지막에 뽑은 캐릭터 값과 같을 경우 pop

- 동일 캐릭터가 2개일 때 터지므로 pop 할때마다 +2씩 증가

------------------------------------------------------------------------------------------

폰켓몬 (21. 08. 16)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%8F%B0%EC%BC%93%EB%AA%AC.java

- HashSet을 이용하여 nums 중복 제거

- 중복제거한 데이터의 길이가 nums 개수의 반절보다 작을 경우 최대 선택 가능한 종류 개수이므로

중복제거한 데이터의 길이를 반환

- nums 데이터 길이의 절반이 중복제거한 데이터의 길이보다 더 클 경우 최대 선택 가능한 종류 개수가 데이터 반절의 길이이므로

데이터 반절의 길이를 반환

------------------------------------------------------------------------------------------

소수 만들기 (21. 08. 22)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%86%8C%EC%88%98_%EB%A7%8C%EB%93%A4%EA%B8%B0.java

- 조합을 이용하여 구현

------------------------------------------------------------------------------------------

모의고사 (21. 08. 24)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC.java

- 수포자 1, 2, 3이 맞은 정답 개수를 correctCount 배열에 넣고 배열 중 최대값을 구하여 동일한 값이 몇 개인지 판별 후 해당 수포자 번호 반환

------------------------------------------------------------------------------------------

<span style="color:red">실패율 (21. 08. 24) - 재풀이</span>

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%8B%A4%ED%8C%A8%EC%9C%A8.java

- HashMap을 이용해서 풀이

- 다른 풀이에 비해 속도면에서 성능이 안좋음. 원인파악 후 재풀이 예정

------------------------------------------------------------------------------------------

3진법 뒤집기 (21. 08. 25)

https://github.com/banjjak2/Programmers/blob/main/Level1/_3%EC%A7%84%EB%B2%95_%EB%92%A4%EC%A7%91%EA%B8%B0.java

- StringBuilder와 거듭제곱 기능으로 해결

------------------------------------------------------------------------------------------

두 개 뽑아서 더하기 (21. 08. 25)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%91%90_%EA%B0%9C_%EB%BD%91%EC%95%84%EC%84%9C_%EB%8D%94%ED%95%98%EA%B8%B0.java

- 조합을 이용해 해결

------------------------------------------------------------------------------------------

약수의 개수와 덧셈 (21. 08. 25)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%95%BD%EC%88%98%EC%9D%98_%EA%B0%9C%EC%88%98%EC%99%80_%EB%8D%A7%EC%85%88.java

- 약수의 개수를 구한 후 더함

------------------------------------------------------------------------------------------

예산 (21. 08. 25)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%98%88%EC%82%B0.java

- 신청금액을 sort 한 후 신청금액 배열의 앞에서부터 빼서 해결

------------------------------------------------------------------------------------------

1차 비밀지도 (21. 08. 27)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%B9%84%EB%B0%80%EC%A7%80%EB%8F%84_1%EC%B0%A8.java

- arr1과 arr2의 각 데이터들을 비트연산(OR) 후 결과값을 가지고 2진화하여 0이면 " ", 1이면 "#"으로 추가

------------------------------------------------------------------------------------------

가운데 글자 가져오기 (21. 08. 27)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EA%B0%80%EC%9A%B4%EB%8D%B0_%EA%B8%80%EC%9E%90_%EA%B0%80%EC%A0%B8%EC%98%A4%EA%B8%B0.java

- substring 메소드 이용

------------------------------------------------------------------------------------------

다트게임 1차 (21. 08. 28)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%8B%A4%ED%8A%B8%EA%B2%8C%EC%9E%84_1%EC%B0%A8.java

- 문자열에서 char값을 하나씩 가져오면서 switch 문으로 값 판단

------------------------------------------------------------------------------------------

같은 숫자는 싫어 (21. 08. 29)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EA%B0%99%EC%9D%80_%EC%88%AB%EC%9E%90%EB%8A%94_%EC%8B%AB%EC%96%B4.java

- 현재값과 이전값을 비교하여 다르면 List에 추가

- 완성된 List를 배열로 변환

------------------------------------------------------------------------------------------

나누어 떨어지는 숫자 배열 (21. 08. 29)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%82%98%EB%88%84%EC%96%B4_%EB%96%A8%EC%96%B4%EC%A7%80%EB%8A%94_%EC%88%AB%EC%9E%90_%EB%B0%B0%EC%97%B4.java

- divisor로 나누어지는 값을 리스트에 저장

- 리스트값을 하나씩 가져와 Collections.sort 메소드로 정렬 후 다시 배열로 반환

------------------------------------------------------------------------------------------

두 정수 사이의 합 (21. 08. 29)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%91%90_%EC%A0%95%EC%88%98_%EC%82%AC%EC%9D%B4%EC%9D%98_%ED%95%A9.java

- 전달받을 a, b에는 대소관계가 정해지지 않아 대소판단 후 사이값들의 총합을 구함

------------------------------------------------------------------------------------------

문자열 내 마음대로 정렬하기 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AC%B8%EC%9E%90%EC%97%B4_%EB%82%B4_%EB%A7%88%EC%9D%8C%EB%8C%80%EB%A1%9C_%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0.java

- 먼저 사전순으로 정렬한 후 특정 문자를 기준으로 정렬

- 사전순으로 먼저 정렬하면 특정 문자를 기준으로 정렬할 때 동일한 문자가 있어도 사전순으로 정렬됨

------------------------------------------------------------------------------------------

문자열 내 p와 y의 개수 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AC%B8%EC%9E%90%EC%97%B4_%EB%82%B4_p%EC%99%80_y%EC%9D%98_%EA%B0%9C%EC%88%98.java

- 문자열을 소문자로 변환 후 p, y 비교

------------------------------------------------------------------------------------------

문자열 내림차순으로 배치하기 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AC%B8%EC%9E%90%EC%97%B4_%EB%82%B4%EB%A6%BC%EC%B0%A8%EC%88%9C%EC%9C%BC%EB%A1%9C_%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0.java

- String을 char배열로 변환 후 StringBuilder를 이용해 문자열을 붙여넣어 반환

------------------------------------------------------------------------------------------

문자열 다루기 기본 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AC%B8%EC%9E%90%EC%97%B4_%EB%8B%A4%EB%A3%A8%EA%B8%B0_%EA%B8%B0%EB%B3%B8.java

- 정규표현식으로 문제풀이 진행

------------------------------------------------------------------------------------------

서울에서 김서방 찾기 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%84%9C%EC%9A%B8%EC%97%90%EC%84%9C_%EA%B9%80%EC%84%9C%EB%B0%A9_%EC%B0%BE%EA%B8%B0.java

- 배열을 하나씩 돌면서 Kim을 찾은 후 인덱스를 반환

------------------------------------------------------------------------------------------

소수 찾기 (21. 08. 30)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%86%8C%EC%88%98_%EC%B0%BE%EA%B8%B0.java

https://banjjak1.tistory.com/17

- "에라토스테네스의 체"를 이용하여 소수 판별

- 큰 수가 소수인지 판별하는 방법으로, 2의 배수부터 지우고(자기자신 제외) 다음 숫자 3의 배수를 지우며(자기자신 제외) 이미 지워진 숫자에 접근한 경우 다음 숫자로 넘어가도록 함

------------------------------------------------------------------------------------------

수박수박수박수박수박수 (21. 08. 31)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%88%98%EB%B0%95%EC%88%98%EB%B0%95%EC%88%98%EB%B0%95%EC%88%98%EB%B0%95%EC%88%98%EB%B0%95%EC%88%98.java

- 나머지 연산으로 판단 후 문자열 조합하여 리턴

------------------------------------------------------------------------------------------

문자열을 정수로 바꾸기 (21. 08. 31)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EB%AC%B8%EC%9E%90%EC%97%B4%EC%9D%84_%EC%A0%95%EC%88%98%EB%A1%9C_%EB%B0%94%EA%BE%B8%EA%B8%B0.java

- Integer.parseInt 메소드로 숫자 리턴

- 웬만하면 java에서 제공하는 메소드보단 직접 구현해서 해보기

------------------------------------------------------------------------------------------

시저암호 (21. 08. 31)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%8B%9C%EC%A0%80_%EC%95%94%ED%98%B8.java

- String에서 문자를 하나씩 가져와 n만큼 이동한 값이 'z'보다 크면 문자+n 에서 'z'를 뺀다.

그럼 'a'에서 얼만큼 더 가야하는지에 대한 값이 나오므로 문자'a'에 앞서 구한 값을 더하고 -1을 해주면 n만큼 이동한 값이 나온다.

대문자 'Z'도 마찬가지로 가능하다.

------------------------------------------------------------------------------------------

약수의 합 (21. 09. 01)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%95%BD%EC%88%98%EC%9D%98_%ED%95%A9.java

https://banjjak1.tistory.com/18

- 약수는 전달받은 숫자/2 보다 클 수 없으므로 for문 조건에 n/2를 해주어야 함

- 위 생각을 못하고 단순하게 작성..

------------------------------------------------------------------------------------------

이상한 문자 만들기 (21. 09. 01)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9D%B4%EC%83%81%ED%95%9C_%EB%AC%B8%EC%9E%90_%EB%A7%8C%EB%93%A4%EA%B8%B0.java

- 짝수번째인 경우 대문자로 변환

- 홀수번째인 경우 소문자로 변환

- toLowerCase(), toUpperCase() 메소드 이용하지 않고 알파벳 범위 정해서 구현

------------------------------------------------------------------------------------------

자릿수 더하기 (21. 09. 01)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9E%90%EB%A6%BF%EC%88%98_%EB%8D%94%ED%95%98%EA%B8%B0.java

- 단순히 각 자리수를 더하는 것이기 때문에 나머지 연산과 나누기 연산을 이용해서 빠르게 풀 수 있었으나

생각하지 못해서 문자열로 변환 후 다시 숫자로 반환..

- 반성하자

------------------------------------------------------------------------------------------

자연수 뒤집어 배열로 만들기 (21. 09. 01)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9E%90%EC%97%B0%EC%88%98_%EB%92%A4%EC%A7%91%EC%96%B4_%EB%B0%B0%EC%97%B4%EB%A1%9C_%EB%A7%8C%EB%93%A4%EA%B8%B0.java

- answer의 배열 길이를 정해주고 반복문을 통해 나머지 연산과 나누기 연산을 이용해 배열에 저장

------------------------------------------------------------------------------------------

최대공약수와 최소공배수 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80_%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98.java

- 소인수분해를 이용한 풀이와 유클리드 호제법을 이용한 풀이 둘 다 작성

------------------------------------------------------------------------------------------

콜라츠 추측 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%BD%9C%EB%9D%BC%EC%B8%A0_%EC%B6%94%EC%B8%A1.java

- 짝수면 /2, 홀수면 *3 후 + 1

------------------------------------------------------------------------------------------

평균 구하기 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%8F%89%EA%B7%A0_%EA%B5%AC%ED%95%98%EA%B8%B0.java

- 배열의 모든값을 더해서 평균을 반환

------------------------------------------------------------------------------------------

하샤드 수 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%95%98%EC%83%A4%EB%93%9C_%EC%88%98.java

- 나머지 연산을 통해 각 자리의 숫자를 더해주고 하샤드 수인지 계산

------------------------------------------------------------------------------------------

핸드폰 번호 가리기 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%95%B8%EB%93%9C%ED%8F%B0_%EB%B2%88%ED%98%B8_%EA%B0%80%EB%A6%AC%EA%B8%B0.java

- StringBuilder로 변환 후 끝 4자리를 제외하고 '*' 처리

------------------------------------------------------------------------------------------

행렬의 덧셈 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%ED%96%89%EB%A0%AC%EC%9D%98_%EB%8D%A7%EC%85%88.java

- 이중 for문으로 2차원 배열 arr1, arr2에 접근 후 더하여 answer에 저장

------------------------------------------------------------------------------------------

x만큼 간격이 있는 n개의 숫자 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/x%EB%A7%8C%ED%81%BC_%EA%B0%84%EA%B2%A9%EC%9D%B4_%EC%9E%88%EB%8A%94_n%EA%B0%9C%EC%9D%98_%EC%88%AB%EC%9E%90.java

- int + long 의 경우 결과값이 long으로 연산결과가 나온다.

int + int 의 경우 결과값이 long으로 연산결과가 나온다.

따라서 인자값을 int형에서 long으로 바꿔주면 해결 가능하다.

------------------------------------------------------------------------------------------

직사각형 별찍기 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95_%EB%B3%84%EC%B0%8D%EA%B8%B0.java

- 구구단과 비슷한 이중포문 반복문제

------------------------------------------------------------------------------------------

위클리챌린지 4주차 (21. 09. 02)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%9C%84%ED%81%B4%EB%A6%AC%EC%B1%8C%EB%A6%B0%EC%A7%80_4%EC%A3%BC%EC%B0%A8.java

- 직업을 class화 해서 풀이했으나 다른 풀이보다 성능 및 코드길이가 좋지않음..ㅠㅠ

------------------------------------------------------------------------------------------

정수 내림차순으로 배치하기 (21. 09. 03)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%A0%95%EC%88%98_%EB%82%B4%EB%A6%BC%EC%B0%A8%EC%88%9C%EC%9C%BC%EB%A1%9C_%EB%B0%B0%EC%B9%98%ED%95%98%EA%B8%B0.java

- 숫자를 문자열로 변환 후 split으로 잘라 각 숫자들을 내림차순으로 정렬하고 split으로 자른 배열을 숫자 형태로 변환

------------------------------------------------------------------------------------------

정수 제곱근 판별 (21. 09. 03)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%A0%95%EC%88%98_%EC%A0%9C%EA%B3%B1%EA%B7%BC_%ED%8C%90%EB%B3%84.java

- 전달받은 숫자를 Math.sqrt 메소드를 이용해 루트연산하고 1로 나눈 나머지가 0보다 크면 제곱근이 아니라 판단하여 -1 반환, 0이면 제곱근으로 판단하고 결과값 반환

------------------------------------------------------------------------------------------

짝수와 홀수 (21. 09. 03)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%A7%9D%EC%88%98%EC%99%80_%ED%99%80%EC%88%98.java

- 단순히 나머지 연산을 통해 짝수인지 홀수인지 판단하는 문제

------------------------------------------------------------------------------------------

제일 작은 수 제거하기 (21. 09. 05)

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%A0%9C%EC%9D%BC_%EC%9E%91%EC%9D%80_%EC%88%98_%EC%A0%9C%EA%B1%B0%ED%95%98%EA%B8%B0.java

- 가장 작은 수를 구하고 answer 배열에 저장할 때 해당 작은 수를 제외하고 저장

------------------------------------------------------------------------------------------

문제는 해시 카테고리에 있지만 sort를 이용해서 풀었었다. 아래는 sort를 이용해 풀었을 때의 코드와 정확성 및 효율성 테스트 결과이다.

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_sort.java

public String solution(String[] participant, String[] completion){
    Arrays.sort(participant);
    Arrays.sort(completion);

    int i=0;
    for(i=0; i<completion.length; i++){
      if (!participant[i].equals(completion[i])){
      	return participant[i];
      }
    }
    return participant[i];
}

그리고 아래는 hash를 이용해 풀었을 때의 정확성 및 효율성 테스트 결과이다.

https://github.com/banjjak2/Programmers/blob/main/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%EB%AA%BB%ED%95%9C%EC%84%A0%EC%88%98_hash.java

public String solution(String[] participant, String[] completion){
    String answer = "";
    HashMap<String, Integer> hm = new HashMap<String, Integer>();

    for (String string : participant) {
      if (hm.get(string) == null){
          hm.put(string, 1);
      }
      else{
          hm.put(string, hm.get(string) + 1);
      }
    }

    for (String string : completion) {
    	hm.put(string, hm.get(string) - 1);
    }

    for (Map.Entry<String, Integer> entry : hm.entrySet()) {
      if (entry.getValue() != 0){
          answer = entry.getKey();
          break;
      }
    }

    return answer;
}

효율성 테스트를 보면 메모리 양은 비슷하지만, 시간을 비교했을 때 상당한 시간 차이가 발생했었다. 내가 사용한 Arrays.sort 메소드는 내부적으로 TimSort 알고리즘을 사용하는데, 이 알고리즘은 Merge Sort 알고리즘을 기반으로 작성되었으며, Insertion Sort 알고리즘과 Merge Sort 알고리즘의 결합 형태라고 한다. 

https://d2.naver.com/helloworld/0315536

HashMap의 경우 Key, Value 형식으로 구현이 되어 있는데, 키값을 알면 바로 Value 값을 알 수 있기 때문에 속도가 빠른 것으로 판단된다. 

https://d2.naver.com/helloworld/831311

각 Sort 알고리즘 및 데이터 구조의 시간 복잡도는 아래와 같다.