본문 바로가기
블로그 이미지

방문해 주셔서 감사합니다! 항상 행복하세요!

  
   - 문의사항은 메일 또는 댓글로 언제든 연락주세요.
   - "해줘","답 내놔" 같은 질문은 답변드리지 않습니다.
   - 메일주소 : lts06069@naver.com


Java(자바)/코딩 테스트 & 알고리즘

3. 위장(프로그래머스, 해시 Level 3)

야근없는 행복한 삶을 위해 ~
by 마샤와 곰 2020. 8. 21.

* 문제 설명
 - 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다.
 - 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다.
 - 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

* 제한사항
 - clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
 - 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
 - 같은 이름을 가진 의상은 존재하지 않습니다.
 - clothes의 모든 원소는 문자열로 이루어져 있습니다.
 - 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.
 - 스파이는 하루에 최소 한 개의 의상은 입습니다.

 

 

문제를 이해하는 데 시간이 좀 걸렸던 것 같습니다.

아래 테스트 케이스를 살펴봅니다. 기존의 내용에서 키(key) 값 역할을 할 대상을 한글로 바꾸었습니다.

[["yellow_hat", "헤드"], ["blue_sunglasses", "눈"], ["green_turban", "헤드"]]

 

위 같은 값이 존재하면 "헤드"는 2개의 값으로 표현이 되고, "눈"은 1개의 값으로 표현이 됩니다.

데이터를 바탕으로 존재하는 가짓수를 구하면 총 5가지로 표현 할 수 있습니다.

- 헤드 : yellow_hat

- 헤드 : green_turban

- 눈 : blue_sunglasses

- 둘다(헤드+눈) : yellow_hat, blue_sunglasses

- 둘다(헤드+눈) : green_turban, blue_sunglasses

 

위 결과를 토대로 경우의 수를 판단하여 봅니다.

헤드를 선택하는 경우는 2개이며 선택하지 않는 경우는 1개 입니다.

눈의 갯수는 1개이며 선택하지 않는 경우는 1개 입니다.

 

중학교 2학년 때 배우는 경우의 수를 구하는 방법은 합의 법칙과 곱의 법칙이 있습니다.

합의 법칙은 or인 경우에 사용되고, 곱의 법칙은 and인 경우에 사용 됩니다.

위 경우는 헤드와 눈의 경우가 and로 이루어지기 때문으로 곱의 법칙을 사용해야 합니다.

 

* 헤드(2개 + 1개) * 눈(1개 + 1개) = 6개

 

선택되지 않는 경우를 각각의 대상(헤드, 눈)에 대해서 적용하였으므로 나온 결과에서도 선택하지 않는 경우를 빼 주면 완성입니다.

 

* 헤드(2개 + 1개) * 눈(1개 + 1개) = 6개

* 6개 - 1개(선택되지 않는 경우) = 5개

 

그러면 위 내용을 바탕으로 코드를 만들어 보겠습니다.

먼저 2중 배열의 값을 key와 value로 분리하여 보겠습니다.

아마도, Java8의 기능을 사용하면 Collectors를 활용하면 조금 더 쉽게 가능 할 것 같습니다.

public static int solution(String[][] clothes) {
    int answer = 0;
    HashMap<String, ArrayList<String>> item = new HashMap<>();
    for(String arg[] : clothes){
        String key = arg[1];  //키 값
        ArrayList<String> list = item.get(key);
        if(item.get(key) == null){  //키값이 없으면
            list = new ArrayList<>();
            list.add(arg[0]);
            item.put(arg[1], list);	
        } else {  //있으면
            list.add(arg[0]);
            item.put(arg[1], list);
        }
    }
}

 

들어온 데이터를 반복문을 통해서 HashMap에 담아두었습니다.

이렇게 하면 key값을 중심으로 List데이터가 쌓이게 됩니다.

List데이터가 바로 가짓수 입니다.

그러면 이제 가짓수 + 선택되지 않는수를 더한 뒤에 곱해보도록 하겠습니다.

public static int solution(String[][] clothes) {
    int answer = 0;
    HashMap<String, ArrayList<String>> item = new HashMap<>();
    for(String arg[] : clothes){
        String key = arg[1];  //키 값
        ArrayList<String> list = item.get(key);
        if(item.get(key) == null){  //키값이 없으면
            list = new ArrayList<>();
            list.add(arg[0]);
            item.put(arg[1], list);	
        } else {  //있으면
            list.add(arg[0]);
            item.put(arg[1], list);
        }
    }

    for( String key : item.keySet() ){
        int miniCase = item.get(key).size()+1;  //선택하지 않는 경우 1개를 더한다.
        if(answer == 0){  //처음 값 이면
            answer = miniCase;
        }else {  //처음 이후의 값 이면 곱해준다.
            answer = answer * miniCase;
        }
    }    
}

 

그리고 마지막으로 나온 값에서 1을 빼 주도록 합니다.

여태것 선택되지 않는 경우를 1개씩 전부 더했으므로 총 갯수에서도 선택되지 않는 값을 빼 주어야 하기 때문 입니다.

public static int solution(String[][] clothes) {
    int answer = 0;
    HashMap<String, ArrayList<String>> item = new HashMap<>();
    for(String arg[] : clothes){
        String key = arg[1];  //키 값
        ArrayList<String> list = item.get(key);
        if(item.get(key) == null){  //키값이 없으면
            list = new ArrayList<>();
            list.add(arg[0]);
            item.put(arg[1], list);	
        } else {  //있으면
            list.add(arg[0]);
            item.put(arg[1], list);
        }
    }

    for( String key : item.keySet() ){
        int miniCase = item.get(key).size()+1;  //선택하지 않는 경우 1개를 더한다.
        if(answer == 0){  //처음 값 이면
            answer = miniCase;
        }else {  //처음 이후의 값 이면 곱해준다.
            answer = answer * miniCase;
        }
    }    
    return answer - 1;  //결과 반환
}

 

이를 제출하면..

통과했다!

 

테스트 케이스가 이렇게 많을줄 몰랐습니다.

이상없이 코드가 잘 작동하는 것을 볼 수 있습니다.

"다른 사람의 풀이" 에서 Java 8의 기능을 멋지게 발휘하신 코드가 가장 좋은 평가를 받은 것을 보고 정말 감탄하였습니다.

다음 과제인 "베스트엘범" 에서도 열심히 해 보아야 하겠습니다. +ㅅ+

반응형
* 위 에니메이션은 Html의 캔버스(canvas)기반으로 동작하는 기능 입니다. Html 캔버스 튜토리얼 도 한번 살펴보세요~ :)
* 직접 만든 Html 캔버스 애니메이션 도 한번 살펴보세요~ :)

댓글