개발자 Lim

<문제 설명>

<풀기 전 생각>

최단거리를 어떻게 구하느냐가 가장 큰 고민이었다.

 해당 문제에 대해 고민하고 알아보니 일단 공이 한 번 튕겨서 맞기 위해서는 입사각과 반사각이 같아야 하기

때문에 반사각의 성질을 활용하여 생각해보면 맞추어야 할 공을 반사면에 대칭 시킨다면

시작하는 공의 위치에서 대칭이동 된 맞추어야 할 공의 거리가 원쿠션으로 공을 맞출 경우의 거리임을 알 수가 있다.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=yh6613&logNo=220147018035 (자료 및 학습한 자료 링크)

이제 원쿠션으로 공을 맞추었을때 의 길이를 구하는 방식은 해결 되었고 따라서

반사면이 총 4개가 존재하므로 각각의 경우를 체크하여 가장 짧은 최단거리를 구하면 된다

<중간 실패>

그렇게 코드를 짜고 돌려본 결과 29~36번 테스트에서 실패가 나왔고 

원인을 살펴보니 두개의 공의 x좌표 혹은 y좌표가 같은 경우 반대쪽 벽면을 치고 원쿠션을 하는 경우를 체크하지 않아서 임을 파악했고 해당 경우를 체크하도록 코드를 수정하니 Pass 할 수 있었다.

<최종 코드>

import java.util.ArrayList;
import java.util.List;

class Solution {
    // 시간 복잡도 O(4n) 이때 n은 balls 배열의 숫자 이다. 공간 복잡도 O(n)
    public int[] solution(int m, int n, int startX, int startY, int[][] balls) {
        List<Integer> answer = new ArrayList<Integer>();
        for (int []ball:balls) {
            int ans = Integer.MAX_VALUE;
            double tmp = 0;
            if(ball[0] == startX){
                if (ball[1] > startY)
                    tmp = Math.pow(ball[1]+startY, 2);
                else
                    tmp = Math.pow(2*n - ball[1]- startY, 2);
            }
            else if(ball[1] == startY){
                if (ball[0] > startX)
                    tmp = Math.pow(ball[0]+startX, 2);
                else
                    tmp = Math.pow(2*m - ball[0]- startX, 2);
            }

            if(tmp!=0)
                ans = (int)tmp;

            int[][] mirrorPoints = new int[4][2];
            // y 축 대칭
            mirrorPoints[0] = new int[]{-ball[0], ball[1]};
            mirrorPoints[1] = new int[]{2 * m - ball[0], ball[1]};
            // x 축 대칭
            mirrorPoints[2] = new int[]{ball[0], -ball[1]};
            mirrorPoints[3] = new int[]{ball[0], 2 * n - ball[1]};

            for (int[] mirrorPoint : mirrorPoints) {
                if(mirrorPoint[0]==startX||mirrorPoint[1]==startY)
                    continue;
                tmp = Math.pow(mirrorPoint[0] - startX, 2) + Math.pow(mirrorPoint[1] - startY, 2);
                if (ans >= tmp)
                    ans = (int) tmp;
            }

            answer.add(ans);
        }
        return answer.stream().mapToInt(i->i).toArray();
    }
}

<좀 더 생각해 봐야 하는 점>

개인적인 생각으로는 지금은 모든 벽면을 튕기는 경우를 일일이 체크하여 값을 비교하고 있는데

모든 경우를 체크하기 전에 논리적으로 어떤 벽을 튕기는 경우가 최단 거리임을 파악하고 OnePass 알고리즘으로 짤 수 있지 않을까 하는 생각이 든다. 

메모: 수학적인 개념을 다시 복습할 필요성을 느낄 수 있던 문제였다

<풀기 전 생각>

각 문자 하나씩에 접근을 해야함 -> toCharArray() 사용
indexOf() 함수를 통해 만들어야 하는 문자열의 문자의 수가 -1이 아닌 가장 작은수 구하기

target 문자열배열의 문자열 수(반복) 
target 문자열의 char 타입의 수 (반복)
keymap 문자열배열의 문자열 수(반복) 
indexOf() 함수를 통해 만들어야 하는 문자열의 문자의 수가 -1이 아닌 가장 작은수 구하기 O(n)
도출된 값을 저장 

시간복잡도가 약 O(n^4)은 되는 과정을 처음에는 생각했으나

keymap배열을 indexOf함수를 사용해 일일이 탐색 하는 것을 바깥으로 따로 빼내
나온 값들을 어느 자료구조에 저장해두고 빠르게 불러온다면 더 효율적인 코드가 되지 않을까 하는 생각이들어

해당 값을 빠르게 접근 할때 사용하는 자료구조 Map 을 생각할 수 있었고 
미리 Map에다가 모든 정보를 다 저장해 두고 그 정보를 가져오기 만약 해당 정보가 없으면 -1로 처리 하는 방식으로 코드를 짜야겠다 판단하여

결과적으로 시간복잡도를 O(n^2)으로 줄이는 코드를 생각할 수 있었다.

<최종 코드>

import java.util.HashMap;

class Solution {
    // 시간 복잡도 O(mn) 공간 복잡도 O(n)
    public int[] solution(String[] keymap, String[] targets) {
        int[] answer = new int[targets.length];
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();

        // 시간 복잡도 O(keymap.length()*keymap[n].length)
        for (String keyUnit: keymap) {
            for(int i=0;i<keyUnit.length();i++) {
                char key = keyUnit.charAt(i);
                int value = i+1;
                if(map.containsKey(key))
                    value = Math.min(value, map.get(key));
                map.put(key,value);
            }
        }

        // 시간 복잡도 O(targets.length()*targets[n].length)
        for(int i=0;i<targets.length;i++){
            char[] alphas = targets[i].toCharArray();
            int tmp = 0;
            for (char alpha: alphas) {
                if(!map.containsKey(alpha)){
                    tmp = -1;
                    break;
                }
                tmp += map.get(alpha);
            }
            answer[i] = tmp;
        }
        return answer;
    }
}
public class ARoughKeyboard {
    public static void main(String[] args) {
        Solution s = new Solution();
        String tmp1[] = {"AA"};
        String tmp2[] = {"B"};
        int nums[] = s.solution(tmp1,tmp2);
        for (int num: nums) {
            System.out.print(num);
        }
    }
}

<풀기 전 생각>

해당 문제의 핵심은 알파뱃 순서를 바탕으로 해당 문자열의 원소들을 바꿀 수 있냐는 것 이고

실제 아스키 코드의 문자는 알파벳 순서대로 정렬이 되어 있으므로 해당 char 문자형을 이용하는 생각을 할 수 있었다.

추가로 두 문자열의 각 알파벳 하나씩에 접근 해야 하므로 toCharArray()를 사용하는 것이 제일 좋겠다는 판단을 했고 

만약 s의 문자가 skip에 해당되는 문자임은 단순 반복문을 사용해 빼면 된다고 생각하여 문제 풀이에 들어갔다.

<최종 코드>

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n)
    public boolean isSkip(char skipArray[],char input){
        for (char c: skipArray) {
            if(input==c)
                return true;
        }
        return false;
    }
    public String solution(String s, String skip, int index) {
        StringBuilder answer = new StringBuilder("");
        char sArray[] = s.toCharArray();
        char skipArray[] = skip.toCharArray();

        for (char sApa: sArray) {
            for(int i=0;i<index;i++){
                if(sApa=='z')
                    sApa='a'-1;
                sApa++;
                if(isSkip(skipArray,sApa))
                    i--;
            }
            answer.append(sApa);
        }
        return answer.toString();
    }
}

<메모>

우수 풀이를 보니 String 클래스에는 contains(String) 라는 메서드가 존재하고 해당 함수의 시간 복잡도는 O(nm) 임으로

(n은 문자열의 길이 m은 찾고자 하는 문자열의 길이) 다음 부터 한 글자를 가지고 있는지 판단 할 때는 반복문을 사용하기 보다는 해당 함수를 사용하는 것이 훨씬 가독성이 좋아 질 것 같다.

!skip.contains(String.valueOf(temp))

<풀기 전 생각>

들어오는 n이 long 타입 이어서 인지 바로 정수 연산이 되지 않아서 문자열 배열로서 처리를 해야 한다는 생각을 했고

만약 10000 을 뒤집었을 때 값이 00001이 되는 것을 방지 해야 한다는 생각을 가지고 문제 풀이에 들어갔다.

+ArrayList<Integer> 를 int[] 로 바꾸기

<중간 문제점>

5, 7 번 test에서 실패가 나왔다.

import java.util.ArrayList;

class Solution {
    public int[] solution(long n) {
        int[] answer = {};
        ArrayList<Integer> ans = new ArrayList<>();
        String num = String.valueOf(n);
        char array[] = num.toCharArray();
        for(int i=array.length-1;i>=0;i--){
            if(ans.size()==0&&array[i]=='0')
                continue;
            else
                ans.add(Integer.parseInt(array[i]+""));
        }

        answer = new int[ans.size()];
        for(int i=0;i<answer.length;i++)
            answer[i] = ans.get(i);

        System.out.println("kest");
        return answer;
    }
}

왜 그런가 시도해본 결과 "만약 10000 을 뒤집었을 때 값이 00001이 되는 것을 방지 해야 한다." 이부분이 필요가 없는 조건 이었기 때문에 실패 한 거였다. 10000 -> 00001 으로 배열이 반환되는게 맞았다.

그리고 생각해보면 ArrayList를 쓸 필요 없이 그냥 일반 배열을 사용해도 되는 상황이 된다.

<최종 코드>

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int[] solution(long n) {
        String num = String.valueOf(n);
        char array[] = num.toCharArray();
        int[] answer = new int[array.length];
        int index=0;
        for(int i=array.length-1;i>=0;i--){
                answer[index++]=Integer.parseInt(array[i]+"");
        }

        System.out.println("kest");
        return answer;
    }
}

<메모>

처음에는 long 타입이면 정수 연산이 불가능 할 줄 알았는데 우수 풀이를 보니

단순히 (int) 형으로 타입 캐스팅을 할 경우 정수 연산 %, / 등이 가능했다.

class Solution2{
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int[] solution(long n){
        String a = ""+n;
        int answer[] = new int[a.length()];
        int index = 0;
        while(n>0){
            answer[index++] = (int)(n%10);
            n/=10;
        }
        return answer;
    }
}

<풀기 전 생각>

뽑은 인형의 갯수가 불확실 하므로 길이가 가변적인 자료구조 사용이 필요하다 -> ArrayList, Set, Stack, Queue, Deck

나머지는 단순 for, if 문으로 해결이 가능해 보였다.

<중간 문제점>

처음에 1번 하고 2번이 런타임 에러가 나왔었는데  생각해보니 그 이유는 인형 뽑기에서 0을 뽑은 경우는 아무 것도 안한 걸로 취급해야 하는데 0을 뽑아서 담은 걸로 취급하는 식으로 코드를 짜서 해당 문제가 발생한 것 이었다.

<최종 코드>

import java.util.ArrayList;

class Solution {
    private int pickUp(int [][]board, int num){
        int doll=0;
        for(int i=0;i<board.length;i++){
            if(board[i][num-1]!=0){
                doll = board[i][num-1];
                board[i][num-1] = 0;
                break;
            }
        }
        return doll;
    }
    // 시간 복잡도 O(n*m) 공간 복잡도 O(n)
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        ArrayList<Integer> collections = new ArrayList<Integer>();
        // length-1 = -1 방지
        collections.add(0);
        for(int i=0;i<moves.length;i++){
            int lastIndex = collections.size()-1;
            int before = collections.get(lastIndex);
            int curr = pickUp(board,moves[i]);
            if(curr == 0)
                continue;
            if(before==curr) {
                collections.remove(lastIndex);
                answer+=2;
            }
            else
                collections.add(curr);
        }

        return answer;
    }
}

<메모>

가변적인 길이의 자료구조만을 생각해서 ArrayList를 사용하였는데 다시 생각해보니 Stack을 사용하는게 이 문제 취지에 훨씬 알맞는 내용이지 않았을까 싶다.

<풀기 전 생각>

핵심적으로 해야 할 것은 win_nums의 배열의 저장된 정수를 lottos에 몇개 나 가지고 있는지 탐색 하는 것 임으로

단순 반복으로 선형 탐색하여 해결 할 수도 있겠지만 O(n) 이진탐색 + 정렬 O(2log n)을 통해 속도를 더 개선시키자는 생각으로 문제 풀이에 들어갔다.

<중간 문제점>

단순히 Arrays.binarySearch(win_nums, lottos[i]) > -1 내장된 빌트인 함수를 사용할 수도 있겠지만

앞에 0의 갯수를 감안하여 이진 탐색의 범위를 좁히고 싶어 직접 구현하게 되었다.

<최종적인 코드>

class Solution {
    // 시간 복잡도 O(nlog n) 공간 복잡도 O(n)
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        Arrays.sort(win_nums);
        int zeroCount = 0;
        int correctCount = 0;
        // 0의 갯수 체크
        for (int lotto: lottos) {
            if(lotto==0)
                zeroCount++;
            else
                break;
        }

        // 로또 번호 탐색 시작
        for (int num:win_nums) {
            int first = zeroCount;
            int last = lottos.length-1;
            // 이진 탐색
            while(first<=last){
                int mid = (first+last)/2;
                if(lottos[mid]>num)
                    last = mid-1;
                else if(lottos[mid]<num)
                    first = mid+1;
                else {
                    correctCount++;
                    break;
                }
            }
        }

        int maxCorrect = zeroCount+correctCount;
        int maxRank = 7-maxCorrect;
        answer[0] = maxRank>=6?6:maxRank;

        int minRank = 7-correctCount;
        answer[1] = minRank>=6?6:minRank;

        return answer;
    }
}

<메모> 

우수 풀이를 보니 Map 자료구조의 containsKey() 시간 복잡도 O(1) 함수를 활용하여 지금 내가 짠 코드의 시간 복잡도 O(nlog n) 보다 더 효율적으로 O(n)으로 푼 풀이를 볼 수 있어서 

중복을 제외한(중요!) 두 배열에서 겹치는 요소를 탐색 할 때는 Mep or Set의 자료구조를 활용해야 겠다.

<풀기 전 생각>

문자열의 조합이라 정규식을 활용하여 각 3번의 횟수의 대한 문자열을 나눌까도 생각하였지만 

처음에 0~10이 아닌 1~9 까지의 숫자가 들어온다고 착각하여 각 문자 하나당 처리하면 쉽게 풀 수 있을 것 같아

toCharArray()를 사용하여 문자열을 split()을 사용한 것 보다 빠르게 한 글자씩 채취해서

처리하고자 하였다.

<중간 문제점>

toCharArray()를 통해 char 타입으로 한 글자씩 추출 한 것은 좋았으나 Integer.parseInt()는 String 타입만을 지원하기 때문에 어떻게 해야 하나 고민 하였는데 간단히 +"" 공백을 추가하는 것으로 문자열로 바꾸어 해결 할 수 있었다.

10이 문자열에 포함되어 있어서 if문 하나를 추가해서 해결 하였지만

극단적으로 0~10 까지의 값 만을 가지고 답을 만들 수 있어 유연하지는 못 하게 된 것 같다.

 <전체 코드>

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public int solution(String dartResult) {
        int answer = 0;
        char charArray[] = dartResult.toCharArray();
        // 얻을 수 있는 point는 3종류 이지만 * 아이템을 처리 하기위해 맨 앞에 공간을 하나 더 만들어줌 
        int points[] = new int[4];

        int turn = 1;
        int point = 0;
        for(int i=0;i<charArray.length;i++){
            // 점수 부분
            if(charArray[i]>='0'&&charArray[i]<='9') {
                if(charArray[i+1]>='0'&&charArray[i+1]<='9')
                    point += Integer.parseInt(charArray[i]+""+charArray[i+1]+"");
                else
                    point += Integer.parseInt(charArray[i] + "");
            }
            // 점수 보너스 부분
            else if(charArray[i]=='S'||charArray[i] == 'D'||charArray[i] == 'T'){
                if (charArray[i] == 'S')
                    point = (int)Math.pow(point, 1);
                else if (charArray[i] == 'D')
                    point = (int)Math.pow(point, 2);
                else
                    point = (int)Math.pow(point, 3);
                
                // 만약 다음 문자가 없거나 특수 문자가 아니라면 해당 점수를 저장하고 다음 점수로 파트로 넘아감
                if(i+1==charArray.length||(charArray[i+1]>='0'&&charArray[i+1]<='9')){
                    points[turn] = point;
                    turn++; point=0;
                }

            }
            // 특수 아이템 부분
            else{
                if(charArray[i]=='*') {
                    point *= 2;
                    points[turn-1]*=2;
                }
                else
                    point*=-1;

                points[turn] = point;
                point=0;
                turn++;

            }
        }

        for (int num: points) {
            answer+=num;
        }
        return answer;
    }
}

<메모>

앞으로는 (charArray[i]>='0'&&charArray[i]<='9') 대신 사용하면 좋을 것 같다.

해당 피턴의 정규식

String reg = "([0-9]{1,2}[S|T|D][*|#]{0,1})";

+ 해당 클래스를 사용한 아주 인상적인 풀이가 있어서 공부해두어야 할 것 같다.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

<풀기 전 생각>

sort()함수를 사용하여 유저들의 클리어 스테이지 정보를 정렬시키고

각 스테이지의 실패율을 float 타입으로 실제로 구하고 차후 반복문을 이용해 높은 순서대로 인덱스를 뽑아 반환 할 계획을 세우고 문제 풀이에 들어 갔다.

<중간 문제점>

 float의 표현 범위는 소수 7번째 자리 까지 임으로 그 이상의 자리 수에서 차이가 난 경우는 비교하는게 불가능 하여

1 , 6, 7, 9, 13, 14, 23, 24, 25, 26 에서 오류가 발생하였고

 double 로 고쳐도 Pass가 되지 않아 좀더 고민하게 되었다.

<실패한 코드>

class Solution {
    public int[] solutionFail(int N, int[] stages) {
        int[] answer = new int[N];
        int maxPeople = stages.length;
        double[] failureRate = new double[N];
        int i=0; int j=0;
        Arrays.sort(stages); // n*log n
        // 전체 스테이지 탐색
        for(int stage=1;stage<=N;stage++) {
            // 실패율의 분자
            int numerator = 0;
            for (i = 0; i < maxPeople; i++) {
                if(stage==stages[i])
                    numerator++;
                if(stage<stages[i])
                    break;
            }
            // 예외 처리
            if(i==0)
                failureRate[stage] = 0;
            else{
                // 실패율의 분모 (통과한 인원 수)
                int denominator = maxPeople-i+numerator;
                failureRate[stage-1] = (double) numerator/denominator;
            }
        }
        System.out.println("qf");
        for(i=0;i<answer.length;i++) {
            double tmp = -1; int index=-1;
            for (j = 0; j < failureRate.length; j++) {
                if(tmp<failureRate[j]){
                    tmp=failureRate[j];
                    index = j;
                }
            }
            failureRate[index] = -1;
            answer[i] = index+1;
        }
        return answer;
    }

}

애초에 비교방식을 실수가 아닌 분자*분모 이런 식으로 정수 끼리 비교할 경우 정확한 비교가 가능하다고 판단하여

코드를 수정했으나 

1 ,6, 7, 13, 23, 24, 25가 계속해서 성공하지 않았고 

고민 한 결과 분자가 0이 된 경우 실패율이 0임을 처리하니

최종적으로 23, 24을 제외하고는 pass 하게 되었고

추가적으로 고민하다 문제에서 정수의 범위는 1~200000 임을 보게 되었고

int 형으로는 200000 * 200000 의 수를 전부 표현 하는게 불가능 하다는 생각이 들게 되어 

long 타입으로 바꾸어서 푸니 비로서 pass 할 수 있었다.

<최종 코드>

시간 복잡도 O(n*m) 공간 복잡도 O(n)

class Solution {
    public int[] solution(int N, int[] stages) {
        // 정수 범위를 벗어나는 경우 때문에 안됨
        int[] answer = new int[N];
        int maxPeople = stages.length;
        // 분자, 분모 순으로 저장
        long[][] failureRate = new long[N][2];
        int i=0; int j=0;
        Arrays.sort(stages); // n*log n
        // 전체 스테이지 탐색
        int numerator,denominator;
        for(int stage=1;stage<=N;stage++) {
            // 실패율의 분자
            numerator = 0;
            for (i = 0; i < maxPeople; i++) {
                if(stage==stages[i])
                    numerator++;
                if(stage<stages[i])
                    break;
            }
            // 실패율의 분모 (통과한 인원 수)
            if(numerator==0)
                denominator=1;
            else
                denominator = maxPeople-i+numerator;
            //failureRate[stage-1] = (float) numerator/denominator;
            failureRate[stage-1][0] = numerator;
            failureRate[stage-1][1] = denominator;
        }
        System.out.println("qf");
        for(i=0;i<answer.length;i++) {
            long tmp[] = {-1,1}; int index=-1;
            for (j = 0; j < failureRate.length; j++) {
                if(tmp[0]*failureRate[j][1]<failureRate[j][0]*tmp[1]){
                    tmp[0]=failureRate[j][0];
                    tmp[1]=failureRate[j][1];
                    index = j;
                }
            }
            failureRate[index][0] = -1;
            failureRate[index][1] = 1;
            answer[i] = index+1;
        }

        return answer;
    }
}

 메모: 우수 풀이를 보니 해당 인터페이스를 구체화 하여 문제를 해결 하였는데 추가 학습할 필요가 있어 보인다.

+ double도 결국에는 소수점 16자리 까지 표현이 불가능 한거로 알아서 미묘한 오차가 생길 줄 알았는데 예상 외 였다.

Comparable<Stage>