슬로

https://school.programmers.co.kr/learn/courses/30/lessons/150368

이모티콘의 최대 개수가 7개, 할인율의 종류가 4개이므로 최대 4^7 경우의 수를 탐색해야했다.

재귀를 써본적이 없어서 7중 for문을 써서 풀려고 했다 😅 하지만 이모티콘의 개수에 따라 for문을 다르게 중첩해야 하기에 그렇게 풀기는 어려웠다.

재귀를 써서 DFS로 풀기로 하고 함수를 작성했다.

<로직>

할인율의 조합을 담는 rates 배열을 가지고 재귀호출을 하면서, rates 배열의 모든 경우의 수를 탐색.

재귀함수가 처음 호출될 때는 rates배열이 다 0으로 초기화되어있다. 호출 될 때마다, 현재 index에 할인율을 지정된 할인율을 담음. 지정된 할인율은 재귀호출의 파라미터로 넘어오는데, 0~3의 인덱스로 각 RATES[idx]로 표현된다.

할인율을 담았으면 현재 길이를 확인한다. cur + 1 == emoticons.length  이면 재귀를 종료하고 문제에서 요구한 계산 실행.

아직 length가 부족하면 다음 할인율을 담아야하니 재귀호출을 한다. 이 때, 현재 rates의 배열에서 파생되는 모든 경우의 수(다음거 10, 20, 30, 40)를 탐색해야하므로 모든 경우의 수에 대해 재귀호출을 한다. 하나의 재귀 프로세스는 rates가 꽉차서 계산이 실행될때만 종료되기 때문에, 메모리걱정은 안해도 된다.\

문제에서 요구하는 계산 = 그냥 할인율,이모티콘 곱해서 가격구하고 몇명이 사는지, 그리고 최대인원이 살 때 매출 얼마인지. ==> MAXREG 변수가 최대로 갱신될 때 MAXREV 갱신. MAXREG가 동률일 때 MAXREV 비교

<구현>

DFS를 처음 짜봤는데, search함수 내에서 calculate라는 함수를 미리 넣어놓고, 나중에 짰다. 이렇게 하니까 search함수의 재귀 종료 시점에서 어떤 계산이 일어나야하는지, 그 때 필요한 파라미터는 뭐가있는지, 어떤 반환값을 가져야하는지를 미리 생각해볼 수 있어서 좋은 것 같다.

import java.util.*;
class Solution {
    public static int MAXREG = 0;
    public static int MAXREV = 0;
    public static int[] RATES = {10, 20, 30, 40};
    
    public int[] solution(int[][] users, int[] emoticons) {
        int[] answer = new int[2];
        int[] rates = new int[emoticons.length];
        for(int i = 0; i< RATES.length; i++){
            search(users, emoticons, rates, 0, i);
        }
        
        answer[0] = MAXREG;
        answer[1] = MAXREV;
        return answer;
    }
    
    public static void search(int[][] users, int[] prices, int[] rates, int cur, int idx){
        rates[cur] = RATES[idx];
        if (cur + 1 == rates.length){
            int[] infos = calculate(users, prices, rates);
            if (infos[0] > MAXREG){
                MAXREG = infos[0];
                MAXREV = infos[1];
            }
            else if (infos[0] == MAXREG){
                MAXREV = Math.max(MAXREV, infos[1]);
            }
        }
        else{
            for(int i = 0; i<RATES.length; i++){
                search(users, prices, rates, cur + 1, i);
            }
        }
    }
    
    public static int[] calculate(int[][] users, int[] prices, int[] rates){
        int[] ans = {0,0};
        
        for (int[] user:users){
            int buyrate = user[0];
            int buylimit = user[1];
            int pricesum = 0;
            for(int i = 0; i<prices.length; i++){
                if(rates[i] >= buyrate){
                    pricesum += (100 - rates[i]) * prices[i] / 100;
                }
            }
            if (pricesum >= buylimit){
                ans[0] += 1;
                pricesum = 0;
            }
            else{
                ans[1] += pricesum;
            }
        }
        return ans;
        
    }
}

서비스가 커지고 문제가 복잡해질수록, 이를 처리하기 위한 소프트웨어의 아키텍쳐적인 부분이 중요해진다.

내가 진행했던 토이프로젝트의 서버는 크게 세 가지 일을 했다.

-새로운 데이터를 처리

-서비스로직을 처리(시간표그려주기 등)

-기존의 데이터를 이용 (db 활용)

Spring 에서는 해당 부분들이 각각의 레이어로 나누어져있다.

-Presentation layer : 사용자와 상호작용하는 처리 계층. CLI, HTTP요청, HTML처리 등을 담당 (Model, View, Controller..)

   ==> 특정 url에 요청을 보내면 해당 url에 묶인 메서드가 호출되었던 부분과 비슷.

 Spring에서 @Controller로 표현

-Domain(business / service) layer : 서비스나 시스템의 핵심 로직. 유효성 검사, 계산 등 어플리케이션의 도메인과 관련된 작업들을 담당함. 프로그램이 복잡해지면, 비지니스 로직을 수행하기 위한 별도의 계층이 필요하다. 그게 Domain layer

 Spring에서 @Service로 표현

-Data Access(persistence) Layer (DAO 계층) : Database / Message Queue / 외부 API와의 통신 등을 처리한다.

DB 혹은 데이터 소스가 서버 외부에 별개로 존재하는 경우가 매우 많기 때문에, 데이터 소스와의 소통계층이 필요함.

Spring에서 @Repository로 표현

레스토랑에 비유하면

@Controller : 웨이터

@Service : 쉐프

@Repository : 주방보조 (재료가져다줌)

<Database>

DBMS : Database Management System

RDBMS : Relational Database Magagement System

==RDBMS==============

-테이블이라는 최소  단위로 구성되고, 테이블은 열과 행으로 이루어져있다.

-MySQL, PostgreSQL, Oracle 등

======================

H2 : In-memory DB의 대표주자. 인메모리DB란 서버가 작동하는 동안에만 내용을 저장하고, 서버를 닫으면 데이터가 모두 삭제  ==> 연습용으로 좋다.

<SQL> : Structured Query Language  :  RDBMS에서 사용하는 언어

=====DDL=====  : Data Definition Language   : 테이블이나 관계의 구조를 생성하는데 사용

CREATE DATABASE 데이터베이스이름;

CREATE TABLE 테이블이름

(

필드이름1 필드타입1,

필드이름2 필드타입2,

...

)

ALTER TABLE 테이블이름 ADD 필드이름 필드타입;

ALTER TABLE 테이블이름 DROP 필드이름;

ALTER TABLE 테이블이름 MODIFY COLUMN 필드이름 필드타입;

DROP DATABASE 데이터베이스이름;

DROP TABLE 테이블이름;

TRUNCATE DATABASE 데이터베이스이름;

TRUNCATE TABLE 테이블이름;

=====DCL=====  : Data Control Language   :  데이터의 사용 권한을 관리하는데 사용

GRANT SELECT , INSERT          : 권한 부여

ON mp

TO scott WITH GRANT OPTION;

REVOKE SELECT, INSERT         :  권한 회수

ON emp

FROM scott

[CASCASE CONSTRAINTS];

=====DML=====  : Data Manipulation Language   :  테이블에서 데이터를 검색 / 삽입 / 수정 / 삭제

INSERT INTO 테이블이름 (필드이름1,필드이름2,필드이름3...) VALUES(데이터값1, 데이터2, 데이터3....)

INSERT INTO 테이블이름 VALUES (데이터1,데이터2,데이터3....)

SELECT 필드이름 FROM 테이블이름 WHERE[조건];

UPDATE 테이블이름 SET 필드이름1 = 데이터값1, 필드이름2 = 데이터값2...... , WHERE 필드이름 = 데이터값;

DELETE FROM 테이블이름 WHERE 필드이름 = 데이터값;

<SQL Cheatsheet>

=====CREATE 제약조건들=====

AUTO_INCREMENT  :  컬럼의 값이 중복되지 않게 1씩 자동으로 증가하게 해줘 고유번호를 생성

NOT NULL : 해당필드는 NULL값을 저장할 수 없게됨

UNIQUE : 해당필드는 서로 다른값을 가져야만 함

PRIMARY KEY : 해당필드가 NOT NULL과 UNIQUE 특징을 모두 가지게 됨

     ==> 테이블에 유일하게 존재하는 값의 조합을 설정해서 중복된 데이터가 테이블에 삽입되는 것을 방지하는 제약조건

     ==> 데이터의 무결성을 위해서 사용, 데이터를 빠르게 검색할 수 있게 됨

FOREIGN KEY : 두개의 테이블을 연결하는 다리 역할을 하는 KEY 

     ==> FOREIGN KEY (필드이름) REFERENCES 테이블이름(필드이름)

     ==> FOREIGN KEY 역시 데이터의 무결성을 보장. FK를 적용하려는 컬럼이 참조하는 테이블의 컬럼은 PK, UNIQUE

어플리케이션이 데이터베이스를 직접 다룰 때의 문제점

- 훨씬 번거롭다 : 테이블 만들고, 쿼리 작성하고, 쿼리를 jdbc api통해 실행, 결과 객체도 직접 만들어줘야함

- SQL의존적이다: SQL에 컬럼을 추가하면, 관련된 객체, 쿼리문 등등 모든 부분을 수정해야함 => 비지니스로직보다 SQL↑

- 패러다임 불일치

==> ORM, JPA 기술의 등장

ORM : object relation Mapping

<JPA>  : Java Persistence API

=>자바 ORM 기술에 대한 표준 명세

1. 쿼리를 자동으로 만들어줌

2. 어플리케이션 계층에서 sql 의존성을 줄임 (번거로운 반복작업 ↓)

3. 패러다임의 불일치 해결

4. 방언을 지원하기 때문에, h2 DB, mySQL, oracle 등 SQL표준을 준수한 DB무엇을 붙여도 같은 코드로 쓸 수 있다.

@Entity     annotation을 통해 해당 클래스가 DB의 테이블 역할을 한다는 것을 알려준다.

@OneToMany  // @ManyToOne // @OneToOne // @ManyToMany   : Entity들의 연관관계 형성

eg) Food 엔티티의 food // Orders 엔티티의 food_id가 매핑되어야 한다고 할 때,

Food 클래스 안에서:

@OneToMany(mappedBy = "food", fetch = FetchType.EAGER)

private List<Orders> orders = new ArrayList<>();

Orders 클래스 안에서:

@ManyToOne

@JoinColumn(name = "food")

private Food food;                      ==> 생성자까지 추가해줘야함

repository 패키지에 각 entity별로 FoodRepository와 같이 생성

public interface FoodRepository extends JpaRepository<Food, Long>{}

foodRepository.saveAll(List<Food>)와 같이 사용 가능

메서드들 : save, saveAll, findAll, findById 등등

웬만한 기능들은 JpaRepository에 구현 되어있기 때문에, Repository 구현체에서 override 해주면 된다.

https://docs.spring.io/spring-data/jpa/docs/current/reference/html/#jpa.query-methods  에서 query method 들을 확인가능

<추가 공부>

-영속성 컨텍스트, 1차 캐시

https://school.programmers.co.kr/learn/courses/30/lessons/64065

열받게도 문제를 또 잘못 읽어버린 ㅡㅡ (정답 풀이 맨 아래)

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓삽질의 시작↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

<문제 이해>

주어지는 집합의 size가 순차적으로 1 -> 2 -> 3 ->4 .... 순이므로 (<== 삽질의 근원), n번째에 주어지는 집합에서 n-1번째 집합을 빼고 남는 원소가 n번째에 주어진 원소가 될 것이다. n 번째에 주어진 원소를 An이라고 하면, 결과로 반환해야하는 튜플은

(A1, A2, A3, A4.....)가 되어야 함. 즉, 주어진 Set들의 Set을 돌면서 이전 Set에 추가된 원소들을 찾으면 될 것.

<풀이 구상>

1. input[i]를 돌면서 input[i-1]의 원소들을 하나씩 지워나가고, 남는 원소를 FinalSet에 추가

    ==> 각 시행마다 input[i]의 길이 * input[i-1]의 길이를 탐색하므로 시간 오래걸릴 듯

2. input[i]와 input[i-1]를 Set으로 만들어주고, Set끼리의 연산

   ==> 파이썬처럼 Set - Set 연산이 가능한지 알아봐야함

   ==> int[]를 Set으로 만드는 것 자체가 오래걸리지 않을까 ?

   ==> 문제에서 중복이 없음을 보장하고 있는데 Set을 쓰는게 맞는가?

<구현가능성>

===============문제를 확인해보니, 주어지는 input이 배열이 아니라 String임============

★String 처리하여 각 input을 받아올 방법 필요

-파이썬처럼 Set - Set 연산이 가능한지 ?  ==> .removeAll(c) 메서드로 가능

myself.removeAll(Collection c) ==> 내 자신의 원소가 collection c에 있으면 remove.

결국 iterator를 끝까지 도는 것은 매한가지다. 효율은 그닥일 듯. 이 함수를 쓰려면 input string s 를 거꾸로 읽는게좋겠다.

번외로, retainAll이라는 메서드도 있다.

==> 어차피 돌거면 그냥 앞에서부터 읽으면서, 그동안 나온 숫자를 모아놓은 SET을 유지   (=> 어차피 중복X 보장이고, 순서를 알아야하므로 List로 하기로 함)하고, i번째 집합의 원소마다 contains를 확인하여 없으면 answer에 붙이고 없으면 pass하도록 하는게 나을 것 같다고 생각함

-String을 읽으면서 {와 } 사이의 숫자를 읽는 방법이 필요함

buffer라는 개념이 생각남  ==> 추후 공부하여 정리하기

버퍼는 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리의 영역

자세히는 모르지만, 이런 방법을 생각했다

1. {를 만나면 버퍼를 연다 

2. ,를 만나면 버퍼에 저장된 String을 숫자로 변환해 기존 Set에 있는지 검사

3. Set에 없으면 Set에 넣고, 진행 // Set에 있으면 버퍼를 닫고 다음 }까지 진행

이를 위해 buf라는 char[] 배열을 선언하였고, 이 배열의 내용물을 Int로 바꾸는 메서드와 buffer를 clear해주는 메서드를 작성하였다. ==> size를 저장하는 변수를 관리해야하는데, 어디 선언해야 예쁜지 몰라서 그냥 List<Character>로 진행

<구현>

<문제>

1. 내 Buffer를 String으로 바꾸는 방법에 대한 문제

buffer를 List<Character>로 구현했더니, buffer의 내용물을 String으로 바꿔주는 과정에서

Character List에 담긴 2가 String "2"로 변환되지 않고, "[2]"로 변환되는 문제가 있었다.

 buf의 타입을 바꿔줘야 할 것 같았지만, 일단 코드 작동을 확인하기 위해 정규표현식으로 [와 ]를 벗겨주었더니, 

첫번째 예시에 대해서 통과하여 일단 로직이 잘못되지는 않았다는 걸 알 수 있었다. 그러나,

한자리수를 초과하는 숫자에 대해서 "20"과 같은 String으로 나오는 것이 아니라 "2, 0"으로 나와 숫자로 변환이 안됐다.

buffer.toString()이   "[2, 0]"을 return 했다는 얘기였다.

String.valueOf(buf) 도 마찬가지였다.

String.valueOf() 메서드는 파라미터로 Object가 들어왔을 때, object가 null이 아니면 object의 toString() 함수를 호출한다고 되어있다. 따라서 String.valueOf(buf) ==  buf.toString() 메서드 (현재 buf는 List<Character>인 Object 니까)

List의 toString() 메서드를 보면,

사람이 이 Object에 뭐가 담겨있는지 한 눈에 볼 수 있도록 변환하도록 되어있다.

ArrayList의 element type은 Map이 될 수도 있고, Integer가 될 수도 있고, 어떤 객체든 올 수 있다.

만약 [1, 2, 3, 4, 5, 6]이 List로 담겨있을 때 내가 바랐던 것처럼 하나의 String에 이 요소들을 모두 모으게 되면,

"123456"이 되어 이 List가 한 자리 숫자들을 하나의 element로 담고있다는 정보가 없어질 것이다. 타입이 Map이거나 다른 사용자가 정의한 Class라면 더 어지러울 것이므로, toString()의 return값은 "[요소1, 요소2]" 이런식의 String으로 반환하여 로그를 찍어볼 때 한 눈에 볼 수 있게 해둔 것 같다.

★char[]같은 경우 각 element에 문자가 딱 하나씩 담긴게 보장이 되므로, "abcde"같은 string으로 반환해준다.

int, char, long, float, double, boolean, char[]에 대해서는 String 클래스 안에 정의되어있지만,

int[] 타입의 ints의 경우 Object로 간주해 int[]에 override 되어있는 toString()함수를 호출하게 하는 것을 보면, 숫자 하나, 문자하나 또는 char[]과 같이  헷갈릴만한 소지가 없는 경우에만 String.valueOf를 정의하고 있는 것을 알 수 있다.

<문제 해결>

방법1. buf를 List<Character>로 유지할 경우 : StringBuilder 클래스를 사용한다.

방법2. buf를 char[] 로 바꿔줄 경우 : toString()으로 변환 가능. 대신, List의 이점을 포기해햐함

                                                                                         ==>buffer size 저장, buffer clear 간편

조금 귀찮아도 방법 2로 하기로 했다.

<더 큰 문제>

또 문제를 똑바로 안읽었다. input = {{집합1}, {집합2}, {집합3}.... } 에서 input 역시 집합이므로 안에 원소가 길이가 바뀔 수가 있다는 것......... 나는 예시1만 보고 냅다 로직을 구상해버린 것이었다.😭😭

어쩐지 쉽더라 .... 정신적 충격이 심해 조금 쉬었다가 해야겠다..

============================================================================================

<새로운 풀이>

정신이 말짱해지고 오니 왜 저렇게 했는지 모르겠다. 난 정규표현식과 Comparator를 아는데 !!

1.input s 에서 처음 등장하는 {{와 마지막에 등장하는 }}를 지워준다.

2.split( " },{ ")로 각 내부집합을 받아온다

3. 2에서 받아온 내부집합은 String[] 인데, custom Comparator를 사용하여 길이순으로 정렬해준다.

4.내부집합의 원소들을 돌면서 Set에 있는지 확인하고, 없으면  tuple에 넣어준다

import java.util.*;
class Solution {
    public static int[] solution(String s) {
        List<Integer> tuple = new ArrayList<>();

        String regex = "^\\{\\{|}}$";  // s 시작의 {{, 끝의 }}를 지워줌
        String[] toarr = s.replaceAll(regex,"").split("},\\{");
        Arrays.sort(toarr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.length() - o2.length();
            }
        });

        for(String set:toarr){
            String[] nums = set.split(",");
            for(String num:nums){
                int intNum = Integer.parseInt(num);
                if (!tuple.contains(intNum)){
                    tuple.add(intNum);
                    break;
                }
            }
        }
        int[] answer = new int[tuple.size()];
        for(int i = 0; i< tuple.size(); i++){
            answer[i] = tuple.get(i);
        }

        return answer;
    }
}

처음 했던 방식보다 훨씬 깔끔하고 쉽게 풀렸다. 애초에 문제를 잘못 이해 했을 경우에도 이렇게 하는게 맞았는데, 깊이 생각 안하고 냅다 풀어버리니까 버퍼에 집착해서 이상하게 풀게 됐던 듯.

test case에서 걸려서 다행이지 hidden case에만 걸렸으면 진짜 오래 고민했을 것 같다.

제출 후에 다른사람들의 풀이를 보니 비슷한 풀이가 많았는데, 내 코드를 줄일 여지를 몇 개 찾아 적어놓는다

1. Comparator를 람다식으로 작성 ==> 가독성 좋아보임 (어차피 간단한 comparator니까)

2. java.util.regex의 Pattern과 Matcher를 활용해 input s에서 숫자만 찾고. matcher의 find와 group 활용

     ==> 추후 regex 공부할 때 알아보고 정리하기

3. Set.add에는 boolean 반환값이 있다. List로 하지 않더라도 if (Set.add(num)) ==> num을 tuple에 저장

    과 같은식으로 할 수 있을 것 같다. (Set.add는 중복아닐 때 true 반환). 물론 이 문제에서는 중복인 경우가 주어지지

    않는다고 했으니 중복검사를 안 하는 List.add가 조금이나마 더 효율적이지 않을까....

<오늘 배운 점>

1. 문제를 똑바로 읽자 제발

2. 문제를 읽었으면 예시를 떠올려보자. 최대한 내가 생각한 풀이가 틀리게 되는 방향으로 생각해보기

3. toString() 메서드에 대한 이해......(왜 그냥 String으로 반환해주지 않는지 이해해서 유익하긴 했다.)

https://school.programmers.co.kr/learn/courses/30/lessons/72412

lv.1 어지간한 문제를 다 풀고 lv2로 넘어왔다.

lv.2의 가장 어려운문제들은 어떤지 궁금해서 마지막페이지로 가서 아무거나 누른 문제.

2021 카카오 코테 문제였나보다.

구현도 쉽지 않았지만, 계속 효율성테스트를 실패해서 약 4시간을 고민한 결과 문제를 잘못읽었음을 깨달았다.

query에 들어오는 조건이 순서가 뒤죽박죽일 수  있는줄 알았는데, 순서가 정해져있었다.

결론 : 문제가 길어도 똑바로 읽고 시작하자

<두번째 try>

기존 코드 문제 : 쿼리가 어떤 순서로 들어오는지 모른다고 생각을 해서, 쿼리를 split으로 나누고, 각 조건마다 for문을 돌면서 info가 그 조건을 contain하는지 확인했다. 또한, 이 작업을 info의 모든 element에 대해 해야해서 시간이 굉장히 많이 걸렸다.

추가적으로, 문제에 info는 최대 10만, query는 최대 50만의 길이로 위 코드의 이중포문은 최대 50억번을 돌게된다.😂

개선방안 : 언어,직군,경력,소울푸드를 구분할 수 있는 key를 만들어서 Map의 key로 사용하고, 해당 key의 value는 List로 선언을 해서, 해당key를 가진 지원자들의 점수를 삽입해주도록 한다.

==> 이렇게 하면 Map.get(key)를 통해 조건들에 해당하는 지원자들의 점수리스트를 가져오고, reverse sort 후 indexOf로 해당 점수를 넘은 사람이 몇명인지 알아낼 수 있을 듯.

생각해볼 점 : info에는 모든 정보가 있지만, query에는 누락된 조건이 있을 수 있다.

예를 들어, info상의 "java backend junior pizza" 지원자는 query의 "java and - and - and - 150" 조건에 의해 검색되어야한다. 두 개의 다른 string을 어떻게 같은 조건으로 검색할것인지(Map의 key를 찾을 때 정규표현식을 쓸수있나 ?)

<세 번째 Try>

글쓰다가 뒤로가기 눌러서 코드 캡쳐가 사라졌다 ....

각 조건마다 1~9의 숫자 string을 주어 조건들의 조합으로 key를 생성하였다.

<info 인코딩>

java backend senior pizza 150 ==> encode_query와 getScore 함수에서 각각

"3579"의 key와 int 150의 숫자로 인코딩하였다.

이처럼 만들어진 (3*2*2*2) = 24개의 key와, ArrayList를 가진 Map을 선언하여

각각의 key에 해당하는 지원자들의 점수를 삽입한뒤, 추후에 있을 탐색을 위해 정렬해두었다.

keyMap :    Map< String, List<Integer>>

<query 인코딩>

query도 마찬가지로 인코딩해주었는데, query의 경우 조건이 주어지지 않는 항목들이 있어 정규식으로 처리해주었다.

"- and backend and - and pizza 150"와 같은 query에서 and와 pizza를 지우고, split()의 regex를 "\s+"로 주어 하나 이상의 공백을 기준으로 split하였다. 

"- and backend and - and pizza"  ==> key  : "59"  score : 150

"- and - and - and - 150"              ==> key : ""      score : 150

<keySet 검색>

처리된 query string의 각 문자들을 모두 포함하고 있는 key들을 검색하여, 이들 각각의 리스트에서 점수로 걸러내면 정답을 얻을 수 있다고 생각했다.

- Map.keySet()의 각 원소(key)가 contains(Regex)인지 검사한다.

- Regex = "(?=.*" + String.join(")(?=.*", qr.split("")) + ").*"   ==> key가 query의 각 char을 적어도 하나 포함하는지

<List 검색>

regex로 얻은 key들의 List를 각각 가져오고, 각 리스트에서 >점수컷 인 사람을 세서 answer에 누적시킨다.

<결과분석>

효율성 테스트를 4개 중 2개 통과했다. 이 문제에서 가장 시간이 오래 걸리는 부분은 각 query에 대해서 List를 탐색하는 부분일 것이다. 내가 한 방법대로 하면 쿼리 조건이 빈 것 없이 4개를 채워서 들어오면 탐색을 한 번만 하지만, 

- - - - 150 처럼 점수만 조건으로 들어왔을때는 최대 (3*2*2*2) = 24번의 탐색을 진행하게 된다. 이게 효율성테스트를 통과하지 못하는 직접적인 이유인 듯하다.

<다른방법>

조건에 빈 틈이 있어도 탐색횟수를 줄이려면, 빈 조건이 있는 조건까지 key를 생성해주면 된다. 기존 (3*2*2*2)의 key에서 조건이 빠지는 경우까지 생각하여 (4*3*3*3) = 108개의 고유  key를 생성하고, info의 조건 하나마다 포함,불포함하는 경우 총 16가지의 경우의 수에 점수를 모두 삽입해주면 된다.

문제를 보자마자 생각했던 방법인데, 당시에는 "조건 영역의 개수가 늘어나거나, 조건의 option이 한두가지만 추가되어도, 하나의 info에 대해 삽입해야할 Key의 permutation이 기하급수적으로 많아지기 때문에 리소스 측면에서 낭비가 심하다" 라고 생각했다. 내가 간과한 것은 query의 개수가 많으면 많을수록 HashTable을 만드는 것에 대한 기회비용이 작아진다는 것이다. (한 번 잘 만들어놓으면 매 query에 대해 단 한 번의 탐색만 하도록 보장해줄 수 있기 때문)

내가 풀었던 방법은 삽입의 비용이 이걸 상쇄할정도로 매우 크거나, query들의 조건이 빠짐없이 전달된다고 가정했을 때 효과적일 것이라고 생각한다.

<최종 풀이>

import java.util.*;
class Solution {
    public static int[] solution(String[] info, String[] query) {
        //initialize codeMap
        codeMap.put("cpp",'1'); codeMap.put("java",'2'); codeMap.put("python",'3');
        codeMap.put("frontend",'4'); codeMap.put("backend",'5'); codeMap.put("senior",'6');
        codeMap.put("junior",'7'); codeMap.put("chicken",'8'); codeMap.put("pizza",'9'); codeMap.put("-",'-');
        int[] answer = new int[query.length];
        //Map 생성, key permutation별로 전부 삽입해주기
        Map<String, List<Integer>> keyMap = new HashMap<>();
        for (String inf:info){
            int score = getScore(inf);
            String[] encoded = encode_info(inf);
            for (String key:encoded){
                if (!keyMap.containsKey(key)){
                    keyMap.put(key, new ArrayList<Integer>());
                }
                keyMap.get(key).add(score);
            }
        }
        ///key별로 미리 정렬해놓기
        for (String elem:keyMap.keySet()){
            Collections.sort(keyMap.get(elem));
        }
        //query를 돌면서 이분탐색 진행
        int ansidx = 0;
        for (String qr:query){
            int cut = getScore(qr);
            qr = encode_query(qr);
            if (keyMap.containsKey(qr)){
                List<Integer> lst = keyMap.get(qr);
                answer[ansidx] = countscore(lst, cut);
                ansidx++;
            }
            else{
                answer[ansidx] = 0;
                ansidx++;
            }
        }
        return answer;
    }

    public static Map<String, Character> codeMap = new HashMap<>();

    public static char stringTocode(String code){

        return codeMap.get(code);
    }

    public static String[] encode_info(String info){

        String[] tempsplit = info.replaceAll(" [0-9]+", "").split(" ");
        int idx = 0;
        String[] permutations = new String[16];
        for (int i = 0; i<2; i++){
            char[] encoded = new char[4];
            encoded[0] = (i == 1)?stringTocode(tempsplit[0]):'-';
            for(int j = 0; j<2; j++){
                encoded[1] = (j == 1)?stringTocode(tempsplit[1]):'-';
                for(int k = 0; k < 2; k++){
                    encoded[2] = (k == 1)?stringTocode(tempsplit[2]):'-';
                    for(int n = 0; n<2; n++){
                        encoded[3] = (n == 1)?stringTocode(tempsplit[3]):'-';
                        permutations[idx] = String.valueOf(encoded);
                        idx++;
                    }
                }
            }
        }
        return permutations;
    }

    public static String encode_query(String query){
        String encoded = "";
        String[] tempsplit = query.replaceAll(" [0-9]+","").split(" and ");
        for (String sp:tempsplit){
            encoded += stringTocode(sp);
        }
        return encoded;
    }

    public static int getScore(String info){
        return Integer.parseInt(info.replaceAll("[^0-9*]",""));
    }

   public static int countscore(List<Integer> arr, int score){

    int mid=0;
    int end = arr.size();
    int start = 0;

    while (end > start) // end가 start보다 같거나 작아지면, 그 값이 Lower Bound이므로 반복을 종료한다.
    {
        mid = (start + end) / 2; 
            if (arr.get(mid) >= score) // 중간값이 원하는 값보다 크거나 같을 경우, 끝값을 중간값으로 설정하여 다시 탐색한다.
            end = mid;
        else start = mid + 1; // 중간값이 원하는 값보다 작을 경우, 시작값을 중간값+1로 설정하여 다시 탐색한다.
    }
    return arr.size()-start;

    }
}

조건들을 숫자로 mapping해줄 필요는 없지만, regex 연습할 겸 사용해봤다.

자바의 객체지향에 익숙해지면 리팩토링 해봐야겠다.

<배운 점>

1. 문제를 잘 읽어야된다

2. 풀이를 구상할 때, 연산량이 큰 메서드가 무엇인지 생각하고, 요구조건에 맞게 설계해야한다(중요)

3. 여러번 풀면서 문자열을 다르게 처리하며 정규표현식 쓰는 연습 해봄 --> 글 따로 정리

4. Map의 Entry element를 List로 하여 저장하는 아이디어

알고리즘 문제를 푸는데, for문 안에서 정규식을 처리하고 특정한 로직을 수행하는데 정규식의 어떤 케이스에서 에러가 나는지 몰라 함수 여러군데에 print문을 찍어 확인하였다.

코드도 지저분해지는 것 같고, 다 찾아서 주석처리해주는 것도 번거로워서 이참에 디버거를 써보기로 함.

중단점을 생성해주고 디버깅 실행하면, 중단점에서 코드를 멈춰준다.

이런식으로 멈춰있는 동안에 변수들의 상태를 확인할 수 있고, 다음 코드를 한 줄씩 실행하면서 이들의 변화를 볼수있다.

하지만, 나에게 발생한 문제는 for문이 한참 돌다가 발생한 것이기 때문에 손으로 한줄씩 넘겨주면서 Exception이 발생한 곳을 찾아줄 수 없었다.

이럴땐, Exception이 발생할 때 멈춰주도록 설정을 하면 된다.

이렇게 NullPointerException이 발생했을 경우 멈춰주게되고, 왼쪽 탭에서 한 줄씩 이전으로 돌릴 수도 있다.

한줄 뒤로 돌아왔더니, 정규식을 처리한 이후 strip을 해주면 ""만 남는 케이스가 있어 이것을 넘겨받은 함수에서 해당하는 값을 찾지 못 해 에러가 발생한 것이었다.

https://school.programmers.co.kr/learn/courses/30/lessons/42889

스테이지별 실패율을 정렬하고, 그 인덱스를 반환해야 했기에,

Python의 dictionary와 같은 자료형에서 value 기준으로 정렬하면 좋겠다고 생각했다.

Java에서 Map은 Map.Entry 클래스들의 Set이다.

이로써, Map은 (key,value)의 입력이 들어올 때 마다 Map.Entry클래스를 인스턴스화해서 이를 저장하는걸 알수있다.

List< Map.Entry<Integer, Double> > 을 만든 뒤,이를 커스텀 Comparator를 통해 정렬하고, List를 돌면서 stage단계인 Key를 반환하게 하면 될거라고 생각했다.

Stage 별 해당 Stage에 머무르고 있는 사람을 Map으로 관리한 뒤,

로직에 맞는 실패율을 구해 entryList에 넣어준다. 삼항연산자는 연습삼아 써봤는데, 가독성이 안좋아 지양해야겠다.

1. stage i에 있는 사람이 0이면 failrate = 0

2. stage i에 사람이 있으면, 그 뒤 스테이지에 있는 사람(stage i를 깬 사람)의 합을 구해 나눗셈으로 실패율 계산

     ==> 이 때, afterstage == 0이면, 뒷 스테이지로 넘어간 사람이 없다는 뜻 + 0으로 나눗셈 안되므로

             failrate = 0으로 설정한다.

1.빨간부분이 comparator 정의. o1과 o2는 Map.Entry<Integer, Double>이며 getKey와 getValue 메소드를 사용할 수 있다.

문제의 로직대로 비교한 뒤, List의 sort함수를 사용해 정렬

2. Collections.reverseOrder() 메소드는 매개변수로 받은 comparator의 리턴값을 거꾸로 바꾼 Comparator를 반환한다.

나머지는 리스트를 돌면서 Key를 배열에 담아주면 끝

https://school.programmers.co.kr/learn/courses/30/lessons/12915

문자열들을 주어진 기준에 따라 분류하는 문제.

String[]을 각 String의 n번째 문자 기준으로 정렬하고, n번째문자가 같은경우 사전순으로 정렬해야한다.

정렬이 일어나는 과정에는 반드시 두 요소를 비교할 수 있는 기준이 있어야한다. 따라서 내가 정의한 클래스의 인스턴스들 간의 크기를 비교해줄 수 있게하려면 Comparable 인터페이스를 implement하여, 그 안의 compareTo 메서드를 Override 해주어야한다.

비교하고싶은 객체가 o 라고하자.

o1.compareTo(o2)는 o1이 작을때(왼쪽에있을때) 음수를, o1이 클 때 (오른쪽에있을때) 양수를 리턴해야한다.

String에는 이것이 구현되어있다.

하지만 String을 다른 기준으로 비교하고싶다고 해서 String.compareTo()를 Override할 순 없다. final이기때문에

따라서 이럴 경우 Arrays.sort()나 Collections.sort()에 내가 만든 Comparator를 전달하여 정렬할 수 있다.

cmp를 살펴보면, 먼저 문제에 정의된대로 n번째 인덱스의 character를 비교하고 있다. character는 기본형 변수로 빼기 연산이 가능하고, o1ch가 o2ch보다 앞에와야하면 음수가, 뒤에와야하면 양수가 return된다.

o1ch와 o2ch가 같을 경우, 사전 기준으로 비교해야하기 때문에 String의 compareTo를 사용하여 int를 반환하게 하였다.

이 문제에 정의된 방법 상으로 s1이 s2보다 좌측에 와야하면 음수, 우측에 와야하면 양수를 리턴하는 comparator를 전달하여 정렬하였다.

Comparator<type>의 타입은 기본형일 수 없다. 래퍼클래스 이용할것

<생성자>

Constructor. 객체가 생성(new)될 때 호출되며, 객체를 초기화하는 역할을 하며, 부가적인 역할도 함.

모든 클래스는 반드시 생성자가 있어야함 (안만들어주면 컴파일러가 기본생성자로 만들어줌)

컴파일러에 의해 생성되는 기본 생성자는 해당 클래스의 접근제어자를 따라간다.

생성자도 오버로딩 가능

<this>

자기 자신(인스턴스)를 가리키는 변수.

왜 ? 생성자에서 생성할 때, 클래스에서 정한 변수명과 파라미터로 정한 변수명이 겹칠 경우가 있음

public ClimbingGym(String name){

    this.name = name

}

이런식으로 this 써준다. 생성자에서 필드변수를 가리키는 경우에는 this.변수명 으로 써주는게 국룰

오버로딩에서도 많이 활용된다.

this는 Car를 가리키므로  this()는 즉  Car()와 같다. Car 클래스의 생성자를 호출하는 것.

<제어자>

제어자는 클래스, 변수, 메서드의 선언부에 사용되어 부가적인 의미를 부여함

접근 제어자 : public // protected // default // private

그 외 제어자 : static // final // abstract

public : 접근 제한이 전혀 없음

protected : 같은 패키지 내에서 + 다른패키지의 자손클래스에서 접근 가능

default : 같은 패키지 내에서만 접근 가능

private : 같은 클래스 내에서만 접근 가능

클래스에 사용 가능한 접근제어자 : public // default

메서드 & 멤버변수에 사용 가능 : public // protected // default // private

메서드에 static과 abstract를 동시에 사용 불가

클래스에 abstract와 final을 동시에 사용 불가

abstract메서드의 접근 제어자가 private일 수 없다

메서드에 private과 final을 같이 사용할 필요는 없다

접근제어자는 객체의 무결성 즉, 변경이 없는 상태를 유지하기 위해 사용한다.

외부에서 필드에 접근하는 것을 막기 위해 필드에 private, default 등의 접근 제어자를 사용할 수 있다.

==>제어자때문에 나오는 개념이 ★★★★★Getter // Setter★★★★★

<Getter & Setter>

★ getter와 setter는 직접적인 값의 조회와 세팅을 방지하기 위해 사용됨 !!

보통 하나의 필드마다 getter와 setter가 존재함 getColor(), setColor() 와 같이 camelCase로 선언하는게 국룰

예를들어, double type으로 선언한 age필드에 누가 person.age = "27살" 이런식으로 값을 직접 바꾸게되면 안되기때문에 setAge() 같은 public한 setter 메소드를 사용해 값을 변경하도록 하고, 그 안에 특정한 로직을 담게된다.

외부에서 객체의 private한 필드를 읽을 필요가 있을 때 Getter 메서드를 사용. Getter를 이용해 내부 로직을 숨기면서, 내보내야 하는 정보만 내보낼 수 있다.

<상속>

부모클래스를 상속받은 자식클래스는 부모클래스의 필드나 메서드를 사용할 수 있다.

상속을 사용하면 코드의 중복이 제거되고, 재사용성이 크게 증가하여 생산성과 유지보수성에 매우 유리해진다.

상속 keyword : extends

public class 자식클래스 extends 부모클래스 { }

-부모클래스에 새로운 필드와 메서드가 추가되면 자식클래스는 이를 상속받아 사용할 수 있다.

-자식클래스에 새로운 필드와 메서드가 추가되어도 부모클래스는 어떠한 영향도 받지 않는다.

-따라서 자식 클래스의 멤버 개수는 부모클래스보다 항상 같거나 많다.

★Java는 다중상속을 허용하지 않음 : 클래스간의 관게가 복잡해지기 때문

★부모 클래스에 final인 멤버가 있으면 상속 불가 : 변경 불가하기 때문에 override할 수 없기때문

★overload : 클래스 내에 같은 이름의 메소드를 여러가지로 정의  // override : 부모클래스의 메서드를 재정의

<추상 클래스>

-미완성된 설계도. 부모는 완성시키지 않은 method를 가지고 있고, 자식은 이를 상속받아서 완성시킴

- abstract 키워드를 class 앞에 넣어줘서 사용

eg) public abstract class 추상클래스명;                 ==> {}가 없고, 세미콜론으로 선언만 함

1. 추상 클래스는 추상 메서드를 포함할 수 있다 (없어도 선언 가능하긴함)

2. 추상 클래스는 자식 클래스에 상속되어서 자식 클래스에 의해서만 완성될 수 있음

3. 추상 클래스는 여러개 자식클래스 중에서 공통적인 필드나 메서드를 추출해서 만들 수 있다.

부모클래스를 자식들이 가져다 쓴다는 느낌보다, 자식클래스들의 공통된 특징을 묶어주는 느낌이 강하다(추상화)

상속받은 클래스에서 추상 클래스의 추상 메서드는 반드시 오버라이딩 되어야 한다(인터페이스와 다른 점)

<Interface>

두 객체를 연결해주는 다리.

- 상속관계가 없는 다른 클래스들이 서로 동일한 메서드를 구현해야할 때 인터페이스는 구현 클래스들의 동일한 사용 방법과 행위를 보장해줄 수 있다.

예를들어, 멀티 리모컨 인터페이스를 통해 삼성티비 객체, LG티비 객체의 채널을 변경할 수 있음

interface 키워드로 선언하며,   public interface 인터페이스명{ }    과 같은 형태가 됨. public // default 접근자 지정 가능

1. 인터페이스의 모든 멤버 변수는 public static final  : *생략가능 -생략시 컴파일러가 자동으로 추가

2. 인터페이스의 모든 메서드는 public abstract : *생략가능-생략시 컴파일러가 자동 추가(static, default 메서드 제외)

3. 생략되는 제어자는 컴파일러가 자동으로 추가해줌

- 인터페이스는 추상 클래스와 마찬가지로 직접 인스턴스를 생성할 수 없어, 클래스에 구현되어 생성된다.

public class 클래스명 implements 인터페이스명{

    @Override

    public 리턴타입 메서드이름(매개변수 ...{

            //실행문

        }

}

- 인터페이스의 추상 메서드는 구현될 때 반드시 오버라이딩 되어야 함. (안하면 컴파일 시 오류 발생)

- 인터페이스의 추상 메서드를 일부만 구현해야 한다면, 해당 클래스를 추상 클래스로 변경해주면 된다

    ==> implements 받는 클래스를 추상클래스로 선언한 뒤, 이것을 필요한 클래스에 상속해서 override

- 인터페이스 간의 상속이 가능하다. 인터페이스간의 상속은 extends 키워드를 사용하며, 다중상속 가능

===========Interface의 default, static 메서드=============

--------------interface의 디폴트 메서드----------------

-디폴트 메서드는 추상 메서드의 기본적인 구현을 제공하는 메서드.

-default 역시 접근 제어자가 public이며, 생략 가능

-추상 메서드가 아니기때문에 인터페이스의 구현체들에서 필수로 재정의할 필요는 없다.

--------------interface의 static 메서드----------------

-static 메서드의 경우, interface에 바로 접근 가능.

-이유 : static 메서드는 compile 단계에서 생성되기 때문에 구현체를 선언하지 안하도 쓸 수 있다.

<인터페이스의 다형성>

A가 interface, B는 interface를 implement받은 객체라고 할 때,

A a1 = new B(); 를 하면 B라는 구현체가 A로 형변환 일어나게 된다.

C는 구현체 B를 상속받은 객체라고 할 때,

A a2 = new C(); 를 하면 C가 A로 형변환됨.