오늘은 검색 알고리즘에 대해서 가볍게 공부해봤습니다. 그 중에서도 배열과 Linked List에 대해서 자세히 알아 보았고, 주로 어떤 용도에서 활용할 수 있을지도 알게 되어서 좋았습니다. 프로그래밍을 하면서 가장 많이 접해본 것중 하나가 배열이라서 … 드디어 아는게 나왔네요.

검색 알고리즘

정적 Array

정적 Array가 처음에 뭐지 싶었는데 찾아보니… 그냥 배열을 정적 어레이라고 부르는거 였다.
보통 아래 그림처럼 고정된 크기와 동일한 자료형만 저장할 수 있는 자료의 집합을 배열이라고 합니다.

배열의 모습

배열의 가장 큰 장점은 인덱스만 알고 있으면 바로 원하는 키 값이 들어있는 배열의 요소에 바로 접근할 수 있다는게 장점이라고 생각합니다.

하지만 장점이 있으면 단점이 존재하기 마련이다. 중간에 배열의 요소를 삭제하는 작업을 수행하면 배열의 요소들을 밀어넣는 작업을 하기 때문에 추가적인 비용이 들어갈 수 있다는 점 입니다.
또 한 배열의 생성할때 크기를 정해줘야 하기 때문에 어떤 크기를 가진 데이터가 들어올지 모르는 상황에서는 융통성이 많이 부족한 친구입니다.

배열의 특징

• 검색속도가 빠르다.
• 크기가 고정되어 있다.
• 배열 요소의 추가, 삭제를 하는데 추가적인 오버헤드가 발생한다.

동적 Array

이와 대조적으로 데이터의 크기와 상관없이 융통성 있게 크기를 추가할 수 있는 친구가 있는데… 대표적으로 Linked List라는 녀석이다… 대학교 시절에 C언어를 공부할때 가장 어렵게 느껴져서 대충 들어보기만 했지만 알고리즘 입문(자바편)을 공부하면서 조금 친해질?? 수 있었습니다.

Linked List

Linked List는 노드라고 불리는 작은 메모리 영역안에 데이터 필드와 링크영역이 존재하는데 이 데이터 필드는 실제 데이터 값이 저장되어있고 링크는 다음 노드의 주소 값을 저장하는 공간입니다.

실제로 Linked List라는 개념을 알고리즘 투게더 with 거니라는 Youtube 채널을 보면서 쉽게 이해 할 수 있었습니다. 정적어레이와 동적어레이에 차이에 대해서 자세히 이해가 안간다면 이 채널을 보는 것을 추천드립니다. Linked List 또한 단점이 존재하는데 배열과 다르게 Linked List는 원하는 키 값을 찾기 위해서는 링크를 타야하기 때문에 검색속도가 느리다는 단점이 존재합니다.

마치 학교 선생님이 반에 학생들에게 누가 창문을 깼는지 영희라는 학생에게 물어보면 영희는 철수를 손가락으로 가르키고, 철수는 지수를 가르키는 것처럼 각각의 학생들이 앉아있는 책상 위치가 주소라고하면 링크는 각각의 학생의 책상 위치를 가르킨다고 보면 된다. 하지만 선생님이 결국 누가 창문을 깼는지 알기 위해서는 학생들이 각각 가르키는 손가락을 확인해야 범인을 알 수 있다. 이것도 건희님의 채널을 보고 신박한 비유라고 생각했는데… 설명을 제가 잘 못해서… 이해가 안가시면 맨 아래 해당 유튜브를 참고하시길 바랍니다.

대신에 배열과 다르게 중간의 어떠한 값을 가지고 있는 노드를 삭제한다면 앞에 있는 노드의 링크 주소를 삭제하려는 노드의 뒤쪽 노드의 주소로만 변경해주기만 하면 되기 때문에 추가, 삭제가 용이하다는 장점이 있습니다.

또한 링크 공간이 4byte씩 메모리 공간을 소모하기 때문에 같은 데이터 개수를 저장하는 배열보다는 메모리를 많이 먹는다는… 단점이 있습니다.

Linked List 특징

• 데이터 크기에 의존적이지 않고 융통성 있게 데이터추가 가능
• 키 값을 찾을시에는 링크를 통해서 해당 노드의 값을 찾기 때문에 검색속도가 느리다.
• 앞 뒤 노드들만 연결해주기만 하면 노드의 추가, 삭제가 용이하다.

Linked List의 종류

1. Single Linked List
2. Doubly Linked List
3. Circular Linked List

앞에서 언급한것처럼 노드에는 데이터 필드와 링크라는 영역이 존재하는데, 이 링크의 구조에 따라서 Linked List의 종류가 달라집니다.

위에서 그림은 노드에 링크를 하나씩만 존재하는 Single Linked List 입니다. 가장 많이 본 녀석이죠… 그 다음에 노드에 링크가 2개씩 존재하는 녀석이 Doubly Linked List입니다. 말 그대로 더블이라는 표현에서 보듯이 위의 링크가 다음 노드의 주소를 가지고 있고 아래 링크는 앞의 노드의 주소를 가지고 있어서 서로 연결된 모습을 보입니다.

Doubly Linked List

맨 처음 나오는 노드를 헤더라고 부르고,맨 마지막 노드를 테일이라고 부릅니다. 헤더와 테일은 링크는 null을 가지고 있습니다. 즉 아무것도 가리키고 있지 않습니다.

이제 그 다음에 나오는 Linked List가 환영 연결 리스트라고 불리는 녀석입니다.
마찬가지로 노드당 링크를 2개씩 가지고 있지만 위에 Doubly Linked List랑 구별되는 특징은 헤더와 테일이 서로 연결되어 있다는 특징이 있습니다.

Circular Linked List

헤더의 한쪽 링크는 테일의 주소 값을 가지고 있고,

이제 위의 개념들을 토대로 선형검색 코드를 간단하게 구현해하여 리뷰하겠습니다.

선형 검색

선형탐색은 처음부터 하나하나 비교하여 검색하는 방법으로 구현하기 쉽고, 정렬이 안 되어있어도 된다는 장점이 있습니다. 대신 하나하나 찾으면서 검색하기 때문에 시간이 오래 걸린다는… 단점이 있습니다.

Java언어를 사용하여 배열에 원하는 키 값을 찾는 코드입니다.

public class SeqSearch {

    static int seqSearch(int[] a, int n, int key){
        int i=0;
        a[n] = key; //배열의 마지막 인덱스에 원하는 키값을 넣는다.

        //배열의 크기보다 작거나 같을때까지 반복...
        for(i=0; i<=n; i++){
            if(a[i] == key)  배열의 요소와 키 값이 같으면 for문을 탈출!!
                break;
        }
        return i==n ? -1:i; // i의 값이 배열의 크기와 같다면 -1 리턴, 같지않으면 i를 리턴
    }


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("요솟수: ");

        int num = sc.nextInt();
        int[] x = new int[num+1];  //보초법이라 해서 원하는 배열의 크기 +1만큼 생성합니다.

        for(int i=0; i<num; i++){
            x[i] = sc.nextInt();
        }

        System.out.println("검색할 값: ");
        int key = sc.nextInt();  //키 값을 입력받는다.
        int idx = seqSearch(x, num, key);

        if(idx == -1)  // 배열에 원하는 키 값이 존재하지 않을때 -1을 리턴
            System.out.println("그 값의 요소가 없습니다.");
        else
            System.out.println(key +"은 x[" + idx +"]에 있습니다.");
   }
}

위의 코드는 보초법 방식으로 배열에서 원하는 키 값을 찾는 검색 알고리즘 입니다.
seqSearch 메소드를 유틸성으로 이용하기 위해서 Static 영역에 생성하여 원하는 키값을 찾는 메서드입니다.

원하는 크기의 배열을 선언과 찾고자 하는 키값을 seqSearch() 메서드의 매개변수로 넘겨줍니다.
여기서 배열을 힙 영역에 생성할 때 원하는 크기의 +1 만큼 증가시켰습니다. 왜 이렇게 선언하는 이유는 실제로 보초법을 사용하지 않을시에는 예를들어서 소스코드가 아래와 같다고 한다면

static int seqSearch(int[] a, int n, int key){

   int i = 0;


    while(true){
        if(i == n)
            return -1;
        if(a[i] == key)
            return i;
        i++; 
    }
}

i의 값에 따라서 분기문이 2개로 나뉘게 됩니다.

i == n이 성립하는 경우 (종료 조건1: 검색 실패이므로 -1을 반환)

a[i] == key가 성립하는 경우 (종료조건2: 검색성공이므로 i를 반환)

선형 검색은 반복할 때마다 다음의 종료조건 1과 2를 모두 판단합니다. 단순한 판단이라고 생각할 수 있지만 '티끌모아 태산’이라는 말이 있듯이 종료 조건을 검사하는 비용은 결코 무시할 수 없습니다.
이 비용을 반으로 줄이는 방법이 보초법입니다.

위에서 배열을 원하는 크기의 +1만큼 생성하였습니다. 검색하기 전에 검색하고자 하는 키 값을 맨 끝 요소에 저장합니다. 이때 저장하는 값을 보초라고 합니다.
이렇게 코드를 작성하면 원하는 값이 원래의 데이터에 존재하지 않아도 보초인 마지막 인덱스까지 검색하면 종료가 성립합니다. 이렇게 하면 조건분기인 종료조건1이 없어도 됩니다. 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 합니다.

이진 검색

마지막으로 이진 검색법에 대해 리뷰하겠습니다. 이 알고리즘은 선형탐색과 다르게 반씩 범위를 나누어 가면서 분할정복하여 탐색하는 방법 키 값으로 이미 정렬되어 있다는 것입니다. 이진검색은 선형탐색보다 검색속도가 더 빠르다는 장점이 있습니다.

• 속도가 빠르다
• 자료구조 안 값들이 정렬되어있어야 한다.

예를 들어서 원하는 키 값이 8인경우 (n-1)/2 = 3 a[3] = 12를 기준값으로 잡고 키 값과 비교를 합니다. 키 값이 작기 때문에 a[3]부터 검색 범위를 버리고 (n-1)/2 = 1 a[1] = 3을 기준 값으로 잡습니다. 마찬가지로 8 > 3이기 때문에 a[1]부터 밑에 범위는 버리고 시작하면 남은 인덱스는 a[2]만 남게되고 키 값과 일치하게 되여 해당 인덱스를 리턴하면 됩니다.

이런 방식으로 이진탐색은 검색범위를 계속 좁히면서 원하는 키 값을 찾는 알고리즘 입니다.
그렇기 때문에 속도가 빠를 수 밖에 없습니다. 또 한 검색 범위를 절반씩 좁히기 위해서는 배열요소 값이 정렬되어 있어야 하는 번거로움이 존재하죠…

위의 책 그림은 이진 검색을 이해하는데 좋은 예인거 같아서 첨부하였습니다. 마찬가지로 건이님 채널에서 배웠습니다.ㅎㅎ 넘나 유익한것…

만약 선생님이 총 500 페이지인 국어책의 370페이지를 펼치라고 하였을때 학생들은 대충 절반인 250 페이지를 펼친 다음에 찾고자 하는 페이지와 비교하여 작으면 1250 페이지의 범위는 버리고 250500 페이지의 범위에서 해당페이지를 찾습니다. 이런식으로 범위를 나누어가면서 내가 찾고자하는 패이지를 찾는게 이진탐색 방법입니다. 참 쉽죠잉~

다음에는 이진검색을 Java코드로 살펴보겠습니다.

public class BinarySearch {

    static int binSearch(int[] a, int n, int key){
        int pl = 0;     //배열의 첫번째 요소 a[0]
        int pr = n-1;   //배열의 마지막 요소 a[n-1]

        do{
            int pc = (pl+pr)/2; //배열의 기준값
            if(a[pc] == key)  
                return pc;
            else if(a[pc] < key)
                pl=pc+1;
            else
                pr=pc-1;
        }while(pl<=pr);

        return -1;
    }


     public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("요솟수: ");
        int num = sc.nextInt();

        int[] x = new int[num];
        System.out.println("오름차순으로 입력하세요.");

        System.out.println("x[0] : ");
        x[0] = sc.nextInt();

        //이진검색은 사전조건이 정렬되어 있어야 합니다.
        for(int i=1; i<num; i++){
            do{
                System.out.println("x[" + i +"] : ");
                x[i] = sc.nextInt();
            }while(x[i] < x[i-1]); //배열의 i < i-1번째 요소보다면 작으면 반복
        }

        System.out.println("검색할 값 : ");
        int key = sc.nextInt();

        int idx = binSearch(x, num, key); // 이진검색 메소드

        if(idx == -1)
            System.out.println("그 값의 요소가 없습니다.");
        else{
            System.out.println(key +"은 x[" + idx + "]에 있습니다.");

        }
    }
}

위의 소스코드에서 do while문을 이용하여 오름차순으로 정렬하고 있습니다.
원하는 키 값과 배열의 길이, 배열의 참조 값을 binSearch() 메서드의 매개변수로 넘겨주면서 이진검색을 하고 있습니다. binSearch() 메서드는 파리미터로 받은 키 값과 배열의 첫번째 요소와 마지막 요소를 가지고 있는 로컬변수 pl, pr, pc를 이용하여 기준 값을 구하고 키 값과 기준 값을 비교하며 범위를 절반씩 좁히면서 검색을 수행합니다. 이렇게 좁히다 보면 결국 pl과 pr은 만나게 되고 pl이 pr보다 크거나 같으면 do while문이 종료가 되고 -1을 리턴하여 검색이 실패한걸 알 수가 있습니다.

검색 알고리즘을 정말 모래알 같이 쬐끔… 맛보면서 느낀점은 데이터 크기에 따라서 배열을 사용할지 Linked List를 사용할지… 어느게 더 좋은 자료구조인지 따지기 보다는 매모리 효율에 맞게 사용하는게 가장 최적의 방법이지 않을까… 조심스럽게 생각해봅니다. 아직 가야할 길이… 정말 많이 남았지만 어제보다 더 나아졌다는 마인드로 블로그를 정리하면서 보람을 느낍니다. ㅎㅎ

저에게 Linked List에 대해서 좀 더 쉽게 다가갈수 있도록 도와주신 건이님께 감사의 말씀 올립니다.

참조: YouTube 알고리즘 투게더 with 거니

문제6

우아한테크코스에서는 교육생(이하 크루) 간 소통 시 닉네임을 사용합니다. 간혹 비슷한 닉네임을 정하는 경우가 있는데, 이러할 경우 소통할 때 혼란을 불러일으킬 수 있습니다.

혼란을 막기 위해 크루들의 닉네임 중 같은 글자가 연속적으로 포함 될 경우 해당 닉네임 사용을 제한하려 합니다. 이를 위해 같은 글자가 연속적으로 포함되는 닉네임을 신청한 크루들에게 알려주는 시스템을 만들려고 합니다.
신청받은 닉네임 중 같은 글자가 연속적으로 포함 되는 닉네임을 작성한 지원자의 이메일 목록을 return 하도록 solution 메서드를 완성해주세요.
제한사항

• 두 글자 이상의 문자가 연속적으로 순서에 맞추어 포함되어 있는 경우 중복으로 간주합니다.
• 크루는 1명 이상 10,000명 이하입니다.
• 이메일은 이메일 형식에 부합하며, 전체 길이는 11자 이상 20자 미만입니다.
• 신청할 수 있는 이메일은 email.com 도메인으로만 주어집니다.
• 닉네임은 한글만 가능하고 전체 길이는 1자 이상 20자 미만입니다.
• result는 이메일에 해당하는 부분의 문자열을 오름차순으로 정렬하고 중복은 제거합니다.

forms에는 5명의 크루가 신청서를 작성하였고 이 중 jason@email.com과 jm@email.com, mj@email.com 크루가 중복 닉네임 대상으로 뽑혔습니다. 따라서 이 세 크루의 이메일을 출력합니다.

풀이

package beautifultask;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class NickName {


    public static String[] solution(String[][] forms){

        String[] answer = new String[forms.length];

        HashSet<String> emails = new HashSet<>();

        final Map<String, String > hashMap = new HashMap<>();

        for (int i = 0; i < forms.length; i++) {

            final String name = forms[i][1];

            if(name.length() < 2){
                break;
            }


            for (int j = 0; j < name.length() - 1; j++) {
                final String key = name.substring(j, j+2);
                if(hashMap.containsKey(key)){
                    final String email = hashMap.get(key);
                    if(!email.equals(forms[i][0])){
                        emails.add(email);
                        emails.add(forms[i][0]);
                    }
                }
                hashMap.put(key, forms[i][0]);
            }
        }

        final List<String> collect = emails.stream()
                .sorted()
                .collect(Collectors.toList());
                   //List size가 인자로 넘어가는 배열 객체의 size 보다 클때, 해당 List의 size로 배열이 만들어집니다.
            //반대로 해당 List size가 인자로 넘어가는 배열객체의 size 보다 작을때는, 인자로 넘어가는 배열객체의 size로 배열이 만들어집니다.
        final String[] results = collect.toArray(new String[0]);

        return results;
    }

    public static void main(String[] args) {


        String[][] forms ={{"jm@email.com", "제이엠"},{"jason@email.com","제이슨"},{"woniee@email.com","워니"},{"mj@email.com","엠제이"},{"nowm@email.com","이제엠"}};


        String[] result = solution(forms);

        for (String value : result)
            System.out.println(value);


    }

}

우아한테스크코스 온라인 코딩 테스트 6번 문제입니다. 후반부 문제이지만 연속된 2자리 닉네임을 체크하는데 많은 고민을 하였습니다. 이 문제는 친구의 풀이를 보고 참조하였습니다.
결국 중복된 2글자가 겹치는 닉네임이 있으면 그 닉네임에 해당되는 이메일들을 가지고 있는 정렬된 문자열 배열을 리턴하는 것이 핀트입니다.

forms라는 2차원 배열에 이메일, 닉네임이 각각 들어있습니다. 저같은 경우에 HashSet, HashMap 클래스를 이용하여 중복체크를 하였습니다.

for (int j = 0; j < name.length() - 1; j++) {
    final String key = name.substring(j, j+2);
    if(hashMap.containsKey(key)){
        final String email = hashMap.get(key);
        if(!email.equals(forms[i][0])){
            emails.add(email);
            emails.add(forms[i][0]);
        }
    }
    hashMap.put(key, forms[i][0]);
}

문제4

배달 앱을 이용하려면 유저는 로그인 → 장바구니에 음식 담기 → 주문 과 같은 순서를 거칩니다. 이를 위해 서버에서는 다음과 같은 일을 합니다.

1. 로그인: LOGIN 아이디 비밀번호

   • 이미 로그인했다면 거부한다.
   • 아이디와 비밀번호가 유효하면 로그인을 허용한다.
   • 아이디와 비밀번호가 유효하지 않으면(아이디가 없거나 비밀번호가 다른 경우) 로그인을 거부한다.

2. 장바구니에 음식 담기: ADD 음식아이디

   • 로그인한 유저라면 허용한다.
   • 로그인하지 않았으면 거부한다.

3. 주문하기: ORDER

   • 장바구니에 담은 음식이 있으면 허용한다. 주문 후에는 장바구니를 비운다.
   • 장바구니에 담은 음식이 없으면 거부한다.
     서버에 저장된 유저 정보 infos와 한 사람의 행동을 담은 배열 actions가 매개변수로 주어질 때, 각 행동이 허용되었으면 true, 거부되었으면 false를 담아 return 하도록 solution 메서드를 완성해주세요.

제한 사항

• infos의 길이는 1 이상 10 이하입니다.
• infos의 원소는 아이디 비밀번호 형태입니다.
• actions의 길이는 1 이상 100 이하입니다.
• actions의 원소는 다음 형태 중 하나입니다.
  • LOGIN 아이디 비밀번호
  • ADD 음식아이디
  • ORDER
• infos와 actions 배열에서 주어지는 아이디와 비밀번호는 영문 소문자로만 이루어져 있습니다.
• actions 배열에서 주어지는 음식아이디는 숫자로만 주어집니다.

풀이

package beautifultask;

import java.util.*;

public class DeliveryProcess {

    public static boolean[] solution(String[] infos, String[] actions) {

        boolean[] answer = new boolean[actions.length];
        Member member = null;

        Map<String, Member> accounts = new HashMap<>();

        // 서버에 저장된 사용자 정보를 해시 Map 객체로 관리합니다.
        // Key 값은 회원 아이디로 회원 객체를 관리합니다.
        for (int i = 0; i < infos.length; i++) {
            String[] memberInfo = infos[i].split(" ");
            accounts.put(memberInfo[0], new Member(memberInfo[0], memberInfo[1]));
        }

        for (int i = 0; i < actions.length; i++) {
            String[] request = actions[i].split(" ");

            switch (request[0]) {
                case "ADD":
                    if (member != null) {
                        member.addFood(request[1]);
                        answer[i] = true;
                    } else {
                        answer[i] = false;
                    }
                    break;

                case "LOGIN":
                    boolean loginResult = getLoginResult(request, member, accounts);
                    if(loginResult) {
                        member = accounts.get(request[1]);
                    }
                    answer[i] = loginResult;
                    break;

                case "ORDER":
                    if(member == null){
                        answer[i] = false;
                    }else{
                       if(member.getCart().size() == 0){
                           answer[i] = false;
                       }else {
                           member.clearCart();
                           answer[i] = true;
                       }
                    }
                    break;

                    default:
                        throw new IllegalStateException("IllegalArgumentException");
            }
        }
        return answer;
    }

    //memberInfo = member 정보가 있습니다.
    public static boolean getLoginResult(String[] request, Member member, Map<String, Member> accounts){

        if(!accounts.containsKey(request[1])){
            return false;
        }

        final Member accountMember = accounts.get(request[1]);

        if(!accountMember.getPassword().equals(request[2])){
            return false;
        }

        if(member != null){
            return false;
        }

        return true;
    }


    public static void main(String[] args) {

        String[] infos = {"kim password", "lee abc"};
        String[] actions = {
                "ADD 30",
                "LOGIN kim abc",
                "LOGIN lee password",
                "LOGIN kim password",
                "LOGIN kim password",
                "ADD 30",
                "ORDER",
                "ORDER",
                "ADD 40",
                "ADD 50"};

        boolean[] result = solution(infos, actions);

        for (boolean answer : result) {
            System.out.println(answer);
        }


    }

}


class Member {

    private String id;
    private String password;
    // HashSet 클래스는 중복을 거르고 담기 때문에 식별자가 유일한 개체만 담습니다.
    private HashSet<String> cart = new HashSet<>();


    public Member(String id, String password) {
        this.id = id;
        this.password = password;
    }


    public void addFood(String foodId) {
        cart.add(foodId);
    }

    public void clearCart() {
        cart.clear();
    }


    public HashSet<String> getCart() {
        return cart;
    }

    public String getPassword() {
        return password;
    }
}

우아한테스크코스 온라인 코딩 테스트 4번 문제는 배달앱 주문과정을 구현하는 것입니다.
위에 나와있는 룰에 기반하여 행동이 들어있는 문자열 타입의 배열을 받아서 허용할지 거부할지 판단하여 boolean 타입의 배열을 리턴하는 것이 핵심입니다.

가장 먼저, 서버에 저장된 회원의 아이디와 패스워드 정보가 들어있는 infos 배열을 각각의 HashMap 클래스를 사용하여 Member 객체의 생성자 로 넣어주어 관리하도록 하였습니다.

for (int i = 0; i < infos.length; i++) {
    String[] memberInfo = infos[i].split(" ");
    accounts.put(memberInfo[0], new Member(memberInfo[0], memberInfo[1]));
}

이 문제를 자세히 살펴보면 행동이 담긴 문자열 배열의 값이 ADD 데이터, LOGIN 데이터, ORDER 데이터 으로 구성되어 있는데 뒤에 나오는 데이터는 공백으로 구분되어 있습니다. 이것을 split() 메서드를 사용하여 공백으로 문자열을 자른 후에 각각의 행동을 처리하도록 swich문을 이용하여 해결하였습니다.

public static boolean getLoginResult(String[] request, Member member, Map<String, Member> accounts){

    if(!accounts.containsKey(request[1])){
        return false;
    }

    final Member accountMember = accounts.get(request[1]);

    if(!accountMember.getPassword().equals(request[2])){
        return false;
    }

    if(member != null){
        return false;
    }

    return true;
}

위의코드는 행동이 LOGIN일때 처리하는 부분입니다.
이미 로그인한 회원이 있으면 false, Map 객체에 containsKey() 메서드로 아이디가 존재하는지 확인하고 없으면 마찬가지로 false, 아이디가 존재하지만 패스워드가 틀리면 false를 리턴하도록 작성하였습니다. 이 세가지 조건을 다 충족하지 않는다면 로그인한 유저가 없거나 아이디, 패스워드가 서버에 저장된 정보랑 일치하는걸로 판단하여 true를 리턴합니다.

그리고 member 객체는 로그인 정보가 들어있는 행동 배열 값이랑 일치하기 때문에 로그인하도록 처리하였습니다.

문제 설명

접속자가 많을 때는 서버를 많이, 접속자가 적을 때에는 서버를 적게 띄워야 합니다. 배달의 민족에서는 각 시간대에 발생한 로그 수를 파악해 미래에 서버를 몇 대 띄울지 계산하려 합니다. 로그는 YYYY/MM/DD hh:mm:ss 형식으로 표시되며, 한국은 UTC+09:00 시간대이므로 로그에 표시된 시각에서 9시를 더해야 올바른 한국 시각이 나옵니다.

예를 들어 2019/10/01 09:33:19 로그는 한국 기준, 2019년 10월 1일 18시 33분 19초에 발생한 로그입니다.
로그 발생 시각을 담은 문자열 logs가 매개변수로 주어졌을 때 0시부터 23시까지, 한국 시간 기준 각 시간대별로 로그가 몇 회씩 발생했는지 return 하도록 메서드를 완성해주세요.

제한 사항

• 발생 시각은 개행(\n) 문자로 구분되어있습니다.
• 발생 시각은 10개 이상 100개 이하로 주어집니다.
• 발생 시각은 YYYY/MM/DD hh:mm:ss 형식이며 24시 표시법을 따릅니다.
• 연도는 2011 이상 2019 이하 값으로만 주어집니다.
• 잘못된 시각이 주어지는 경우(-1년 13월 55일 25시 82분 400초 등)는 없습니다.

풀이

package beautifultask;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.Arrays;

public class PrintLogNumber {

    public static int[] solution(String[] input) {

        int[] hours = new int[24];
        Arrays.fill(hours, 0);

        DateTimeFormatter pattern = DateTimeFormatter.ofPattern("yyyy/MM/dd HH:mm:ss");

        for (int i = 0; i < input.length; i++) {

            final LocalDateTime parser = LocalDateTime.parse(input[i], pattern);

            // 시간 정보만 가져옵니다.
            int hour = parser.getHour() + 9;
            hours[hour] += 1;
        }

        return hours;
    }


    public static void main(String[] args) {

        String log = "2019/05/01 00:59:19\n" +
                "2019/06/01 01:35:20\n" +
                "2019/08/01 02:01:22\n" +
                "2019/08/01 02:01:23\n" +
                "2019/08/02 03:02:35\n" +
                "2019/10/03 04:05:40\n" +
                "2019/10/04 06:23:10\n" +
                "2019/10/10 08:23:20\n" +
                "2019/10/12 08:42:24\n" +
                "2019/10/23 08:43:26\n" +
                "2019/11/14 08:43:29\n" +
                "2019/11/01 10:19:02\n" +
                "2019/12/01 11:23:10\n";

        String[] input = log.split("\n");

        int[] result = solution(input);

        for (int value : result) {
            System.out.println(value);
        }

    }
}

어제 우아한테스크코스 온라인 코딩 테스트에서 나온 2번 문제입니다. 한국 시간 기준 각 시간대별로 로그가 몇 회씩 발생했는지 배열 타입으로 return 하는 것이 핀트입니다.

이 문제를 분석하면서 출제자의 의도를 분석을 해보면서 해당 날짜 관련 데이터에서 얼마나 잘 핸들링 할 수 있는지 파악하는것이 목적이 아닐까.. 조심스럽게 생각해봤습니다.
평상시에 날짜, 시간과 관련된 객체를 다루어 본 경험이 있으시다면 그렇게 어렵지 않는 문제였습니다.

먼저, 문자열 변수에 들어있는 날짜 데이터들을 \n을 구분자로 문자열 타입 배열로 변환해주고 처리하는게 가장 처리하기 쉬운거 같습니다.

두번째로는 아래와 같이 java.time.format 패키지에서 제공해주는 DateTimeFormatter 클래스를 사용하여 ofPattern 메서드로 출력형식으로 원하는 날짜 포맷을 지정해줍니다.

DateTimeFormatter pattern = DateTimeFormatter.ofPattern("yyyy/MM/dd HH:mm:ss"); 

주의사항: yyyy/MM 은 대소문자 구분 없이 연,월을 표현하지만, dd,HH,ss는 대소문자에 따라 출력형식이 달라집니다.
DD는 년의 몇 번째 일(1 ~366), dd는 월의 몇 번째 일(1~31), HH는 시간(0~23), hh 시간(1~12), SS(1/1000초) ss는 초(0~59)를 의미합니다.

마지막으로 자바 1.8부터 제공해주는 날짜와 관련된 클래스인 LocalDateTime 객체의 parse() 메서드를 사용하여 날짜 데이터가 들어있는 문자열 타입의 배열을 꺼내와서 이전에 DateTimeFormatter으로 지정한 출력형식으로 파싱을 하여 LocalDateTime 객체를 얻어옵니다.

LocalDateTime parser = LocalDateTime.parse(input[i], pattern);

이제 날짜, 시간 등 원하는 대로 처리 할 수 있습니다.

아래는 자바 1.8 버전부터 제공해주는 날짜 관련 객체와 메소드에 대한 정보가 나와있는 참조 사이트입니다. 아래 개발자분들이 올려주신 정보는 저에게 정말 많은 도움이 되었습니다.

참조: https://lovefields.github.io/java/2017/06/15/post76.html, https://jekalmin.tistory.com/entry/%EC%9E%90%EB%B0%94-18-%EB%82%A0%EC%A7%9C-%EC%A0%95%EB%A6%AC

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1의 문자 u, e, a로 strings를 정렬합니다.

제한 조건

1. strings는 길이 1 이상, 50이하인 배열입니다.
2. strings의 원소는 소문자 알파벳으로 이루어져 있습니다.
3. strings의 원소는 길이 1 이상, 100이하인 문자열입니다.
4. 모든 strings의 원소의 길이는 n보다 큽니다.
5. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

입출력 예 설명

입출력 예 1

sun, bed, car의 1번째 인덱스 값은 각각 u, e, a 입니다. 이를 기준으로 strings를 정렬하면 [car, bed, sun] 입니다.

입출력 예 2

abce와 abcd, cdx의 2번째 인덱스 값은 c, c, x입니다. 따라서 정렬 후에는 cdx가 가장 뒤에 위치합니다. abce와 abcd는 사전순으로 정렬하면 abcd가 우선하므로, 답은 [abcd, abce, cdx] 입니다.

package jungja_study;

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

public class StringSorting {

    public static String[] solution(String[] words, int n) {

        int length = words.length;
        String[] alpa = new String[length];
        String[] answer = new String[length];
        List<String> list = new ArrayList<>();

        // words 배열의 n번째 인덱스에 해당하는 문자를 alpa 배열에 대입
        for (int i = 0; i < words.length; i++) {
            alpa[i] = String.valueOf(words[i].charAt(n));
        }
        // words 배열 각각의 요소의 n번째 인덱스의 문자가 같은 경우에 사전순으로 앞선 문자열로 정렬해야합니다.
        // 따라서 미리 정렬을 통해서 나중에 정렬된 alpa 배열과 비교하여 찾을때 따로 사전순으로 앞선 정렬 처리를 할 필요가 없어집니다.
        Arrays.sort(words);
        //words 배열의 n번째 인덱스에 해당하는 문자를
        Arrays.sort(alpa);


        //정렬된 alpa 배열과 words 배열을 비교하여 words서 배열 정수 n 값에 따라 컬렉션타입의 리스트 객체에 저장합니다.
        for (int i = 0; i < alpa.length; i++) {
            for (int j = 0; j < words.length; j++) {
                if(alpa[i].equals(String.valueOf(words[j].charAt(n)))){
                    if (!list.contains(words[j])) {
                        list.add(words[j]);
                    }
                }
            }
        }


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

        return answer;
    }

    public static void main(String[] args) {

        String[] testCase1 = {"sun", "bed", "car"};
        String[] testCase2 = {"abce", "abcd", "cdx"};

        String[] result1 = solution(testCase1, 1);
        String[] result2 = solution(testCase2, 2);


        for (String s : result1) {
            System.out.println(s);
        }

        for (String s : result2) {
            System.out.println(s);
        }
    }
}

이 문제는 문자열 처리 능력을 묻는 문제로 chartAt와 String.valueOf, Arrays.sort 메소드를 활용하여 풀었습니다. 난이도는 그렇게 어려운 편은 아니였지만 아무래도 제 수준에서 그나마 까다로웠던 조건이 인덱스 1의 문자가 같은 문자열일 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치해야하는 조건에서 좀 생각을 깊게 했었던거 같습니다.

이 부분은 단순하게 미리 Arrays.sort()로 주어진 배열을 사전순으로 정렬한 후에 n번째 인덱스에 해당하는 문자만 들어있는 배열 alpa와 비교를 통해 같은 것만 컬렉션 타입의 객체에 넣어주면 되는 문제입니다.

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

1. phone_book의 길이는 1 이상 1,000,000 이하입니다.
2. 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

package jungja_study;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class PhoneNumberList {

    public boolean solutionh(String[] phone_book) {

        boolean answer = true;
        Map<Integer, String> map = new HashMap<>();

        Arrays.sort(phone_book);

        for (int i = 0; i < phone_book.length; i++) {
            map.put(i, phone_book[i]);
        }

        for (int i = 0; i < phone_book.length; i++) {
            System.out.println(map.get(i));
        }


        for (int i = 0; i < map.size() - 1; i++) {
            if (map.get(i).length() < map.get(i + 1).length()) {
                if (map.get(i + 1).startsWith(map.get(i))) {
                    answer = false;
                    break;
                }
            }
        }

        return answer;
    }


    public static void main(String[] args) {

        PhoneNumberList phoneNumberList = new PhoneNumberList();
        String[] phone_book = {"119", "97674223", "1195524421"};
        String[] phone_book2 = {"123", "456", "789"};
        String[] phone_book3 = {"12", "123", "1235", "567", "88"};
        System.out.println(phoneNumberList.solutionh(phone_book));
        System.out.println(phoneNumberList.solutionh(phone_book2));
        System.out.println(phoneNumberList.solutionh(phone_book3));

    }
}

사실 해시 관련 문제이기 대문에 해시로 엮어서 풀려고 많은 생각을 했지만... 테스트 케이스 7,8에서 계속 에러가 발생하여서.. 다른 풀이의 답을 참조하게 되었습니다. 하지만 대부분 풀이를 보면 해시를 사용하기 보다는 정렬을 이용해서 문자열 메소드 startWith를 이용하여 푸는게 가장 깔끔하게 풀어집니다. 이 문제의 핵심은 전화번호가 들어가 있는 phone_number 배열에서 각각의 전화번호가 다른 인덱스에 있는 전화번호의 접두사인지 확인하여 false, true 둘 중에 하나를 리턴하면 되는 문제입니다.

저 같은 경우에는 HashMap 객체를 이용하여 전화번호 목록에 있는 번호들을 넣었지만, 사실 여기서 가장 핵심은 Arrays.sort() 정렬 메소드 입니다. 굳이 해시를 이용하지 않아도 간단하게.. 풀리는 문제였습니다.
sort() 메소드로 전화번호 목록이 담긴 배열을 넣으면 사전식으로 정렬이 되기 때문에 어떤 전화번호의 접두사가 되는 전화번호가 앞 순서에 위치하게 되기 때문에 정렬된 전화번호 리스트를 순회하여 다음에 오는 전화번호가 현재 전화번호로 시작하는지 체크를 해주면 됩니다.

프로그래머스에서 Best Practice를 보면 정렬없이 아래와 같이 풀수도 있습니다.

for(int i=0; i<phone_book.length-1; i++) {
    for(int j=i+1; j<phone_book.length; j++) {
        if(phone_book[i].startsWith(phone_book[j])) {return false;}
        if(phone_book[j].startsWith(phone_book[i])) {return false;}

    }
}

위와 같은 방식으로 풀면 문자열 길이를 체크하지 않고 순회하며 비교가 가능합니다.