개발자로 살아남기

[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 배열에 저장할 때 해당 작은 수를 제외하고 저장

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

최대공약수, 최소공배수 구하기

공약수 : 두 개 이상의 자연수(양의 정수) 중에서 공통된 약수

최대공약수 : 공약수 중 제일 큰 약수

서로소 : 공약수가 1뿐인 2개 이상의 자연수

최대공약수

 - 소인수분해로 구하기 (서로소가 나올 때까지 소수로 계속 나눔)

 - 출처 : https://mathbang.net/202

 - 최대공약수는 6x2 = 12

공배수 : 2개 이상의 자연수 중에서 공통된 배수

최소공배수 : 공배수 중 제일 작은 공배수

최소공배수

 - 위 사진에서 최소공배수는 6x2x5x4 = 240 이다.

소인수분해를 이용한 최대공약수, 최소공배수 구하기

// 소인수분해를 이용한 풀이
// 결과값 = 공약수들 + 서로소들
public static int[] factorization(int n, int m){
    int divisor = 2;
    List<Integer> facts = new ArrayList<Integer>();
    int[] retData;

    while(true){
        if ((n % divisor == 0) && (m % divisor == 0)){
            facts.add(divisor);
            n /= divisor;
            m /= divisor;
        }
        else{
            if (divisor > n || divisor > m){
                facts.add(n);
                facts.add(m);
                break;
            }

            divisor++;
        }
    }

    retData = new int[facts.size()];
    for(int i=0; i<facts.size(); i++){
        retData[i] = facts.get(i);
    }

    return retData;
}

유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기

 - 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r0를 구하고 다시 r을 r0로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a, b의 최대 공약수이다.

 - 출처 : https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

// gcd : 최대공약수
// lcm : 최소공배수
public static int[] gcdlcm(int n, int m){
    int gcd;
    int lcm;

    gcd = gcd(n, m);
    lcm = (n * m) / gcd;

    return new int[] { gcd, lcm };
}

public static int gcd(int n, int m){
    // 나머지가 0이면
    if (m == 0){
        // 나눈값 반환
        return n;
    }

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

약수의 총 합 구하기

프로그래머스의 약수의 총 합을 풀었는데 정석의 방법으로 풀었었다.

int answer = 0;

for(int i=1; i<=n; i++){
    if (n % i == 0){
        answer += i;
    }
}

return answer;

다른 풀이를 보니 아래와 같이 풀었는데, 그 이유는 간단했다.

int answer = 0;

for(int i=1; i<=n / 2; i++){
    if (n % i == 0){
        answer += i;
    }
}

answer += n;

return answer;

for문의 조건에서 n/2를 한 이유는 약수는 n의 절반이 넘는 값이 나올 수 없기 때문인데

예를들어, 12의 경우 약수는 1, 2, 3, 4, 6, 12이며 1x12 == 2x6 == 3x4 == 12 로 계산이 가능하다.

따라서 어떤 수가 들어오더라도 n의 약수 중 n의 절반이 넘는 값이 약수가 될 수 없다.

그래서 아래 풀이의 경우 연산횟수를 절반으로 줄일 수 있다.

에라토스테네스의 체

에라토스테네스의 체 (위키)

  - 어떤 수가 소수인지 판별할 수 있는 방법

  - 2의 배수부터 지우고(자기자신 제외) 다음 숫자로 넘어가 3의 배수를 지우고(자기자신 제외)를 반복

  - 지운 숫자에 접근할 경우 다음 숫자로 넘어감

public int eratosthenes(int n){
    int[] arr = new int[n - 1]; // 0, 1 제외하고 n은 포함되어야 하니까 -1
    int count = 0;

    for(int i=2; i<=n; i++){
        arr[i - 2] = i;
    }
    
    for(int i=2; i<=n; i++){
        if (arr[i - 2] == 0){
            continue;
        }

        for(int j=i+i; j<=n; j+=i){ // 자기자신 제외 (i + i), 배수만큼 (j + i)
            arr[j - 2] = 0;
        }
    }

    for (int i : arr) {
        if (i != 0){
            count++;
        }
    }

    return count;
}

문제는 해시 카테고리에 있지만 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 알고리즘 및 데이터 구조의 시간 복잡도는 아래와 같다.

유클리드(유클리디안) 거리

 - 피타고라스 정리와 비슷한 개념

 - 실제 거리를 구할 때에도 사용하지만, 인공지능 등 다양한 분야에서 유사도를 판단할 때 자주 사용됨

 - 피타고라스 정리과 다르게 유클리드 거리는 다차원 공간에서 거리를 구할 수 있음

위 그림을 보면 유클리드 거리와 피타고라스의 정리를 이용해 붉은선의 길이를 구하는 공식은 동일하다.

그러나, 두 점이 3차원 좌표에 있을 경우 피타고라스 정리로는 해결이 안되고 유클리드 거리로 구해야한다.

예를 들어서 좌표가 P1(-1, 2, 3), P2(4, 0, -3)인 경우에는 아래와 같이 계산해야 한다.

맨하탄 거리

 - 택시거리, L1 거리, 시가지거리 라고도 함

 - 유클리드 거리와 같이 좌표간의 거리를 구함

 - 유클리드 거리보다 더 계산하기 쉬움

위 사진의 설명에서 볼 수 있듯이 좌표간 거리가 1이라고 할 때 빨간색, 파란색, 노란색 모두 12로 가장 짧은 맨하탄 거리이며 초록색 선 길이는 유클리드 거리를 이용하여 계산한 값이다. 맨하탄 거리를 구하는 공식은 아래와 같다.

2차원의 경우,

위 그림과 같으며, 3차원의 경우

위 그림과 같다.

즉, 좌표에서 차원에 맞게 뺀 후 절댓값을 취하여 그 값들을 다 더하면 맨하탄 거리가 된다.