1. 문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.

예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

 

2. 제한사항

  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

3. 입출력 예

numbers target return
[1, 1, 1, 1, 1] 3 5

 

 

4. 문제를 보고 가진 생각 정리

위 문제는 5개수를 모두 사용하여 나올 수 있는 경우의 수를 생각하여야 한다. 위 테스트 케이스 기준 나올 수 있는 총 경우의 수는 2^5로 32개이다. 이 경우의 수를 이진 그래프로 나타내보았다.

 

모든 경우의 수를 표현하려면 그림이 너무 커져서 2개의 수에 대해서만 생각을 해보았다. 문제 예시처럼 5개의 수가 주어진다면, 깊이가 5인 곳에서의 모든 경우의 수에 대한 합을 구하여 target과 일치하는 로직으로 풀이를 하면 될 것이라고 생각하였다. 또한, 깊이 우선으로 탐색을 하여야 하기 때문에, 함수에서 함수를 호출하는 재귀 함수를 선택하기로 하였다. 

 

 

5, 풀이 코드

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
    	//4번의 그림에서 start와 같은 로직
        search(numbers, target, 0);
        return answer;
    }
    
    public void search(int[] numbers, int target, int depth){
    
    	//입력된 numbers의 length까지 탐색을 완료하였을 경우, 배열의 합을 구하여 target과 비교
        if(numbers.length == depth){
            int sum=0;
            for(int i=0;i<numbers.length;i++){
                sum+=numbers[i];
            }
            if(sum==target)
                answer++;
        //탐색이 완료되지 않았다면, 다음 depth에 해당하는 탐색을 진행한다.
        //numbers에서 제공된 수가 양수일 수도 있고, 음수일 수도 있기 때문에 두 경우에 대해 탐색 진행.
        }else{
            search(numbers, target, depth+1);
            numbers[depth]*=-1;
            search(numbers, target, depth+1);
        }
    }
}

'IT > Algorithm' 카테고리의 다른 글

[프로그래머스] 타겟 넘버  (0) 2020.05.07
[프로그래머스] 완주하지 못한 선수  (0) 2020.04.29

1. 문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

 

 

2. 제한사항

  • 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
  • completion의 길이는 participant의 길이보다 1 작습니다.
  • 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
  • 참가자 중에는 동명이인이 있을 수 있습니다.

 

 

3. 입출력 예

participant completion return
[leo, kiki, eden] [eden, kiki] leo
[marina, josipa, nikola, vinko, filipa] [josipa, filipa, marina, nikola] vinko
[mislav, stanko, mislav, ana] [stanko, ana, mislav] mislav

 

 

 

4. 입출력 예 설명

예제 #1
leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

 

5. 문제 해석 및 회고

위 문제는 배열을 비교하여 participant 배열에는 없는 것을 찾는 문제였다. 지금까지 C++위주로 학습하다 JAVA로 풀이하려니 JAVA 자료형에 대한 이해가 부족한 것을 많이 느꼈다. 다음은 내가 몰랐던 부분이거나, 짚고 넘어가야 할 부분이다.

 

  • Java에서 Map 자료형은 같은 key가 입력될때, 기존 값을 덮어쓰기 해버린다
  • String[] 자료형과 ArrayList자료형의 길이(사이즈)를 구할때는 각각 .length와 .size()를 사용한다.
  • Map자료형을 탐색시, Iterator를 사용하여 키 값을 기준으로 탐색이 가능하다.

맨 처음 풀때는, string값 하나하나를 .equals()로 비교하다보니 정답은 나왔지만 효율성에서 매우 꽝이었다. 효율성을 위해 고민한 결과, 탐색시, 나왔던 값과 나오지 않은 값에 대한 판단을 HashMap에 <key, value>로 담아 관리하게 되면 string 비교를 하지 않고 등장 횟수 처리를 통해 조금 더 효율적으로 처리할 수 있을 것이라 판단했다.

위 생각을 확장하면, 데이터가 모두 다른 사람으로 주어진다면, 0 or 1로 처리가 가능하다. 그러나 이 문제는 동명이인이 있을 수 있기 때문에, 이에 대한 처리도 필요하였다. 그래서 달릴 거리가 남아 있는 상태를 1 이상의 수, 완주하여 complete한 상태를 0으로 하여 문제를 풀기로 마음먹었다. 풀이 코드는 다음과 같다.

 

 

 

 

6. 풀이 코드

import java.util.Map;
import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public String solution(String[] participant, String[] completion) {

        String answer = new String();
        Map<String, Integer> map = new HashMap<>();
        
        //마라톤 참가자의 map 등록, 동명이인은 1번 더 같은 거리를 뛰는 것으로 간주하고, 동일인 취급.
        for(int i=0;i<participant.length;i++){
            if(map.get(participant[i])==null){
                map.put(participant[i], 1);
            }else{
                map.put(participant[i], map.get(participant[i])+1);
            }
        }
        
        //완주자는 완주거리에 대한 값 빼줌.
        for(int i=0;i<completion.length;i++){
                map.put(completion[i], map.get(completion[i])-1);
        }

		//아직 뛸 거리가 남은 사람을 탐색한다.
        //완주할 거리가 남아있으면, 1이상의 값을 나타낸다.
        //완주 하였으면 더이상 뛸 거리가 없으므로 0으로 표기한다.
        Iterator<String> iter = map.keySet().iterator();
        while(iter.hasNext()){
            answer = iter.next();
            //완주하지 못한 사람이 걸리면 바로 값을 return 한다.
            if(map.get(answer)!=0){
                return answer;
            }
        }
        
        //while문에 안걸리면 마지막 Map 원소의 key값이 덜 뛴 사람이다.
        return answer;
    }
}

 

 

 

 

7. 출처

https://programmers.co.kr/learn/courses/30/lessons/42576

'IT > Algorithm' 카테고리의 다른 글

[프로그래머스] 타겟 넘버  (0) 2020.05.07
[프로그래머스] 완주하지 못한 선수  (0) 2020.04.29

1. Create

  • URL : <domain>/<version>/user
  • Method : POST
  • Request Header
    • Content-Type: application/json
  • Request Body (format = JsonObject)
    • Userinfo(userid, username, password, email, phone_number, address,  ... ) - JsonObject
    • secretHash HMAC(signing_key(clientSecret, sha256)[clientId + username]) - String
  • Response

    • If success, 
    • If failed, response is HTTP status code with customed error message

 

2. Read

  • URL : <domain>/<version>/user/me
  • Method : GET or POST
  • Request Header :
    • Authorization: Bearer <YOUR_ACCESS_TOKEN>
  • Response
    • If success, response is HTTP status code with userinfo that matched with access token.
    • If failed, response is HTTP status code with customed error message.

2.1. Read by List

  • URL : <domain>/<version>/users
  • Method : GET or POST
  • Request Header : 
    • Authorization: Bearer <YOUR_ACCESS_TOKEN>
    • Content-Type: application/json
  • Request Body
    • Query Parameters - JsonObject

 

 

 

3. Update(덮어쓰기? 부분업데이트?)

  • URL : <domain>/<version>/user/me
  • Method : PUT
  • Request Header
    • Authorization: Bearer <YOUR_ACCESS_TOKEN>
    • Content-Type: application/json
  • Request Body
    • Updated UserInfo - JsonObject
  • Response
    • If Success, return requester's id
    • If failed, response is HTTP status code with customed error message.

 

 

 

4. Delete

  • URL : <domain>/<version>/user/me
  • Method : DELETE
  • Request Header
    • Authorization: Bearer <YOUR_ACCESS_TOKEN>
  • Response
    • If Success, return customed message that user delete is completed.
    • If failed, return HTTP status code with customed error message.

 

 

 

 

 

5. User Table

  • DB : mysql
  • Storage Engine : InnoDB (Transaction이 많이 일어나기 때문에 MyISAM보다 InnoDB가 유리)
  • Schema : portal_user 
  • 향후 잘못되었다 판단한 부분은 빨간색으로 표시

 

Column Type Nullable PK 설명
id varchar(255)    O 사용자 고유 식별자
name varchar(50)     사용자 이름
email varchar(100)     사용자 이메일
authorities varchar(255) → ????     권한 → 역할의 조합이므로, 테이블을 따로 빼서 관리한다.
password varchar(255)     암호화된 비밀번호
role varchar(30) → ????     역할 → 권한에 종속되는 개념이므로, 정규화가 필요함.
last_logined_date datetime     마지막 로그인된 날짜 및 시간
account_create_date datetime     계정 생성 날짜
account_last_update_date datetime     마지막 계정 정보 수정 날짜 → 로그성임. 
credential_last_update_date datetime     비밀번호 마지막 변경 날짜 → 바로 밑 항목과 비슷한 성격이다.
비밀번호 만료일을 가지고 계산할 수 있는 항목임.
credential_expire_date datetime     비밀번호 만료일 → last update를 이 컬럼으로 대체 할 수 있음.
is_account_enabled bit(1)     계정 활성화 여부
is_account_locked bit(1)     계정 잠금 여부
is_credential_expired bit(1)     비밀번호 만료 여부 → 이 컬럼이 필요한가?
is_account_expired bit(1)     계정 만료 여부 (spring security isEnabled()와 매칭되는 column)

 

 

 

5.1. DB Table 설계시, 참고자료

https://github.com/spring-projects/spring-security/blob/master/core/src/main/java/org/springframework/security/core/userdetails/UserDetails.java

 

 

5.2. 찾은 문제점

  • Spring Security의 Default UserDetails를 보고 필드를 설계를 하였으나, 설계한 필드들이 "왜"쓰이는 필드들인지 이해를 하지 못하였다.
  • 오버헤드가 걸리지 않는 선에서 충분히 credential expire date에 대해 판별할 수 있지만, credential_expire_date와 is_credential_expired와 같은 중복케이스가 첫 설계시 존재했다.
  • 데이터에 비해 불필요하게 크기를 잡았다. 불필요한 데이터 크기 설계는 자제하도록 하자.
  • mysql 데이터 타입을 잘 모르다 보니 효율적인 데이터 타입에 대한 선택을 하지 못했다.
  • 정규화를 하지 못했다.

 

 

 

6. 20200423 개선된 DB 설계

 

6.1. User Schema

Column Type Nullable PK 설명
id varchar(20)    O 사용자 고유 식별자
name varchar(10)     사용자 이름
email varchar(30)     사용자 이메일
password varchar(255)     암호화된 비밀번호
last_logined_date datetime O   마지막 로그인된 날짜 및 시간
account_create_date datetime     계정 생성 날짜
account_last_update_date datetime     마지막 계정 정보 수정 날짜
credential_expire_date datetime     비밀번호 만료일
is_account_enabled bit(1)     계정 활성화 여부
is_account_locked bit(1)     계정 잠금 여부
is_account_expired bit(1)     계정 만료 여부

 

 

6.2. Authority Schema(복합 PK)

Column Type Nullable PK FK 설명
id varchar(20)   O User.id User Table로부터의 외래키
role varchar(10)   O   User에게 부여된 역할

+ Recent posts