항해99 11/10(수) 알고리즘 - 알아서 푼 것들

실패율 - Entry 사용

코딩테스트 연습 - 실패율

class Solution {
    public int[] solution(int N, int[] stages) {
        // 실패율의 정의 : 스테이지에 도달했지만 클리어하지 못 한 플레이어의 수 / 스테이지에 도달한 플레이어의 수
        // N은 전체 스테이지의 개수
        // 멈춘 스테이지 리스트가 stages
        // 실패율이 높은 스테이지부터 내림차순으로 return

        int[] answer = new int[N];
        int[] clearArr = new int[N+2]; // 501스테이지까지 담기 위해서
        Map<Integer, Double> map = new HashMap<>();

        for(int i = 0; i < stages.length; i++){ // 1스테이지부터 시작
            clearArr[stages[i]]++;
        }

        int clearCnt = clearArr[clearArr.length-1]; // 다 깬 사람 숫자는 제일먼저 더해놓는것
        for(int i = clearArr.length-2; i > 0; i--){ // 실패율 계산. 끝 스테이지는 이미 계산했으므로 제외
            // 1. 위에서부터 내려오면서 계산하면 중첩 for문 사용할 필요가 없어짐
            // 5스테이지까지 있을때 숫자가 6인 사람은 모두 깬 사람임 = 더하기만 하면 됨
            // 그 이하는 남아있는 숫자가지고 꼬물꼬물 해서 실패율 구해 맵에 넣는게 좋나?
            clearCnt += clearArr[i];
            if(clearCnt == 0){
                map.put(i, 0.0);
            }else{
                map.put(i, (double)clearArr[i] / clearCnt);
            }
        }

        List<Map.Entry<Integer, Double>> entries = new LinkedList<>(map.entrySet());
        // o1, o2 순서 바꾸면 오름차순 정렬로 바뀜
        Collections.sort(entries, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));

        int arrCnt = 0;
        for( Map.Entry<Integer, Double> entry : entries){
            answer[arrCnt++] = entry.getKey();
        }
        return answer;
    }
}

풀고보니 나름 뿌듯했다. 처음이었으면 감도 못 잡았을 것 같은데 단 이틀만에 이만큼까지 풀어낼 수 있도록 실력이 끌어올려진 것이 나름 스스로 대견하다. 이 중 인터넷을 통해 힌트를 얻은 것은 Entry를 이용해서 정렬하는 것이다. 보아하니 언젠가 쓸 일이 있을 것 같아보인다. 자주 써보면서 체화시켜줘야겠다.

Map을 이용해서 이런 식으로 푼 건 처음이었는데, 꽤 모양새가 괜찮다. 속도는 좀 느리더라도 말이다.....

 

 

폰켓몬 - Iterator 사용

코딩테스트 연습 - 폰켓몬

class Solution {
    public int solution(int[] nums) {
        // nums.length/2마리 가져가도 된다고 함
        // 중복해서 가져가지 않고 최대한 많이 가져가게 만들면 됨

        int answer = 0;
        Set<Integer> set = new HashSet<>();

        // 중복값 제거
        for(int i =0; i < nums.length; i++){
            set.add(nums[i]);
        }

        if(set.size() < nums.length/2){
            answer = set.size();
        }else{
            Iterator<Integer> iter = set.iterator();
            while(iter.hasNext() && answer < nums.length/2){
                iter.next();
                answer++;
            }
        }

        return answer;
    }
}

폰켓몬을 중복해서 가져가는건 best case가 아니기 때문에 Set을 사용해서 중복값을 제거해주고 그 값이 전체 포켓...이 아니라 폰켓몬 수/2보다 낮으면 그냥 전체 크기를 반환, 넘으면 Iterator 사용해서 출력시켜줬다. 심플한 문제 주제에 작명센스 하나는 고급진 것 같다.

 

 

비밀지도

코딩테스트 연습 - [1차] 비밀지도

class Solution {
    public String binaryZeroFill(String str, int n){
        String res = str;

        for(int i = 0; i < n-str.length(); i++){
            res = "0" + res;
        }

        return res;
    }

    public String[] solution(int n, int[] arr1, int[] arr2) {
        // 한 변의 길이가 n인 정사각형 배열. 종류는 공백(0) 또는 벽(1)
        // arr1 지도와 arr2 지도를 겹쳐서 전체 지도를 얻을 수 있다.
        // 한쪽이라도 벽이면 벽이며, 둘 다 공백이어야 지도에서 공백이다.
        // 각 배열은 지도의 가로줄에서 벽을 1, 공백을 0으로 부호화했을 때 나오는 이진수이다.
        // 1. n*n 배열 생성(해보고 필요 없으면 생략)
        // 2. 지도 복호화(정수를 이진수로 변환. parseInt나 toBinaryString 쓰면 편할 듯?)
        // 3. 겹쳐보기

        String[] answer = {};
        List<String> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String sArr1 = Integer.toBinaryString(arr1[i]);
            String sArr2 = Integer.toBinaryString(arr2[i]);

            // 0으로 채워주기
            if (sArr1.length() < n){
                sArr1 = binaryZeroFill(sArr1, n);
            }
            if (sArr2.length() < n){
                sArr2 = binaryZeroFill(sArr2, n);
            }

            // 겹쳐보기
            char[] chars = new char[n];
            for(int k = 0; k < chars.length; k++){
                //둘 중 하나라도 벽이면
                if(sArr1.charAt(k) == '1' || sArr2.charAt(k) == '1'){
                    chars[k] = '#';
                }else{
                    chars[k] = ' ';
                }
            }
            list.add(String.valueOf(chars));
        }

        answer = list.toArray(new String[list.size()]);
        return answer;
    }
}

이진수로 바꿔주는 것, 이것을 비교하는 것 두 가지를 잘 해주면 쉽게 풀 수 있는 문제인 것 같다. 지문이 일견 복잡해보일 수 있지만, 내용 자체는 평이한 수준의 문제였다. 마음에 들지 않는 점은 중첩 for문을 사용한 점이다. 다른 문제들을 보니 for문 두 번으로 처리한 케이스도 있었다.

 

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] result = new String[n];
        for (int i = 0; i < n; i++) {
            result[i] = Integer.toBinaryString(arr1[i] | arr2[i]);
        }

        for (int i = 0; i < n; i++) {
            result[i] = String.format("%" + n + "s", result[i]);
            result[i] = result[i].replaceAll("1", "#");
            result[i] = result[i].replaceAll("0", " ");
        }

        return result;
    }
}

그 중에서도 이런 식의 기능 활용은 정말 끝내주는 것 같다. or 연산자로 긴 코드를 한 방에 해결해버렸다. 보기에 너무 예뻐보여서 한 번 내 코드에 적용해봤다.

 

class Solution {
    public String binaryZeroFill(String str, int n){
        String res = str;

        for(int i = 0; i < n-str.length(); i++){
            res = "0" + res;
        }

        return res;
    }

    public String[] solution(int n, int[] arr1, int[] arr2) {
        List<String> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String sArr = Integer.toBinaryString(arr1[i] | arr2[i]);
            
            sArr = binaryZeroFill(sArr, n);
            sArr = sArr.replaceAll("1", "#");
            sArr = sArr.replaceAll("0", " ");
            list.add(sArr);
        }
        
        return list.toArray(new String[list.size()]);
    }
}

엄청나게 짧아졌다. 대박적이다.

 

 

크레인 인형뽑기 게임 - Stack 사용

코딩테스트 연습 - 크레인 인형뽑기 게임

class Solution {
    public int pickUp(int[][] board, int target){
        int result = 0;

        // 바구니가 비어있지 않을 경우에만 실행
        if(board[board.length-1][target-1] != 0){
            for(int i = 0; i < board.length; i++){
                System.out.println(i + ", " + (target-1));
                // 세로로 탐색
                if(board[i][target-1] == 0){
                    continue;
                }else{
                    result = board[i][target-1];
                    board[i][target-1] = 0;
                    break;
                }
            }
        }

        return result;
    }

    public int solution(int[][] board, int[] moves) {
        // 화면은 board 크기의 정사각형 격자
        // 격자 아래칸부터 인형들이 쌓여있음
        // 크레인은 멈춘 위치의 가장 위의 인형을 집어 올려 바구니에 쌓게 됨
        // 쌓인 인형이 같은 종류의 인형이라면, 인형을 터뜨림. Stack의 peek, pop 기능 사용하면 될 듯
        // 인형이 없는 곳에서 작동하는 크레인은 아무런 동작도 하지 않음
        // board : 화면 상태, move : 크레인의 무빙
        // 터뜨려 없앤 인형의 개수를 return.
        int answer = 0;
        Stack<Integer> bucket = new Stack<>();
		
        // 이 반복문은 테스트를 위한 출력구간이라 안 넣어도 됨
        for(int i = 0; i < board.length; i++){
            for(int k = 0; k < board.length; k++){
                System.out.print(board[i][k] + " ");
            }
            System.out.println();
        }
        
        
        for(int i = 0; i < moves.length; i++){
            // 보드에서 집어들기
            int pick = pickUp(board, moves[i]);

            System.out.println("집어온거 : " + pick);
            // 무언가 집어오는데 성공한 경우
            if(pick != 0){
                if(!bucket.isEmpty() && bucket.peek() == pick){
                    bucket.pop();
                    System.out.println("터뜨림!");
                    answer += 2;
                }else{
                    bucket.push(pick);
                }
            }
            System.out.println("현재 스택 상황 : " + bucket.toString());
        }

        return answer;
    }
}

어떻게 해야 값을 집어올 수 있는지에 대한 고민을 많이 했다. 풀고보니 별 거 없었지만, 2시간은 넘게 걸렸던 것 같다. 카카오 코딩 문제들은 전체적으로 지문에 대한 이해도가 꽤 있어야 빠르게 풀 수 있을 것 같다.

 

 

 

 

이렇게 이번주차에 할당된 40문제 + 챌린지 14문제를 다 풀어봤다. 어려운 문제도 많았고 쉬운 문제도 많았다. 배운 점도 많았고 전체적인 알고리즘 풀이 방법에 대해서도 감이 잡히는 것 같다. 이젠 프로그래머스 레벨2로 넘어갈 준비가 된 듯한 느낌이 든다. 화이팅.