알고리즘 스터디(1) - 10804번, 2587번, 1427번, 11047번

💛 브론즈2 - 10804번: 카드 역배치

🔻 JAVA

package onboard;

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

public class Problem2 {
    public static Integer[] solution(Integer[][] flipCards){
        Integer[] answer = new Integer[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

        for(int i=0; i < 10; i++){
            int start = flipCards[i][0] - 1;
            int end = flipCards[i][1] - 1;
            int middle = (start + end) / 2;
            int temp = 0;

            for(int s=start, e=end; s<=middle; s++, e--){
                temp = answer[s];
                answer[s] = answer[e];
                answer[e] = temp;
            }
        }
        return answer;
    }
}

/* test 케이스 */
@Nested
 class Problem2Test{
        @Test
        void case1(){
            Integer[][] flipCards = {{5, 10}, {9, 13}, {1, 2}, {3, 4}, {5, 6}, {1, 2}, {3, 4}, {5, 6}, {1, 20}, {1, 20}};
            Integer[] answer = {1, 2, 3, 4, 10, 9, 8, 7, 13, 12, 11, 5, 6, 14, 15, 16, 17, 18, 19, 20};
            assertThat(Problem2.solution(flipCards)).isEqualTo(answer);
        }
    }

🔻python

import sys
input = sys.stdin.readline #입력을 빠르게 받기 위해 사용
# sys 모듈을 불러와서 표준입력을 빠르게 받기 위한 코드

cards = [i for i in range(1,21)] #1부터 20까지의 숫자로 구성된 리스트 만들기
for _ in range(10): #10번 반복하는 for문
    a,b = map(int,input().split()) #두 개의 정수를 입력받아 a와 b에 저장
    a-=1
    cards[a:b] = cards[a:b][::-1] #a부터 b-1까지의 카드 뒤집기
    #구간을 뒤집기 위해서는 리스트의 슬라이싱과 [::-1] 문법을 사용합니다. [::-1]은 리스트의 역순을 만들기 위한 Python의 슬라이싱 문법
print(*cards) #카드 리스트를 출력, *를 사용해서 리스트를 언패킹하여 출력

sys.stdin.readline 함수

• Python의 기본 input 함수는 입력을 받기 위해 사용되며, 사용자의 입력을 문자열 형태로 반환하나, 입력이 많아질 경우 처리 시간이 오래 걸림. 대량의 입력을 빠르게 처리하기 위해서는 sys 모듈을 사용하여 입력을 받는 것이 좋다!

• sys.stdin.readline 함수는 표준 입력에서 한 줄씩 입력을 읽어 들이며, 문자열로 반환하여 input 함수보다 빠름. 따라서 sys 모듈을 이용하여 대량의 입력을 빠르게 처리 가능!

Python의 슬라이싱 문법

• 슬라이싱(slicing)은 시퀀스 객체를 자른 후 일부를 선택하여 가져올 수 있는 기능, 시퀀스 객체에는 리스트, 튜플, 문자열 등이 있고 이러한 객체들은 순서가 있으므로 슬라이싱 가능

my_list[start:stop:step] # start는 시작 인덱스, stop은 종료 인덱스, step은 간격

my_list = [1, 2, 3, 4, 5]

# 리스트의 2번 인덱스부터 4번 인덱스까지 슬라이싱
result = my_list[2:5]
print(result)  # [3, 4, 5]

# 리스트의 처음부터 3번 인덱스까지 슬라이싱
result = my_list[:4]
print(result)  # [1, 2, 3, 4]

# 리스트의 2번 인덱스부터 끝까지 슬라이싱
result = my_list[2:]
print(result)  # [3, 4, 5]

# 리스트 전체를 슬라이싱하여 복사
result = my_list[:]
print(result)  # [1, 2, 3, 4, 5]

# 리스트를 거꾸로 뒤집기
result = my_list[::-1]
print(result)  # [5, 4, 3, 2, 1]

🔻C

#include <stdio.h>

int main() {
    int cards[20]; // 20개의 정수로 구성된 배열을 선언
    for (int i = 0; i < 20; i++) {
        cards[i] = i + 1; // 배열의 각 요소에 1부터 20까지의 숫자 저장
    }
    for (int i = 0; i < 10; i++) { // 10번 반복하는 for문
        int a, b;
        scanf("%d %d", &a, &b); // 두 개의 정수를 입력받아 a와 b에 저장
        a--; // a의 값을 1 감소
        for (int j = a; j < (a + b) / 2; j++) { // a부터 b-1까지의 카드를 뒤집기 위한 for문 
            int temp = cards[j];
            cards[j] = cards[b - j + a - 1];
            cards[b - j + a - 1] = temp; // 카드의 위치를 바꾸기 위한 코드
        }
    }
    for (int i = 0; i < 20; i++) {
        printf("%d ", cards[i]); // 카드 배열을 출력하는 코드
    }
    return 0;
}

💛 브론즈2 - 2587번: 대표값2

🔻 JAVA

package onboard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Problem3 {
    public static List<Integer> solution(List<Integer> numbers){
        List<Integer> answer = new ArrayList<>();
        int sum = 0;

        Collections.sort(numbers);

        for(int i=0; i<5; i++){
            sum += numbers.get(i);
        }
        int average = sum / 5;

        int mid;
        mid = numbers.get(numbers.size() / 2);

        answer.add(average);
        answer.add(mid);

        return answer;
    }
}

/* test 케이스 */
@Nested
    class Problem3Test{
        @Test
        void case1(){
            List<Integer> numbers = new ArrayList<>(Arrays.asList(10, 40, 30, 60, 30));
            List<Integer> answer = new ArrayList<>(Arrays.asList(34, 30));
            assertThat(Problem3.solution(numbers)).isEqualTo(answer);
        }
    }

🔻python

x = [] # 빈 리스트 x를 생성
for i in range(5): # for 루프를 이용하여 5번 반복
    x.append(int(input())) # 사용자로부터 정수 값을 입력받아 리스트 x에 추가
x.sort() # 리스트 x를 오름차순으로 정렬
print(int(sum(x)/5)) # 리스트 x의 합을 5로 나눈 후, 정수로 반환(소숫점 이하 버림)하여 평균 값을 출력
print(x[2]) # 리스트 x의 3번째 원소를 출력! 

Python 리스트(List) 관련 함수

List

: 여러 개의 값을 순서대로 저장하는 자료형으로, 대괄호로 묶어서 표현한다. 파이썬 리스트의 가장 큰 특징은 동적으로 크기가 변할 수 있어서 요소를 추가, 삭제, 변경 가능하다.

append(x): 리스트의 맨 뒤에 요소 x를 추가합니다.
extend(iterable): 리스트의 맨 뒤에 iterable의 모든 요소를 추가합니다. 여기서 iterable은 여러 개의 요소를 가진 순회 가능한 객체로 리스트, 튜플, 세트, 문자열 등이 될 수 있음
insert(i, x): 지정된 위치(i번째 인덱스)에 요소 x를 삽입합니다.
remove(x): 리스트에서 첫 번째로 나오는 요소 x를 삭제합니다.
pop([i]): 리스트에서 지정된 위치(i번째 인덱스)의 요소를 삭제하고, 해당 값을 반환합니다. 지정된 위치가 없으면, 리스트의 마지막 요소를 삭제하고, 해당 값을 반환합니다.
sort(): 리스트의 요소를 오름차순으로 정렬합니다.
reverse(): 리스트의 요소를 뒤집습니다.

🔻C

#include <stdio.h>

int main() {
    int x[5]; // 정수형 배열 x를 선언
    int i, j, temp;

    for (i = 0; i < 5; i++) {
        scanf("%d", &x[i]); // 5번 반복하며 정수 값을 입력받아 배열 x에 저장
    }

    for (i = 0; i < 4; i++) { 
        for (j = i+1; j < 5; j++) {
            if (x[i] > x[j]) {
                temp = x[i];
                x[i] = x[j];
                x[j] = temp;
            } // for 루프를 이용하여 배열 x를 오름차순으로 정렬
        }
    }

    printf("%d\n", x[2]); // 배열 x의 세번째 원소 출력
    printf("%d\n", (x[0] + x[1] + x[2] + x[3] + x[4]) / 5); // 배열 x의 합을 5로 나눈 후, 소수점 이하를 버림하여 평균 값을 출력

    return 0;
}

🤍 실버5 - 1427번: 소트인사이드

🔻 JAVA

package onboard;

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

public class Problem4 {
    public static Integer solution(Integer number){
        List<Integer> bits = new ArrayList<>();
        while(number > 0){
            bits.add(number % 10);
            number = number / 10;
        }
        Collections.sort(bits, Collections.reverseOrder());
        Integer answer = 0;
        for(Integer num : bits){
            answer = answer * 10 + num;
        }
        return answer;
    }
}

/* test 케이스 */
@Nested
    class Problem4Test{
        @Test
        void case1(){
            Integer number = 2143;
            Integer answer = 4321;
            assertThat(Problem4.solution(number)).isEqualTo(answer);
        }
   }

🔻python

x = list(map(str,input())) # 사용자로부터 입력받은 문자열을 리스트에 담는다. map() 함수를 이용하여 입력받은 문자열을 문자 하나씩 분리하여 리스트에 저장, 이따 str 함수를 이용해 분리한 문자를 문자열로 변환
x.sort(reverse=True) # 리스트를 내림차순으로 정렬
for i in x: # 리스트의 각 요소를 반복하면서 
    print(i, end='') # 각 요소를 출력, end=''은 줄바꿈 없이 출력하는 역할

map 함수

• 주어진 iterable(리스트, 튜플, 세트 등)의 모든 요소에 대해 지정된 함수를 적용하여 그 결과를 새로운 iterable로 반환한다. map 함수의 기본 구문은

map(function, iterable)

여기서 function은 각 요소에 적용될 함수이며, iterable은 함수를 적용할 요소들을 포함하는 iterable 객체

map함수를 이용하여 새로운 리스트를 반환하는 예시

def square(x):
    return x**2

numbers = [1, 2, 3, 4, 5]
squares = list(map(square, numbers))
print(squares) # 출력결과: [1, 4, 9, 16, 25]

str 함수

• str 함수는 파이썬의 내장 함수 중 하나로, 인자로 전달된 객체를 문자열로 변환하여 반환한다. 즉, 숫자나 리스트 등 다양한 데이터 타입을 문자열로 변환할 수 있음

str함수를 이용하여 숫자를 문자열로 변환하는 예시

number = 123
string = str(number)
print(string) # 출력결과: "123"

🔻C

#include <stdio.h>
#include <string.h>

int main() {
    char x[11]; // 10자 이하의 숫자 문자열을 저장할 배열
    int i, j, len;

    scanf("%s", x); // 문자열 입력
    len = strlen(x); // 문자열의 길이 계산

    for (i = 0; i < len - 1; i++) { // 선택 정렬 알고리즘을 이용한 내림차순 정렬
        int max_idx = i;
        for (j = i + 1; j < len; j++) {
            if (x[j] > x[max_idx])
                max_idx = j;
        }
        char temp = x[i];
        x[i] = x[max_idx];
        x[max_idx] = temp;
    }

    printf("%s", x); // 정렬된 문자열 출력

    return 0;
}

선택 정렬 알고리즘

: 각 인덱스마다 그 다음 인덱스부터 마지막 인덱스까지의 값을 비교하여 최솟값 또는 최댓값을 찾아 해당 인덱스와 교환하는 알고리즘

🤍 실버4 - 11047번: 동전 0

🔻 JAVA

package onboard;

import java.util.Arrays;

public class Problem5 {
    public static Integer solution(Integer N, Integer K, Integer[] values){
        Integer answer = 0;

        Integer[] coin = new Integer[K+1];
        Arrays.fill(coin, 100001);
        coin[0] = 0;

        for(int i=1; i<=K; i++) {
            for(int j=0; j<N; j++) {
                if(i - values[j] >= 0) {
                    coin[i] = Math.min(coin[i], coin[i-values[j]]+1);
                }
            }
        }

        answer = coin[K] == 100001 ? -1 : coin[K];
        return answer;
    }
}

/* test 케이스 */
@Nested
    class Problem5Test{
        @Test
        void case1(){
            Integer N = 10;
            Integer K = 4200;
            Integer[] values = {1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000};
            Integer answer = 6;
            assertThat(Problem5.solution(N, K, values)).isEqualTo(answer);
        }
    }

🔻python

N, K = map(int, input().split()) # 입력 값으로 받은 N, K를 각각 int 형으로 변환하여 변수에 저장 
coin_lst = list() # coin_lst 리스트를 생성하고 
for i in range(N):
    coin_lst.append(int(input())) # N개의 동전 값들을 입력받아 리스트에 추가한다

count = 0
for i in reversed(range(N)): # reversed() 함수를 이용하여 N-1부터 0까지 역순으로 반복
    count += K//coin_lst[i] # 카운트 값에 K를 동전으로 나눈 몫을 더해줌
    K = K%coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복

print(count) # 카운트값을 최종적으로 출력한다

🔻C

#include <stdio.h>

int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    
    int coin_lst[N]; # 배열 생성하고
    for (int i = 0; i < N; i++) { # N개의 동전 값들을 입력 받아 배열에 추가한다
        scanf("%d", &coin_lst[i]);
    }
    
    int count = 0;
    for (int i = N-1; i >= 0; i--) { # N-1부터 0까지 역순으로 반복하면서 각 동전으로 얼마나 거슬러줄 수 있는지 계산
        count += K / coin_lst[i]; # 카운트 값에 K를 현재 동전 값으로 나눈 몫을 더해준다.
        K = K % coin_lst[i]; # K는 현재 동전 값으로 나눈 나머지로 갱신해주기
    }
    
    printf("%d\n", count);
    return 0;
}

: 파이썬 코드와의 차이를 살펴보면, 파이썬은 리스트를 이용해 동전 값을 저장하고 reversed 함수를 이용해 역순으로 반복하고 C언어에서는 배열을 이용해 동전 값을 저장하고 for문에서 0부터 N-1까지 설정하고 i의 초기값을 N-1으로 설정하여 거꾸로 반복하는 점이 있다! 나머지는 비슷,,