명품호세의 개발 공부 및 기록 블로그

문제의 그림만 보고 생각하면 어떻게 풀어야 할지 감이 잘 안온다. 표를 만들어서 한번 보자

표를 자세히 보면 방이 1개일때를 제외하고는 층이 바뀔때 마다 방이 6의 배수로 늘어나는 것을 볼 수 있다.

또한 1층을 제외한 층의 최소 방번호 역시 최소 방번호 + 해당 층의 방 갯수를 더하면 다음 층의 최소 방번호가 나오는 것을 알 수 있다.

이것을 힌트로 코드를 작성해보자

int range = 2;
int count = 1;

while (range <= N) {
    range += 6 * count;
    count ++;
}

System.out.println(count);

1층일 때는 어차피 1이므로 제외하고 range를 2층의 최소 방번호 부터 시작해보자. (여기서 N은 입력 방 번호값이다)

사용자가 N을 입력하면 range를 2층부터 방의 수를 계속 더해주어 N보다 커지면 중지시키는 알고리즘이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        if (N == 1) {
            System.out.println(N);
            return;
        } else {
            int range = 2;
            int count = 1;

            while (range <= N) {
                range += 6 * count;
                count ++;
            }

            System.out.println(count);
        }
    }
}

참고 : [백준] 2292번 : 벌집 - JAVA [자바] (tistory.com)

주어진 문자열을 모두 순회하면서 변경할 크로아티아 알파벳이 나올경우 비교하여 순회하면 된다.

예를 들면 c가 나올경우 c다음에 =가 나올지 -가 나올지 비교하며 진행하면 된다.

코드로 알아보자

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();

for (int i = 0; i < length; i++) {
        char ch = s.charAt(i);

        char nextCh;

        if (ch == 'c' && i < length - 1) {
            nextCh = s.charAt(i + 1);

            if (nextCh == '=' || nextCh == '-') {
                    i += 1;
            }
        }
 }

1. 위 코드에서 문장 s의 길이로 전체 순회를 돈다.
2. 문자열의 해당 인덱스에 단어를 가져온다.
3. 크로아티아 알파벳에 해당할 경우 그 다음 단어까지 비교한다.
4. 만약 문장 끝에 c가 있을 경우 nextCh를 가져올때 IndexOutofBounds 에러가 발생하니 문장의 끝이 아닌지 확인한다.
5. 변경된 크로아티아 알파벳에 해당할 경우 2단어를 1단어로 취급해야 하니 인덱스 i를 +1 해준다.

아래는 전체 코드 이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int count = 0;
        int length = s.length();

        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);

            char nextCh;

            if (ch == 'c' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=' || nextCh == '-') {
                    i += 1;
                }
            } else if (ch == 'd' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'z' && i < length - 2) {
                    nextCh = s.charAt(i + 2);
                    if (nextCh == '=') {
                        i += 2;
                    }
                } else if (nextCh == '-') {
                    i += 1;
                }
            } else if (ch == 'l' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'j') {
                    i += 1;
                }
            } else if (ch == 'n' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == 'j') {
                    i += 1;
                }
            } else if (ch == 's' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=') {
                    i += 1;
                }
            } else if (ch == 'z' && i < length - 1) {
                nextCh = s.charAt(i + 1);

                if (nextCh == '=') {
                    i += 1;
                }
            }

            count++;
        }

        System.out.println(count);
    }
}

재귀 용법을 활용한 정렬 알고리즘이다.

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

알고리즘의 이해

데이터가 4개일때

예 ) data = [1, 9, 3, 2]

1. 먼저 [1, 9], [3, 2] 로 나눈다.
2. 다시 [1,9]를 [1], [9]로 나눈다.
3. 나눈 [1], [9]를 정렬하여 [1, 9]로 합친다.
4. 다음 [3, 2]를 [3], [2]로 나눈다.
5. 나눈 [3], [2]를 정렬하여 [2, 3]으로 합친다.
6. [1,9]와 [2,3]을 정렬하여 합친다.
   1. 1 < 2 이니 [1]
   2. 9 > 2 이니 [1, 2]
   3. 9 > 3 이니 [1, 2, 3]
   4. 9밖에 없으니 [1, 2, 3, 9]

완성 코드

import random


def split(list_data):
    if len(list_data) < 1:
        return list_data

    mid_index = len(list_data) // 2

    left_list = split(list_data[:mid_index])
    right_list = split(list_data[mid_index:])

    return merge(left_list, right_list)


def merge(left_list, right_list):
    left_start_index, right_start_index = 0, 0
    temp_list = list()

    while len(left_list) > left_start_index and len(right_list) > right_start_index:

        if left_list[left_start_index] < right_list[right_start_index]:
            temp_list.append(left_list[left_start_index])
            left_start_index += 1

        else:
            temp_list.append(right_list[right_start_index])
            right_start_index += 1

    while len(left_list) > left_start_index:
        temp_list.append(left_list[left_start_index])
        left_start_index += 1

    while len(right_list) > right_start_index:
        temp_list.append(right_list[right_start_index])
        right_start_index += 1

    return temp_list


def merge_sort(list_data):
    return split(list_data)


if __name__ == '__main__':
    data = random.sample(range(1000), 15)

    print(data)

    print(merge_sort(data))

퀵 정렬이란?

• 기준점 (pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽 으로 모으는 함수를 작성함
• 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.
• 함수는 왼쪽 + 기준점 + 오른쪽을 리턴한다.

import random


def quick_sort(list_data):
    if len(list_data) <= 1:
        return list_data

    pivot = list_data[len(list_data) // 2]

    left = [item for item in list_data if pivot > item]

    right = [item for item in list_data if pivot < item]

    return quick_sort(left) + [pivot] + quick_sort(right)


if __name__ == '__main__':
    data = random.sample(range(1000), 30)

    print("정렬 전 : ", data)
    print()
    print("정렬 후 : ", quick_sort(data))