1회차 - 알고리즘 기록

📌문제2A-도토리 키재기 

 

도토리 나라의 도토리들이 다니는 도토리 고등학교에서는 매 달 재미있는 이벤트를 한다.

도토리 나라에서는 다른 도토리들 보다 큰 키를 가지는 것이 큰 경쟁력 중 하나였기에,

도토리 고등학교에서는 매 달마다 그 달에 생일이 있는 도토리들 중 가장 큰 키를 가진 도토리에게 상장을 수여한다.

N개의 도토리에 대한 키와 생일 정보가 주어진다.

이 때 이번 달에 생일이 있는 도토리들 중 가장 키가 큰 도토리의 키를 출력하는 프로그램을 작성하자.

 

입력 형식

• 첫 줄에는 도토리의 수를 나타내는 N이 1이상 10만 이하의 자연수로 주어진다.
• 두 번째 줄에는 N개의 도토리의 키가 공백으로 구분된 1이상 10억 이하의 자연수로 주어진다.
• 세 번째 줄에는 N개의 도토리들의 생일이 속한 달을 나타내는 1이상 12이하의 자연수가 공백으로 구분되어 주어진다. 
• 네 번째 줄에는 현재 달을 나타내는 1이상 12이하의 자연수 M이 주어진다 

 

출력 형식

문제의 답을 공백없이 정수로 출력한다. 생일에 해당 달에 속한 도토리가 없는 경우 -1을 출력한다.

 

예시

- 입력

5
12 13 14 15 16
1 5 7 2 3

2

 

- 출력

15

 

생각 풀이

생일 배열에서 현재 달과 일치하는 달의 인덱스를 추출한다.

키 배열에서 추출한 인덱스를 뽑고 그 중에 제일 큰 키를 찾는다.

 

코드 풀이

/**
 * 생일이 m월인 가장 큰 키의 도토리를 찾는 함수
 * @param height  각 도토리의 키
 * @param month   각 도토리의 출생 월
 * @param n   도토리의 수
 * @param m   찾고자 하는 달
 * @return    month[k] == m인 가장 큰 height[k]
 */
public static int getMaximumHeight(int[] height, int[] month, int n, int m) {

    int maxHeight = 0;

    for(int i = 0; i < month.length; i ++ ) {
        if(month[i] == m) {
            if(height[i] > maxHeight) {
                maxHeight = height[i];
            };
        }
    }

    return maxHeight == 0 ? -1 : maxHeight;
}

---

📌 문제2B-오름차순인가?

 

그룹을 관리하는 리더라는 직위는 절대 쉬운 것이 아니다. 외국의 한 유명한 여자 대학교인 질레보르(Zylevol)대학교에는 한국인 유학생 수정이와 예인이가 다니고있다. 수정이는 학생회장으로서 학교 행사마다 학생들을 통솔하는 역할을 맡고 있다. 이번 학교 행사에서도 학생회장 수정이는 학생들을 통솔하는 역할을 맡게 되었다. 이번 행사에서는 안무 준비를 위하여 각 학생들은 키가 작은 학생부터 큰 순서대로 일렬로 서야 한다. 하지만 전 날에 먹은 우유의 탓으로 수정이가 몸져 눕게되자, 평소 자신도 학생 회장을 잘 할 수 있다는 자신감에 가득 차 있던 예인이가 대행을 자원했다.

 예인이는 이리저리 뛰어다니며 학생들을 일렬로 세웠으나, 이 많은 학생들이 정말로 키 순으로 서 있는지 확신이 서지 않았다. 당신은 예인이를 도울 수 있도록 학생들이 실제로 키에 대하여 오름차순으로 서 있는지 판별해주는 프로그램을 작성해주려고 한다.

 

입력 형식

 첫 줄에는 학생의 수 N이 주어진다. N은 1이상 10만 이하의 자연수이다.

두 번째 줄에는 공백으로 구분된 학생들의 키가 총 N개 주어진다. 각 학생의 키는 마이크로미터 단위로 측정하여 1이상 2,000,000 이하의 자연수이다.

 

출력 형식

 첫 줄에 학생들의 키가 오름차순으로 정렬되어 있는지 여부를 YES 혹은 NO로 출력한다.

• YES - 각 학생들의 키가 오름차순으로 정렬되어있다.
• NO - 그렇지 않다

예시

- 입력

5
1 2 3 5 4

 

- 출력

NO

 

생각 풀이

인덱스를 0부터 탄다.

키 배열을 인덱스부터 접근한다. 그리고 인덱스 + 1 과 비교

인덱스 > 인덱스 + 1  조건이 true 라면 오름차순이 아니다 !

 

코드 풀이

/**
 * 주어진 배열이 오름차순인지 검사하는 함수
 * @param data
 * @param n     데이터의 수
 * @return      data[0] ~ data[n-1]이 오름차순이라면 true, else false
 */
public static boolean isOrdered(int[] data, int n){

    for(int i = 0; i < data.length-1; i ++) {
        if(data[i] > data[i+1] ) {
            return false;
        }
    }
    return true;
}

 

---

📌문제2C-다양성

가수의 앨범은 팬들에게는 중요한 존재이다.

긴 기다림의 끝에 마주친 오아시스 같은 존재이기 때문이다.

그렇기에 최근의 가수들은 자신의 앨범에 기념품이나 손편지 등을 추가하여 팬들에게 고마운 마음을 전하고있다.

인기 많은 아이돌 트와이스의 열렬한 팬인 민규는 이번에도 앨범을 사기 위하여 신촌의 한 백화점에 줄을 서서 대기하고있다.

이 백화점에서 판매하는 앨범은 한정판으로서, 각 앨범에는 임의의 화보가 한 장 들어있다.

이미 입대가 얼마남지 않은 민규는 자신의 모든 재산을 털어 트와이스 앨범을 구매하여 모든 종류의 화보를 수집하고자 한다.

 각 화보들은 종류별로 고유한 번호를 가지고있으며 이 번호를 통해 같은 화보인지 아닌지 구분할 수 있다.

물론 여러 앨범들에는 같은 화보가 들어있을 수 있다.

민규는 총 N개의 앨범을 구매하여 화보들을 번호 순서대로 정렬하여 보관하려고 한다.

이 때 민규는 자신이 총 몇 종류의 화보를 획득하였는지 궁금해졌고, 코딩을 잘하는 당신에게 이를 계산하는 프로그램을 작성해주기를 부탁하였다.

민규의 마지막 소원을 들어주기 위하여 프로그램을 작성하시오.

 

입력 형식

 첫 줄에는 화보의 수 N이 주어진다. N은 1이상 10만 이하의 자연수이다.

두 번째 줄에는 각 화보의 고유번호가 공백으로 구분되어 주어진다. 각 화보의 고유번호는 32비트 정수형 중 하나로 주어지며, N개의 고유번호는 오름차순으로 주어진다.

 

출력 형식

 한 줄에 중복을 제외한 화보의 종류의 수를 공백없는 자연수로 출력한다.

 

예시

입력	5 1 2 3 4 5	5 1 2 3 4 4
출력	5	4

 

생각 풀이

리스트 하나를 생성한 다음 원본 배열을 돌면서 리스트에 없는 값들만 하나씩 추가해준다.

근데 테스트 케이스틑 다 작동하는데 timeout 으로 실패한다.

로직 문제인가 ? 이건 분량 끝내고 다시 돌아와서 체크해야겠다.

 

답이 안나와서 정답을 슬쩍 봤는데 엥 ? 이렇게 하니까 된다고 ?

설마 오름차순인가 했는데 오름차순이었다;

문제를 제대로 안읽어 이 꼴이 났다 ㅠㅠ.

무작위 숫자인줄 알고 배열 전체 순회를 하니 timeout 이 발생했나보다.

 

코드 풀이

/**
 * 중복을 제외한 숫자의 종류의 수를 계산하는 함수
 * @param data  원본 배열
 * @param n     원본 배열의 크기
 * @return  숫자의 종류의 수
 */
public static int getElementTypeCount(int[] data, int n){
    List<Integer> equlsList = new ArrayList();

    for( int i = 0; i < n; i ++) {

        boolean check = false;

        for(int y = 0; y < equlsList.size(); y++) {
            if(data[i] == equlsList.get(y)) {
                check = true;
            }
        }

        if(!check) {
            equlsList.add(data[i]);
        }
    }

    return equlsList.size();
}

 

쌤 풀이

/**
 * 중복을 제외한 숫자의 종류의 수를 계산하는 함수
 * @param data  원본 배열
 * @param n     원본 배열의 크기
 * @return  숫자의 종류의 수
 */
public static int getElementTypeCount(int[] data, int n){
        int countType = 0;

        for( int i = 0; i < n; i++){
            if( i == 0 || data[i-1] != data[i]){
                countType++;
            }
        }
        return countType;
}

 

---

📌문제2D-문자열의 비교 (revised)

 

 

프로그래밍 언어에서는 단어나 문장과 같은 두 글자 이상의 텍스트 데이터를 문자열(String)의 형태로 관리합니다.

문자열이란 각 문자를 배열로 저장한 구조를 말합니다. 아래의 그림이 문자열의 구조를 설명해줍니다.

최근의 언어들은 문자열 또한 string과 같은 기본 타입으로서 제공하기에 많은 분들이 모르고 넘어가는 것이 있습니다. 바로 문자열은 단순히 하나의 값이 아니라 문자(character) 값의 배열이기 때문에 숫자와 같이 단순한 비교가 불가능하다는 점입니다.

이를 해결하기 위하여 해싱(hashing)과 같은 기법들이 등장하였으나, 원리를 모르고 사용하는 해싱은 독이 될 수 있습니다.

두 문자열을 사전순으로 비교하거나 서로 같은 문자열인지 판별하려면 어떻게 해야할까요?

또 어떻게 비교해야 효율적으로 비교할 수 있을까요? 이런 점들을 고민하며 문제를 풀어봅시다.

 

지시사항

1. 문자열의 사전순 대소관계 비교를 위한 함수 compare(s1,s2)를 완성하세요. 
2. 문자열의 일치여부를 확인하기 위한 함수 equals(s1, s2)를 완성하세요.

 

제한사항

문자열은 최대 10만글자 이하의 알파벳 소문자로 구성되어 있다

 

생각 풀이

하나는 크고 작음을 비교, 하나는 같은지 비교하기.

문자열은 사실 문자의 배열인데 매번 equals 로 비교하니 문자 비교로 접근한적은 없는 것 같다.

앞으로도 equals 로 비교하겠지만 ,, : )

 

- 크니 작니

아무튼 do while 로 접근해야겠다.

문자열 길이가 작은 문자열 기준으로 비교를 진행하고 진행하는 와중에 비교가 된다면 결과를 바로 반환하고

문자열 길이가 작은 문자열 인덱스까지도 같다면 ?

그 뒤에오는 문자가 다를 것도 고려해야 한다.

문자열 길이가 같다면 문자가 모두 같다는 것이고, 아니면 ,,,,,,,,,

경우의 수는 두개로 나뉜다.

둘 중에 하나 단어는 이미 비교할 문자가 없는 상태니까 s1 의 길이가 더 크다면 1 이고 아니라면 -1 이다.

 

- 같니 다르니

문자열 길이가 다르다면 다르다는 것이니까 비교할 필요도 없당! 보내버리고 ,,

하나하나 비교하다 하나라도 다르면 바로 false ! 끝까지 일치하면 true

 

코드 풀이

public static int compare(char[] s1, char[] s2){
    /* 두 문자열 s1, s2를 비교하여 일치하면 0, 
    s1이 사전순으로 앞서면 음수
    s2가 사전순으로 앞서면 양수를 반환하는 함수
    */
    int index = 0;

    do{
        if((int)s1[index] < (int)s2[index]) {
            return -1;
        }else if((int)s1[index] > (int)s2[index]) {
            return 1;
        }

        index++;
    }while( index < s1.length &&  index < s2.length );

    return s1.length == s2.length ? 0 : s1.length > s2.length ? 1 : -1;
}

public static boolean equals(char[] s1, char[] s2){
    /* 두 문자열 s1, s2가 일치하면 true
     일치하지 않으면 false를 반환하는 함수
    */
    if(s1.length != s2.length) {
        return false;
    }

    int index = 0;

    do{
        if((int)s1[index] != (int)s2[index]) {
            return false;
        }

        index++;
    }while( index < s1.length &&  index < s2.length );

    return true;
}

 

---

📌문제2E-소수의 판별

 

어릴적 주산을 배운 예인이는 항상 주변 사람들에게 자신이 암산을 잘한다고 주장하고 다닌다. 하지만 이런 예인이의 말을 믿지못한 수정이는 예인이에게 암기 퀴즈를 내주기로 하였다. 똑똑한 수정이는 예인이에게 다음과 같은 퀴즈를 제안했다.

• 수정이는 1이상 10억 이하의 자연수를 하나 마음속으로 정한다.
• 수정이는 스탑워치를 사용해 시작버튼을 누름과 동시에 예인이에게 정한 숫자를 말해준다.
• 예인이는 숫자를 듣고 2초안에 그 숫자가 소수인지 아닌지를 대답하여야 한다.

 하지만 자신의 암산 실력에 자신이 없어진 예인이는 몰래 당신에게 수정이가 말한 숫자가 소수인지 빠르게 판별할 수 있는 프로그램을 작성해달라고 부탁하였다. 예인이를 도와주기 위해 프로그램을 작성하시오.

 이 문제는 여러 개의 테스트 케이스로 구성되어있다. 예제 입/출력 데이터를 확인하여 유의하자.

 

입력 형식

입력 데이터의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. T는 1이상 10이하의 자연수이다.

각 테스트 케이스별로 한 줄에 자연수 하나가 주어진다. 각 자연수는 1이상 10억 이하의 자연수이다.

 

출력 형식

 각 테스트 케이스별로 아래와 같은 형식으로 결과를 출력한다.

• 테스트 케이스의 첫 줄에는 테스트 케이스의 번호를 1과 T사이의 자연수로 출력한다. 아래와 같은 형식을 따른다
• 테스트 케이스의 두 번째 줄에는 소수이면 YES를 출력하고, 그렇지 않으면 NO를 출력한다.

 

예시

- 입력

2

1

5

 

- 출력

Case #1

NO

Case #2

YES

 

생각 풀이

자 ,, 처음에 몇개 숫자를 할껀지 판단을 해 !

그리고 일단,,, 하나씩 생각을 해보자 !

5 가 소수인지 아닌지 확인하려면

 

2, 3, 4 로 5를 나누면서 0으로 나뉘어 떨어지니 ? 라고 물어봐야 한다 : (

귀찮다 해볼까 ? 하띵

 

코드 풀이

 

/**
* 주어진 숫자가 소수인지 판별하는 함수 
*
* @param N 
* @return true   소수라면 
* @return false  소수가 아니라면
*/
public static boolean isPrime(int N){

    if(N == 1) {
        return false;
    } else if(N == 2) {
        return true;
    } else if( N % 2 == 0){
        return false;
    }

    int count = 0;

    for( int i = 3; i <= Math.sqrt(N); i += 2) {

        if(N % i == 0) {
            count++;
            break;
        }
    } 
    return count == 0;
}

---