[코딩 테스트 RUN] 코딩 기초 트레이닝 7일차

⚠️ 주의!
프로그래머스에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

7일자 코테런. 내가 생각하는 것보다 더 어려운 문제가 들어있었다.

 

 

수열과 구간 쿼리 4

정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.

각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 i가 k의 배수이면 arr[i]에 1을 더합니다.

위 규칙에 따라 queries를 처리한 이후의 arr를 return 하는 solution 함수를 완성해 주세요.

 

 

문제 코드

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = {};
        return answer;
    }
}

 

 

정답 해설

이전 수열과 구간 쿼리를 풀었다면 쉬이 풀 수 있을 것이다.

다만, 중간에 한 차례 실수를 했었는데, answer의 배열을 맞춰야한단 생각 때문에 for문을 arr.length로 하는 실수가 있었던 것. answer를 그냥 arr로 복사하면 된다.  그 외에는 무난하게 해결된다.

 

 

정답

class Solution {
    public int[] solution(int[] arr, int[][] queries) {
        int[] answer = new int[arr.length];
        int s, e, k;
        int m = 0;
        
        for(int i = 0; i < arr.length; i++) {
            answer[i] = arr[i];
        }
        
        for(int i = 0; i < queries.length; i++){
                s = queries[i][0];
                e = queries[i][1];
                k = queries[i][2];            
                          
                for(int j = s; j <= e; j++){
                    if(j % k == 0){
                        answer[j] += 1;
                    }
            }

        }
                return answer;
    }
}

 

for문 순환이 아니라 Arrays.copyOf를 사용해도 되고, for문 순회 또한 int[] query : queries 형태로 순회해도 된다.

 

 

배열 만들기 2

정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.

만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.

 

문제 코드

class Solution {
    public int[] solution(int l, int r) {
        int[] answer = {};
        return answer;
    }
}

 

 

문제 해설

제일 어려웠던 문제.

ArrayList를 안 쓰고는 어려운 문제. answer의 배열 길이를 정하기 어렵기 때문에 먼저 ArrayList에 담아 사용하는 것이 좋다. 그 외에는 여태까지 했던 것을 얼마나 알고 있는가에 대한 것이다. if문, continue문.

 

ArrayList 메서드에 관해서는 추가한다.

 

ArrayList.add()

해당 ArrayList에 배열을 추가한다.

 

ArrayList.size()

ArrayList의 길이를 정한다. ArrayList.size()가 0일 경우 없지만 그 경우 isEmpty를 더 자주 사용한다.

 

ArrayList.get(index)

해당 ArrayList의 index 위치에 있는 값을 불러온다.

 

 

 

정답

import java.util.ArrayList;

class Solution {
    public int[] solution(int l, int r) {
        int[] answer = {};
        ArrayList<Integer> list = new ArrayList<>();
        String c = "";
        for(int i = l; i <= r; i++){
            c = "" + i;
            boolean valid = true;
            for(int j = 0; j < c.length(); j++){
                if(c.charAt(j) != '0' && c.charAt(j) != '5'){
                    valid = false;
                    continue;
                }                
            }
            if(valid){
                list.add(i);
            }
        }
        if(list.size() > 0) {
            answer = new int[list.size()];
            for(int i = 0; i < list.size(); i++){
                answer[i] = list.get(i);
            }
        } else {
            answer = new int[]{-1};
        }
        
        return answer;
    }
}

 

 

가장 많이 좋아요를 받은 풀이는 이것이다.

import java.util.ArrayList;

class Solution {
    public int[] solution(int l, int r) {

        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 1; i < 64; i++) {
            int num = Integer.parseInt(Integer.toBinaryString(i)) * 5;
            if (l <= num && num <= r)
                list.add(num);
        }

        return list.isEmpty() ? new int[] { -1 } : list.stream().mapToInt(i -> i).toArray();
    }
}

 

 

이진수를 이용한 풀이다.

문제를 보면 5, 50, 55,  … 555 … 등으로 되어있는데, 이걸 5로 나누면 1,10,11, … 과 같이 된다. 즉, 이진수로 풀어쓸 수 있는 것.  r의 값이  1,000,000 이하이므로 이진수적으로는 64 미만으로 나타나면 된다.

다음은 보충 설명이자 공부.

 

 

Integer.toBinaryString(int)

정수를 2진수의 String으로 바꾼다.

 

ArrayList.stream()

ArrayList를 Stream으로 변환한다.

 

.mapToInt()

Stream의 각 요소를 int로 변환한다.

 

ArrayList.toArray()

 

ArrayList를 Array(배열)로 만든다.

 

 

즉 list를 int 배열로 나타내기 위함이다.

 

 

카운트 업

정수 start_num와 end_num가 주어질 때, start_num부터 end_num까지의 숫자를 차례로 담은 리스트를 return하도록 solution 함수를 완성해주세요.

 

문제 코드

class Solution {
    public int[] solution(int start_num, int end_num) {
        int[] answer = {};
        return answer;
    }
}

 

 

문제 해설

아까 문제에 비해 지나치게 쉬운 문제.

answer의 length에만 조심하면 된다.

 

정답

class Solution {
    public int[] solution(int start_num, int end_num) {
        int[] answer = new int[end_num - start_num + 1];
        int index = 0;
        for(int i = start_num; i <= end_num; i++){
            index = i - start_num;
            answer[index] = i;
        }
        return answer;
    }
}

 

 

 

 

 

콜라츠 수열 만들기

모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다.

그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.

계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다.

임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.

 

 

문제 코드

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        return answer;
    }
}

 

정답 해설

이 경우, for문보다는 while문을 사용하는 것이 좋다.

 

 

정답

import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        int[] answer = {};
        ArrayList<Integer> list = new ArrayList<>();
        list.add(n);
        
        while(true){
            if(n % 2 == 0){
                n = n / 2;
                list.add(n);
            } else {
                n = 3 * n + 1;
                list.add(n);
            }
            if(n == 1) break;
        }
        
        answer = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
              answer[i] = list.get(i);
         }        
        
        return answer;
    }
}

 

삼항연산자나 위에서 본 메서드 등을 통해 더 간단하게 만들 수 있다.

 

import java.util.ArrayList;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(n);

        while(n != 1){
            n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
            list.add(n);
        }

        return list.stream().mapToInt(i -> i).toArray();
    }
}

 

 

가장 많은 좋아요를 받은 정답은

import java.util.stream.IntStream;

class Solution {
    public int[] solution(int n) {
        return IntStream.concat(
                        IntStream.iterate(n, i -> i > 1, i -> i % 2 == 0 ? i / 2 : i * 3 + 1),
                        IntStream.of(1))
                .toArray();
    }
}

 

이것이다.

 

IntStream

정수형을 스트림형태로 사용하는 클래스다.

 

Intstream.concat()

스트림들을 결합한다.

 

IntStream.iterate(시작값, 조건, 다음값함수)

시작값에서 조건을 만족하는한 반복하며, 다음값을 정한다.

(1) 시작값은 n

(2) 조건은 i -> i > 1로 i가 1보다 큰 동안이라고 되어있으니 이때까지 반복한다.

(3) 다음 수에 대한 함수인데, 나머지 연산을 삼항연산으로 하여 짝수면 i / 2를, 아니라면 i * 3 + 1을 반환하도록 하고 있다.

 

 

IntStream.of(index)

지정된 값을 포함하는 스트림을 반환한다. 여기서는 1을 넣어 1의 스트림만을 반환했다.

 

 

배열 만들기 4

정수 배열 arr가 주어집니다. arr를 이용해 새로운 배열 stk를 만드려고 합니다.

변수 i를 만들어 초기값을 0으로 설정한 후 i가 arr의 길이보다 작으면 다음 작업을 반복합니다.

1. 만약 stk가 빈 배열이라면 arr[i]를 stk에 추가하고 i에 1을 더합니다.
2. stk에 원소가 있고, stk의 마지막 원소가 arr[i]보다 작으면 arr[i]를 stk의 뒤에 추가하고 i에 1을 더합니다.
3. stk에 원소가 있는데 stk의 마지막 원소가 arr[i]보다 크거나 같으면 stk의 마지막 원소를 stk에서 제거합니다.

위 작업을 마친 후 만들어진 stk를 return 하는 solution 함수를 완성해 주세요.

 

문제 코드

class Solution {
    public int[] solution(int[] arr) {
        int[] stk = {};
        return stk;
    }
}

 

 

문제 해설

마찬가지로 ArrayList를 사용해야하는 것.

마지막 원소가 list.size() - 1임에 유의하면 좋다(마음대로 i로 넣었다가 큰코를 봤다)

remove에만 1을 더하지 않는다는 지점에도 유의.

 

정답

import java.util.ArrayList;

class Solution {
    public int[] solution(int[] arr) {
        int[] stk = {};
        ArrayList<Integer> list = new ArrayList<>();
        int i = 0;
        while(i < arr.length){
            if(list.size() == 0){
                list.add(arr[i]);
                i++;
            }  else if(list.get(list.size() - 1) < arr[i]) {
                list.add(arr[i]);
                i++;
            }  else {
                list.remove(list.size() - 1);
            }
        }
        
        stk = new int[list.size()];
        for(i = 0; i < list.size(); i++){
              stk[i] = list.get(i);
         }  
        
        return stk;
    }
}

 

 

제일 많이 좋아요를 받은 것이다.

 

import java.util.*;

class Solution {
    public Stack<Integer> solution(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;

        while (i < arr.length) {
            if (stack.empty() || stack.peek() < arr[i]) {
                stack.push(arr[i]);
                i++;
            } else if (stack.peek() >= arr[i]) {
                stack.pop();
            }
        }
        return stack;
    }
}

 

 

일단 여기서 Stack은 제네릭 클래스이며, 자료 구조 중 하나이다. LIFO(Last In First Out) 구조의 자료구조로, 마지막에 넣은 게 맨 먼저 나오는 형태이다. 여기서는 Stack을 사용하여 처리했다.

 

Stack.peek()

Stack에서 마지막 데이터를 반환한다.

 

Stack.push()

Stack에 추가한다. javascript에서도 사용하는 것이다.

 

Stack.pop()

마지막 데이터를 꺼내서 반환한다(즉, 제거 처리)