프로그래머스 Lv.1

🔥 숫자 짝꿍 🔥

👀 문제

두 정수 X,Y의 임의의 자리에서 공통으로 나타나는 정수 k들을 이용하여 만들 수 있는 가장 큰 수를 정수를 두 수의 짝꿍이라고 한다. 짝꿍이없으면 짝꿍은 -1이고 짝꿍이 0으로만 구성되어있다면 짝꿍은 0이다.

두 정수 X, Y가 주어졌을 때, X, Y의 짝꿍을 return하는 solution 함수를 완성해보자.

✔️ 조건

• 3 ≤ X, Y의 길이(자릿수) ≤ 3,000,000입니다.
• X, Y는 0으로 시작하지 않습니다.
• X, Y의 짝꿍은 상당히 큰 정수일 수 있으므로, 문자열로 반환합니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

결론부터 말하자면 못 풀었다. 꽤 오래 붙잡고 있었는데 방향을 아예못잡아서 다른분들의 풀이를 참고했다.

class Solution {
    public String solution(String X, String Y) {
        1️⃣
        int[] cntX = new int[10];
        int[] cntY = new int[10];

        2️⃣
       for (String tmpX : X.split("")) cntX[Integer.parseInt(tmpX)]++;
       for (String tmpY : Y.split("")) cntY[Integer.parseInt(tmpY)]++;


        StringBuilder sb = new StringBuilder();
        3️⃣
        for(int i=9;i>=0;i--){
            while(cntX[i] >0 && cntY[i] >0){
                sb.append(i);
                cntX[i]--;
                cntY[i]--;
            }
        }
        String answer = "";
        4️⃣
        if("".equals(sb.toString())){
            answer = "-1";
        }else if("0".equals(sb.toString().substring(0,1))){
            answer = "0";
        }else {
            answer = sb.toString();
        }

        return answer;
    }
}

1. 0~9까지의 숫자가 X과 Y에 몇개씩 존재하는지 알기위한 배열
2. X와 Y를 한 문자씩 잘라서 반복문을 돌려주고 cntX와 cntY에 해당 숫자위치에 ++ 을 해줌
3. 9부터 0까지 내려가면서 cntX와 cntY의 값이 0보다 큰 경우 sb에 append 해줌
4. sb의 값이 "" 과 같다면 -1 0이라면 0 그외라면 sb.toString()이 정답이 된다.

👏 마무리

DATE_FORMAT

프로그래머스 SQL 고득점 Kit 문제를 풀다보니 월별 출력하기, 시각에 따른 COUNT, 해당 월에 대한 값 등 DATE TYPE을 원하는 형태로 변경해서 사용하는 문제들이 많았다.

DATE_FORMAT(날짜, 형식)

위와 같은 형태로 나타낸다. 날짜를 지정한 형식으로 출력하는 것이다.

예를들어 DATE TYPE의 컬럼 START_DATE의 값이 2022-03-06 00:00:00 일 때 우리는 '년-월'의 형태로 출력되기를 기대해보자.

DATE_FORMAT(START_DATE,'%Y-%m)

위와같이 하고 SELECT 을 하면 우리가 원하는 '2022-03'의 형태로 출력된다.

날짜 뿐만 아니라 시간도 추출할 수 있다.

DATE_FORMAT에서 사용하는 구분기호는 아래와 같다.

다양하게 추출이 가능하다.

하지만 나는 문제를 풀면서 DATE_FORMAT(날짜,'%Y-%m-%d') 를 가장 많이 사용했다.

MYSQL에서 사용하는 날짜 관련 함수들

• dayofweek(date) : 날짜를 한 주의 몇번째 요일인지를 숫자로 (1 = 일, 2 = 월)
• weekday(date) : 날짜를 한 주의 몇번째 요일인지를 숫자로 (0 = 월, 1 = 화)
• dayofmonth(date) : 그 달의 몇 번째 날, 리턴값은 1~ 31
• dayofyear(date) : 한 해의 몇 번째 날인지, 리턴값은 1 ~ 366
• month(date) : 몇 월, 리턴값은 1~ 12
• dayname(date) : 영어식 요일 이름
• monthname(date) : 영어식 월 이름
• quarter(date) : 분기
• week(date) : 몇 번째 주일
• week(date, first) : 주어진 인수로 한 주의 시작일을 지정 (0이면 일요일, 1이면 월요일을 시작으로 지정)
• year(date) : 년도
• hour(time) : 시간(0~23)
• minute(time) : 분 (0~59)
• second(time) : 초 (0~59)
• period_add(p,n) : 주어진 달에 n개월을 더함 , 리턴값은 yyyymm
• period_diff(p1,p2) : 주어진 두 기간 사이의 개월

이 함수들은 간단하게 2023년에 구매한 회원을 구하고자 할때 DATE_FORMAT을 사용하는 것보다는 YEAR(DATE)가 훨씬 편리하기 때문에 알아두기로!

[ 프로그래머스 SQL 고득점 Kit ]

• SELECT 3월에 태어난 여성 회원 목록 출력하기 조건에 부합하는 중고거래 댓글 조회하기 흉부외과 또는 일반외과 의사 목록 출력하기 조건에 맞는 도서 리스트 출력하기
• GROUP BY 대여 횟수가 많은 자동차들의 월별 대여 횟수 구하기 카테고리 별 도서 판매량 집계하기 저자 별 카테고리 별 매출액 집계하기 입양 시각 구하기(1)
• JOIN 조건에 맞는 도서와 저자 리스트 출력하기 그룹별 조건에 맞는 식당 목록 출력하기 5월 식품들의 총매출 조회하기
• STRING, DATE 자동차 대여 기록에서 장기/단기 대여 구분하기 조건별로 분류하여 주문상태 출력하기 취소되지 않은 진료 예약 조회하기 조건에 부합하는 중고거래 상태 조회하기 DATETIME에서 DATE로 형 변환

📑 References

[mysql]날짜 관련 함수 모음

프로그래머스 Lv.1

🔥 삼총사 🔥

👀 문제

학생들은 각자 정수 번호를 가지고 있다. 학생 3명의 정수 번호를 더했을 때 0이되면 3명의 학생들을 삼총사라 한다.

학생들의 번호를 나타내는 정수배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution함수를 완성하자.

✔️ 조건

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        for(int i=0;i<number.length;i++){
            for(int j = i+1;j<number.length;j++){
                for(int k = j+1; k<number.length;k++){
                    if((number[i] + number[j] + number[k]) == 0){
                        answer++;
                    }
                }
            }
        }


        return answer;
    }
}

👏 마무리

프로그래머스 Lv.1

🔥 크기가 작은 부분문자열 🔥

👀 문제

숫자로 이루어진 문자열 t와 p가 주어진다. t에서 p와 길이가 같은 부분문자열 중 p보다 작거나 같은 것이 나오는 횟수를 return하는 solution을 완성하자.

✔️ 조건

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열로 0으로 시작하지 않음

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

import java.util.*;

class Solution {
    public long solution(String t, String p) {
        int pl = p.length();
        int tl = t.length();
        long answer = 0;
        long cnt = 0;

        while(pl+cnt <= tl){
            int startIdx = 0;
                startIdx += cnt;
                String com = t.substring(startIdx,pl+startIdx);
                if(Long.parseLong(com) <= Long.parseLong(p)){
                    answer++;            
                }   
            cnt++;
        }
        return answer;
    }
}

💬 다른 풀이

class Solution
{
    public int solution(String t, String p)
    {
        int answer = 0;

        for(int i=0; i<=t.length()-p.length(); i++)
            if(Long.parseLong(t.substring(i, i+p.length())) <= Long.parseLong(p))
                answer++;

        return answer;
    }
}

👏 마무리

무작정 풀기보다는 깔끔하게

쿠폰 seqNumber를 생성할 때 Random클래스를 사용하고 있었는데 Random보다는 SecureRandom을 사용하라고 취약점 리스트에 올라왔다.

디버깅을 해보니 두 개의 값이 서로 같아서 일단은 SecureRandom으로 수정을 했다. 근데 생각해보니 왜...? 어디가 취약하다는거지...? 의문이 생겨서 알아보기로 했다.

📌 Random은 안전하지 않다.

Random함수도 난수를 생성하지만 진짜 난수가 아닌 난수처럼 보이는 알고리즘을 통한 규칙적인 난수만 생성한다...?

이건 또 무슨 소리일까

컴퓨터는 기본적으로 정해진 입력에 따라 정해진 값만 내보낼 수 있는데 따라서 생성된 랜덤값은 정말로 임의의 값이 아니고 특정한 벙법으로 여러 계산을 거쳐서 사람이 볼 때 마치 임의의 값처럼 보이게 하는 의사난수(Pseudo Random)라고 한다.

이를 해결하기 위해서는 난수표를 여러개 만들어 놓고 매번 다른 난수표를 읽도록 해야하는데 여기서 난수표를 선택하는것을 '시드'라고 한다.

그런데 시드값이 같으면 선택되는 난수표도 똑같기 때문에 시드값도 난수여야하는 문제가 발생하게 되고 결국 난수를 만들려면 난수가 필요한 문제가 발생하게 된다.

즉, 시드값이 동일하면 매번 같은 값을 보여주는 것이다.

이젠 Random이 어느 부분에서 취약한지 알게 되었다.

그렇다면 SecureRandom은 Random과 다르게 안전한지 알아보자.

📌 Random vs SecureRandom

1. 크기 Random은 48비트, SecureRandom은 최대 128비트를 포함 할 수 있기 때문에 SecureRandom에서 반복 가능성이 더 낮아진다.

2. 시드 생성 Random은 시스템 시간을 시드로 사용하거나 생성하기 때문에 공격자가 생성 시간말 알고 있으면 재현이 가능하다. SecureRandom은 OS에서 임의의 데이터를 가져와서 시드로 사용한다.

3. 코드 깨기 Random은 고급 CPU를 사용하면 2^48번의 시도만에 깨뜨릴수 있지만 SecureRandom은 2^128번의 시도가 필요하고 오랜시간이 걸린다.

4. 보안 SecureRandom은 FIPS 140-2(암호학에서 사용되는 생성기표준)에서 지정한 테스트를 준수하기 때문에 좀 더 안전하고 SHA1PRNG를 사용하기 때문에 좀 더 안전한 알고리즘을 구현한다.

📌 SecureRandom은 안전한건가?

SecureRandom.getInstanceStrong()은 디폴트로 /dev/random에서 시드값을 얻어온다. 이로인해서 자바 버그로 인해 엄청난 퍼포먼스 저하를 발생시킬수 있다... 따라서 별도의 경로를 설정해주어야한다.

결국 SecureRandom도 Random에 비해 오버헤드와 경합이 적을 뿐 암호학적으로 안전하지 않다.

📒참고

자바의 난수생성기 Random, SecureRandom [Java] Random보단 SecureRandom 를 사용하자.

🌱 IoC (Inversion of Control)

제어의 역전으로 제어의 흐름을 바꾸는 것입니다. 기존에는 객체를 생성하고 의존성객체를 생성하여 의존성 객체 메소드를 호출하는 방식으로 객체가 만들어지고 실행되었다면 스프링에서는 객체 생성 후 제어권을 스프링에게 위임하여 스프링이 만들어놓은 객체를 주입하고 메소드를 호출하는 방식으로 이루어집니다. 객체의 생성부터 소멸까지의 생명주기를 컨테이너가 관리하기 때문에 제어권을 컨테이너가 소유합니다.

IoC의 주된 목적은 Application의 Dependency를 제거해서 느슨한 결합을 제공하는 것 컨테이너가 제어권을 소유함으로써 객체간 결합도를 줄이고 유연한 코드를 작성할 수 있습니다. 또한 모든 의존성 객체를 스프링이 실행될 때 전부 생성 후 필요한 곳에 주입해주므로 Bean은 싱글톤 패턴의 특징을 갖게 됩니다.

IoC의 분류

• DL : 저장소에 저장되어 있는 Bean에 접근하기 위해 컨테이너가 제공하는 API를 이용하여 Bean을 Look up하는 것
• DI : 각 클래스 간의 의존관계를 빈 설정 정보를 바탕으로 컨테이너가 자동으로 연결해주는 것
  • Setter Injection(수정자 주입)
  • Constructor Injection(생성자 주입)
  • Method Injection(필드 주입) ❓DI 더 알아보기

🌱 IoC 컨테이너

객체를 생성, 관리하고 책임지고 의존성을 관리해주는 컨테이너를 말합니다.

인스턴스 생성부터 소멸까지의 인스턴스 생명주기 관리를 개발자가 아닌 컨테이너가 대신 해줍니다.

객체관리 주체가 컨테이너가 되기 때문에 개발자는 비즈니스 로직에 집중 할 수 있습니다.

• IoC컨테이너는 객체의 생성을 책임지고 의존성을 관리

• POJO의 생성, 초기화, 서비스, 소멸에 대한 권한

• 개발자들이 직접 POJO를 생성할 수 있지만 컨테이너에게 맡김

• 개발자는 비즈니스 로직에 집중

• 객체 생성 코드가 없어지므로 TDD가 용이

  ✅ POJO(Plain Old Java Object)

  • 특정 자바 모델이나 기능, 프레임워크를 따르지 않는 Java Object를 지칭하며 특정 기술에 종속되어 동작하지 않는 자바 객체입니다.
  • 특정 기술의 클래스를 상속받거나 직접 의존하게 되면 확장성이 떨어지게 되고 이는 객체지향 설계의 장점을 잃어버리는 것이므로 POJO의 사용은 지향해야합니다.

🌳 이렇게 기억하자!

IoC는 제어의 흐름을 바꾸는 것으로 객체의 생성부터 소멸까지의 생명주기를 컨테이너가 관리하게 함으로써 객체간 결합도를 줄이고 유연한 코드를 작성할 수 있도록 하는 것입니다.

📒참고

IoC 컨테이너 (Inversion of Control) 란? 스프링(Spring) DI와 IOC에 대해 [Spring] Spring IoC와 DI란?

🌱 @RequestBody & @ResponseBody

웹에서 이루어지는 데이터 통신은 클라이언트와 서버간에 이루어지고 이때 중요한 것이 요청(Request)와 응답(Response)입니다. 비동기 통신을 위해서는 요청메시지와 응답메시지를 Body에 담아 보내야하는데 데이터의 형식은 JSON으로 설정합니다.

이때 @RequestBody와 @ResponseBody를 사용합니다.

HttpServleRequest를 이용해 데이터를 가져오면 굳이 @RequestBody가 필요하지 않지만 VO, DTO를 사용해 데이터를 받기위해서는 사용해야 합니다.

🎈 @RequestBody
    클라이언트 >> 서버
    데이터를 전송할 때 JSON형태로 데이터를 만들어 요청하면 서버에서는 @RequestBody를 이용해 
    HTTP요청 body에 담김 값들을 자바 객체로 변환시켜 객체에 저장시킨다.

🎈 @ResponseBody
    서버 >> 클라이언트
    @ResponseBody를 이용해 자바 객체를 HTTP 응답 본문의 객체로 변환하여 클라이언트로 전송한다.

값을 주입하지 않고 변환 시키므로 변수들의 생성자, Getter, Setter가 없어도 정상적으로 할당됩니다.

🌱 @RequestParam

🎈 1개의 HTTP 요청 파라미터를 받기 위해 사용

필수여부가 True여서 기본적으로 반드시 해당 파라미터가 전송되어하는데 전송되지 않으면 400 Error를 유발할 수 있습니다. 반드시 필요한 변수가 아니라면 required값을 false로 설정해주어야합니다.

🌱 @ModelAttribute

🎈 HTTP Body내용과 HTTP파라미터의 값들을 생성자, Getter, Setter를 통해 주입하기 위해 사용

값 변환이 아닌 값을 주입시키므로 변수들의 생성자나 Getter, Setter가 없으면 저장되지 않습니다.

✅ ajax요청을 @ModelAttribute에서 처리?

@ModelAttribute는 파라미터 기반의 요청을 처리하므로 데이터를 파라미터로 넘겨주면 ajax요청도 @ModelAttribute로 받을 수 있습니다.

get방식처럼 url에 데이터를 넣어 전달하게 되는데 좋지 않은 방법입니다.

따라서 ajax요청을 @ModelAttribute로 처리하기 위해서는 FormData를 사용하고 ajax를 통해 file 업로드를 처리할 때는 FormData를 통해 처리하고 서버는 @ModelAttribute로 받아야합니다.

🌳 이렇게 기억하자!

📒참고

@RequestBody와 @ResponseBody란? @ModelAttribute vs @RequestBody

🌱 Spring Framework

자바 개발을 편리하게 해주는 오픈소스 프레임워크

• 경량 컨테이너로서 자바 객체를 직접 관리
  • 각각의 객체 생성, 소멸과 같은 라이프 사이클을 관리, 필요한 객체를 얻어옴
• IoC(제어의 역전)
• DI(의존성 주입)
• AOP(관점 지향 프로그래밍)

🌱 Spring Boot와 Spring Framework의 차이점

Auto Configuration (자동설정)이 가장 큰 차이점이라고 할 수 있다. Spring Boot Starter가 dependency들의 버전을 관리해주고 실행 시에도 Tomcat이 포함되어있어서 편리하기 때문이다.

• Embedded Tomcat

  • Spring Boot 내부에 Tomcat이 포함되어 있어서 설치, 버전관리가 필요 없음

• starter를 통한 dependency 자동화

  • Spring Framework는 각 dependency들의 버전을 관리하는데 어려움이 많음
    • Spring Boot는 starter가 대부분의 dependency를 관리해줌

• XML 설정 X

• jar file을 이용해 자바 옵션 만으로 배포 가능

✅ Spring Boot Starter

특정 목적을 달성하기 위한 위존성 그룹

🌳 이렇게 기억하자!

Spring Boot는 Tomcat이 내장되어 있어 서버를 바로 실행 할 수 있고 Spring Framework에서는 각각 dependency들의 버전을 일일이 맞추어야해서 version관리에 어려움이 많았지만 Spring Boot에서는 Starter가 대부분의 dependency를 관리해주어 편리하다.

📒참고

[Spring] Spring Framework vs Spring Boot

🌱 WS (Web Server)

HTTP 프로토콜을 기반으로 하여 클라이언트에게 정적인 파일을 제공하기 위한 서버로 가장 앞에서 요청에 대한 처리를 진행한다.

1) 정적인 컨텐츠 제공

• WAS를 거치지 않고 바로 자원 제공

2) 동적인 컨텐츠 제공을 위한 요청

• 클라이언트의 요청(Request)을 WAS에 보내고 WAS가 처리한 결과를 클라이언트에게 전달(Response)함
• 클라이언트는 일반적으로 웹 브라우저를 의미

ex) apache, nginx, gws....

🌱 WAS (Web Application Server)

DB 조회나 다양한 로직 처리를 요구하는 동적인 컨텐츠를 제공하기 위한 서버로 HTTP를 통해 애플리케이션을 수행해주는 미들웨어이다.

WAS = Web Server + Web Container

웹 서버 기능들을 구조적으로 분리하여 처리하고자 제시되었고 주로 DB서버와 같이 분산 트랜잭션, 보안, 메시징, 쓰레드 처리 등의 기능을 처리하는 분산환경에서 사용된다.

1) 프로그램 실행 환경과 DB 접속 기능 제공 2) 여러 개의 트랜잭션 관리 기능 3) 업무를 처리하는 비즈니스 로직 수행

ex) tomcat. jeus, web logic...

🌱 WS는 왜 필요하지?

if... 웹브라우저에 이미지 파일(정적인 컨텐츠)를 보낸다.

정적인 파일은 웹문서가 브라우저로 보내질때 함께 전송되지 않는다. 므라우저는 HTML문서를 먼저 받고 필요한 이미지 파일들을 다시 서버로 요청하면 그때 이미지 파일을 받아온다.

따라서 WS를 통해 정젹인 파일들은 Application Server까지 가지 않고 앞단에서 빠르게 보내진다.

정적 컨텐츠만 처리 가능하도록 기능을 분배하여 서버의 부담을 줄인다.

🌱 WAS는 왜 필요하지?

웹페이지는 정적, 동적 컨텐츠가 모두 존재한다.

사용자의 요청에 맞게 적절한 동적 컨텐츠를 만들어 제공해야하는데 WS만 이용하면 원하는 요청에 대한 결과값을 모두 만들어 놓아야한다. 즉, 자원이 부족해지는 문제가 발생한다.

따라서 WAS를 통해 요청에 맞는 데이터를 DB에서 가져와서 비즈니스 로직에 맞게 그때 그때 결과를 만들어서 제공함으로써 자원을 효율적으로 사용할 수 있다.

🌱 WAS가 WS의 기능을 모두 수행하면?

1) 기능 분리로 서버 부하 방지

• WAS는 동적 컨텐츠를 제공하기 위해 존재하므로 단순한 정적 컨텐츠는 Web Server에서 빠르게 클라이언트에게 제공하는 것이 좋다.
• WAS가 정적 컨텐츠 요청까지 처리한다면 부하가 커지고 수행 지연이 일어나면서 페이지 노출시간이 늘어나게 된다.

2) 여러 대의 WAS 연결 가능

• 여러 개의 서버를 사용하는 대용량 웹 어플리케이션의 경우 Web Server와 WAS를 분리하여 무중단 운영을 위한 장애 극복에 쉽게 대응이 가능하다.
• 앞단의 WS에서 오류가 발생한 WAS를 사용하지 못하도록 한 후 WAS를 재시작 함으로써 사용자가 불편함 없이 사용하도록 한다.

자원 이용의 효율성 및 장애 극복, 배포 및 유지보수의 편의성을 위해 Web Server와 WAS를 분리한다.

🎈 Web Server를 WAS 앞에 두고 필요한 WAS는 Web Server에 플러그인 형태로 설정하면 효과적

🌳 이렇게 기억하자!

📒참고

웹서버(WS)와 웹어플리케이션서버(WAS)의 차이 [Web] Web Server와 WAS의 차이와 웹 서비스 구조

하나하나 차근히 공부하고 기록하자

1. WAS(Web Application Server)와 WS(Web Server)의 차이를 설명해주세요. 2. Spring Framework에 대해 설명해주세요. 3. @RequestBody, @RequestParam, @ModelAttribute의 차이를 설명해주세요. 4. Spring Boot와 Spring Framework의 차이점을 설명해주세요. 5. Spring MVC에 대해 설명해주세요. 6. MVC는 어떠한 흐름으로 요청을 처리하는지 설명해주세요. 7. 제어의 역전(IoC, Inversion of Control)에 대해 아는대로 설명해주세요. 8. 스프링에서 빈(Bean)을 등록하는 방법에 대해 말해보세요. 9. 의존성 주입(DI, Dependency Injection)에 대해 설명해주세요. 10. 스프링 빈의 라이프사이클은 어떻게 관리되는지 설명해주세요. 11. 관점지향 프로그래밍(AOP, Aspect Oriented Programming)는 무엇이고, 언제 사용할 수 있을까요? 12. Lombok 라이브러리에 대해 알고 있나요? 알고 있다면 롬복이 만드는 메소드들이 생성되는 시점은 언제인가요? 13. 서블릿(Servlet)에 대해 설명해주세요. / 서블릿의 동작 방식에 대해 설명해주세요. 14. VO와 BO, DAO, DTO에 대해 설명해주세요. 15. 대용량 트래픽에서 장애가 발생하면 어떻게 대응할 것인가요? 16. Spring의 싱글톤 패턴에 대해 설명해주세요. 17. Spring의 스코프 프로토 타입 빈에 대해 설명해주세요. 18. @Transactional의 동작 원리에 대해 설명해주세요. 19. @Transactional를 스프링 Bean의 메소드 A에 적용하였고, 해당 Bean의 메소드 B가 호출되었을 때, B 메소드 내부에서 A 메소드를 호출하면 어떤 요청 흐름이 발생하는지 설명해주세요. 20. A 라는 Service 객체의 메소드가 존재하고, 그 메소드 내부에서 로컬 트랜잭션 3개(다른 Service 객체의 트랜잭션 메소드를 호출했다는 의미)가 존재한다고 할 때, @Transactional을 A 메소드에 적용하면 어떤 요청 흐름이 발생하는지 설명해주세요. 21. @Transactional에 readOnly 속성을 사용하는 이유에 대해서 설명해주세요. 22. JPA N + 1 문제와 발생하는 이유 그리고 해결하는 방법을 설명해주세요. 23. JPA와 같은 ORM을 사용하면서 쿼리가 복잡해지는 경우에는 어떻게 해결하는게 좋을까요?

질문 출처 https://dev-coco.tistory.com/163 https://zero-base.co.kr/event/media_BE_school_qna

PARTITION BY

설문조사 통계쿼리를 작성하면서 응답자마다 몇 회차 응답인지를 보여줘야했는데 그때 PARTITION BY를 이용했다!

그전까지는 GROUP BY를 사용해서 데이터를 추출했었는데 새로운 방법을 알게되었다.

PARTITION BY

• 테이블에서 어떤 항목을 기준으로 테이블을 분리하여 순위나 순서를 나타낼때
• 테이블의 열(coulmn)을 기준으로 분리하여 표현할 때
• 전체 데이터에서 원하는 결과값을 보여줄때 편리

ROW_NUMBER( ) OVER(PARTITION BY [회원번호] ORDER BY CREATE_DATE) AS [회차]

회원번호를 기준으로 응답일로 정렬을 하고 ROW_NUMBER OVER을 통해서 번호를 매겼다.

GROUP BY

• 특정한 컬럼에 대해서 추출이 가능하지만 전체 데이터에 대해 결과를 보여주는데는 한계가 있음

2018 KAKAO BLIND RECRUITMENT

🔥 비밀 지도 🔥

👀 문제

네오가 프로도가 평소 비상금을 숨겨둔 장소를 알려줄 비밀지도를 손에 넣었다. 하지만 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다.

해독하는 방법은 아래와 같다.

1. 지도는 한변의 길이가 n인 정사각형 배열 형태로 각 칸은 공백 또는 벽('#') 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 지도 1과 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백
3. 지도1과 지도2는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록 암호를 해독하는 solution을 완성해보자.

👩‍💻 입력 & 🧙 출력

입력 형식

입력으로 지도의 한 변 크기 n과 2개의 정수배열 arr1, arr2가 주어진다. - 1 ≦ n ≦ 16 - arr1, arr2는 길이 n인 정수배열로 주어짐 - 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n이하이다. 즉, 0 ≦ x ≦ 2n - 1을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#' , 공백으로 구성된 문자열 배열로 출력

🙋‍♀️ 풀이

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[][] map = new String[n][n];
        String[] answer = new String[n];

         1️⃣
        for(int i=0;i<arr1.length;i++){

            2️⃣
            String dots1 = String.format("%0"+n+"d",Long.parseLong(Integer.toBinaryString(arr1[i])));
            char[] dot1 = dots1.toCharArray();

            String dots2 = String.format("%0"+n+"d",Long.parseLong(Integer.toBinaryString(arr2[i])));
            char[] dot2 = dots2.toCharArray();

            3️⃣
            for(int j=0;j<dot1.length;j++){
                if(dot1[j] =='0' && dot2[j] =='0'){
                    map[i][j] = " ";   
                }else if(dot1[j] == '1' || dot2[j] == '1'){
                    map[i][j] = "#";
                }

            }
        }

        4️⃣
        for(int i=0;i<map.length;i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<map[i].length;j++){
                sb.append(map[i][j]);
            }
             answer[i] = sb.toString();
        }
        return answer;
    }
}

이차원 배열 map은 두개의 지도를 합한 최종 지도의 모습을 담는 배열

1️⃣ arr1과 arr2의 길이는 같으므로 arr1의 길이만큼 반복문을 돌린다.

2️⃣ arr1과 arr2의 요소를 이진수로 바꾸고 char형의 배열에 대입한다.

    * 이진수로 바꾸기 * 
    - Integer.toBinaryString : 2진수로 바꿈
    - Long.parseLong : long자료형으로 변환
    - String.format("%0"+n+"d", ...) : ...의 형식을 n자리수 정수로 설정하고 빈공간은 0으로 채움
      String.format을 설정하지 않으면 빈공간이 출력되지 않기 때문에 꼭 해주어야함

    * char형 배열에 대입하기
    - toCharArray : String형의 dots1과 dots2를 배열로 저장


3️⃣ dot1의 길이만큼 반복하면서  dot1과 dot2의 값이 0이라면 해당 위치에는 빈값을 dot1의 값이 1이거나 dot2의 값이 1이라면 해당 위치에는 #를 대입한다.

4️⃣ map의 길이만큼 반복하면서 StringBuilder를 이용해서 각 요소를 append해주고 answer에 대입한다.

💬 다른 풀이

1. 비트연산자와 substring

class Solution {
  public String[] solution(int n, int[] arr1, int[] arr2) {
      String[] answer = new String[n];
      String temp;

      for(int i = 0 ; i < n ; i++){
            1️⃣
          temp = String.format("%16s", Integer.toBinaryString(arr1[i] | arr2[i]));
          2️⃣
          temp = temp.substring(temp.length() - n);
          3️⃣
          temp = temp.replaceAll("1", "#");
          4️⃣
          temp = temp.replaceAll("0", " ");
          5️⃣
          answer[i] = temp;
      }

      return answer;
  }
}

1️⃣ n만큼 반복하면서 비트연산자를 이용해서 arr1과 arr2의 i번째를 비교한 후 Integer.toBinaryString을 이용해서 이진수로 바꾼다. String.format을 이용해서 16자리 String으로 변환한다.

여기서의 temp는 테스트 1을 예로들어보자면 아래와 같다.
           11111
           10101
           11101
           10011
           11111


2️⃣ substring을 이용해서 temp의 길이 즉 16에서 n만큼값만큼 문자열을 제거해준다.

3️⃣ replaceAll을 이용해서 1인 부분은 "#"으로
4️⃣ 0인 부분은 " " 으로 변환한다.
5️⃣ answer의 i번째에 temp를 대입해준다.

👏 마무리

카카오문제를 스스로 풀어서 좋았는데...

실행시간 차이가 심하게 많이 나는걸 보고는 내코드가 💩인걸 깨달았다. 그리고 비트연산자를 사용할 생각을 했었다면 버거롭게 하나하나 비교하고 다시 담는 과정은 하지 않았을것이다.

왜 나아지질 않는걸까

2018 KAKAO BLIND RECRUITMENT

🔥 다트게임 🔥

👀 문제

다트게임의 점수로직을 이해한 후, 0 ~ 10의 정수와 문자 S,D,T,*,# 로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 완성하자

1. 다트게임은 총 3번의 기회
2. 각 기회마다 얻을 수 있는 점수는 0~10
3. 점수와 함께 S,D,T영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱으로 계산됨
4. 옵션으로 스타상(*), 아차상(#)이 존재하면 스타상 당첨 시 해당 점수와 바로 전에 얻은 점수를 각각 2배로 만듬, 아차상 당첨 시 해당 점수는 마이너스됨
5. 스타상은 첫번째 기회에서도 나올 수 있고, 이 경우에는 첫번째 스타상의 점수만 2배가 됨
6. 스타상의 효과는 다른 스타상과 중첩될 수 있음
7. 스타상의 효과는 아차상과 중첩될 경우 중첩된 아차상의 점수는 -2배가 됨
8. S,D,T는 점수마다 하나씩 존재함
9. 스타상, 아차상은 점수마다 둘 중 하나만 존재할 수 있고, 존재하지 않을 수도 있음

👩‍💻 입력 형식

"점수|보너스|[옵션]"으로 이루어진 문자열 3세트 ex) 1S2D*3T - 정수는 0에서 10사이의 정수 - 보너스는 S,D,T 중 하나 - 옵션은 *이나 # 중 하나이며, 없을 수도 있음

🧙 출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 점수값을 출력 ex) 37

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

class Solution {
    public int solution(String dartResult) {
        int answer = 0;

        1️⃣
        char[] c = dartResult.toCharArray();
        2️⃣
        int[] score = new int[3]; 
        3️⃣
        int round = -1;

        4️⃣
        for(int i=0;i<c.length;i++){
            5️⃣
            if('0' <= c[i] && c[i] <= '9'){
                round++;
                score[round] += Integer.parseInt(String.valueOf(c[i]));

                6️⃣
                //점수가 10점일 때
                if(c[i] == '1' && c[i+1] == '0'){
                    score[round] -= Integer.parseInt(String.valueOf(c[i]));
                    score[round] = 10;
                    i++;
                }  
             7️⃣
            }else if(c[i] == 'D'){
                score[round] *= score[round];
            }else if(c[i] == 'T'){
                score[round] *= score[round]*score[round];
             8️⃣
            }else if(c[i] == '*'){
                if(round > 0) score[round-1] *=2;
                score[round] *=2;
            }else if(c[i] == '#'){
                score[round] *= -1;
            }
        }
        9️⃣
        answer = score[0]+score[1]+score[2];

        return answer;
    }
}

문제보고 감도 못 잡고 방황했다ㅎㅎ 씨름하다가 결국 다른분들의 풀이를 찾아본 후에야 문제를 해결할 수 있었다.

1. toCharArray로 dartResult를 char형의 배열로 변환한다.
2. 3번의 게임의 각각의 점수를 저장할 score변수 선언
3. 몇번째 게임인지를 파악하는 round는 -1로 초기화해서 선언
4. c의 길이만큼 반복문을 돌리면서 dartResult를 하나하나 살펴볼것이다.
5. 만약 c의 i번째의 값이 '0'보다 같거나크거고 '9'와 같거나 작다면 round를 +1하고 score의 round에 c의 i번째 값을 대입한다.
6. c의 i번째가 '1'이고 i+1번째가 '0'이면 점수가 10점인 경우를 말한다. 따라서 score의 round번째에 있던 값을 제거해주고 10을 대입한다. 그리고 i++를 통해서 다음으로 넘어가도록 한다.
7. c의 i번째가 D라면 2배 T라면 3배
8. c의 i번째가 *이면 score의 round번째를 2배해주고 만약 round가 0보다 크다면 round-1의 점수도 2배해준다.
9. answer의 값은 scroe의 0,1,2번째를 합한 값이다.

👏 마무리

2021 Dev-Matching

🔥 로또의 최고 순위와 최저 순위 🔥

👀 문제

로또의 순위는 아래의 표를 기준으로 정해진다.

로또를 구매한 민우가 동생의 낙서로 일부 번호를 알아볼 수 없게 되었다. 자신이 구매한 로또로 당첨이 가능했던 최고순위와 최저순위를 알아보고자 한다.

알아볼 수 없는 번호를 0으로 표기해서 알아보자. 민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어진다. 이때 당첨 가능한 최고순위와 최저순위를 차례대로 배열에 담아서 return하는 solution을 완성해보자.

✔️ 조건

• lottos는 길이 6인 정수 배열입니다.
• lottos의 모든 원소는 0 이상 45 이하인 정수입니다.
  • 0은 알아볼 수 없는 숫자를 의미합니다.
  • 0을 제외한 다른 숫자들은 lottos에 2개 이상 담겨있지 않습니다.
  • lottos의 원소들은 정렬되어 있지 않을 수도 있습니다.
• win_nums은 길이 6인 정수 배열입니다.
• win_nums의 모든 원소는 1 이상 45 이하인 정수입니다.
  • win_nums에는 같은 숫자가 2개 이상 담겨있지 않습니다.
  • win_nums의 원소들은 정렬되어 있지 않을 수도 있습니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        int n=0; //일치하는 개수
        int zero = 0; //0의 개수

        for(int i=0;i<lottos.length;i++){
            if(lottos[i] == 0){
                zero++;
            }
            for(int j=0;j<win_nums.length;j++){
                if(lottos[i] == win_nums[j]){
                    n++;    
                }
            }

        }

        if(n==0 && zero ==0){
            answer[0] = 6-(n+zero) ;
            answer[1] = 6-n;    
        }else if(zero==6){
            answer[0] = 1 ;
            answer[1] = 6;    
        }else{
            answer[0] = 7-(n+zero) ;
            answer[1] = 7-n;
        }

        return answer;
    }
}

밑에 조건문이 너무 많이서 별로였는데 다른 코드를 보니 간단히 줄일 수 있었다.

최저순위와 최고순위로 변수로 두고 6보다 큰 경우만 조건문으로 구현했다.

int max = 7-(n+zero);
int min = 7- n;

if(max>6) max = 6;
if(min>6) min = 6;

return new int[] {max,min};

프로그래머스-소수만들기문제를 해결하면서 조합코드를 찾아보게 되었고 그 외에 순열과 중복이 가능한 경우에 대해서 공부가 필요하다고 생각되서 정리해보았다.

🦖 순열 - Permutation

서로 다른 n개에서 r개를 뽑아서 정렬하는 경우의 수

순열에서는 순서가 중요하기 때문에 [1,2] 와 [2,1]은 순서가 다르므로 다른 경우의 수로 카운팅한다.

public class AlgorithmStudy {
    1️⃣
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
        2️⃣
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        3️⃣
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                4️⃣
                permutation(arr, out, visited, depth+1, r);
                visited[i] = false;
            }
        }
    }
    5️⃣
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
}

1️⃣ permuataion은 main에서 호출된다.
    - int[] arr : 순열을 구할 배열
    - int[] out : main에서 new int[r] / 즉, 몇개씩 뽑을지
                  순서대로 방문한 원소를 저장해야하므로 선택된 원소를 순서대로 저장할 배열 
    - boolean[] visited : 중복해서 선택하는 것은 불가능하므로 visited를 
                        이용해서 이미 선택한 원소를 다시 선택하지 않도록 함
    - int depth : r만큼 반복하기 위해서 
    - int r : 몇개씩 묶을 건지

2️⃣ depth의 값과 r이 같을때
    out을 반복문을 돌리면서 해당 요소를 num으로 받아서 출력해준다.
    그리고 return을 통해서 벗어난다.

3️⃣ i를 arr의 길이만큼 반복문을 돌린다.
    만약 visited의 i번째가 false라면 해당 i번째의 값을 true로 바꾸고
    out의 depth번째에 arr의 i번째 값을 대입한다.

4️⃣ depth에 +1한 값을 대입해서 permutation을 다시 호출한다.
    다시 호출 했을 때 2️⃣의 조건문을 만족하지 못하면 반복문으로 들어오는 것이고 
    만족한다면 해당 조건문을 수행한 후 다시 돌아와서 i번째 visited의 값을 false로 바꿔준다.

5️⃣ r과 arr의 초기값을 설정해주고 permutation을 호출한다.

결과는 ❓

1 2
1 3
2 1
2 3
3 1 
3 2

🦖 중복 순열

서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수

순서가 있게 뽑는 것은 순열과 동일하지만 같은 원소를 중복해서 뽑을 수 있다는 것에 차이가 있다.

public class AlgorithmStudy {
    public static void permutation(int[] arr, int[] out, int depth, int r){
        if(depth == r){
            for(int num: out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
}

순열 코드에서 중복을 방지하기 위해 사용했던 visited부분을 제거해주면 된다.

결과는 ❓

1 1
1 2
1 3 
2 1 
2 2
2 3 
3 1 
3 2 
3 3

🦖 조합 - Combination

서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수

public class AlgorithmStudy {
    public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(visited[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new boolean[arr.length], 0, 0, r);
    }
}

순서가 상관이 없으니 [1,2]와 [2,1]이 같은 경우이기 때문에 [1,2]만 카운팅 해주어야한다. 그러기 위해서는 현재 선택한 원소보다 뒤에 있는 원소에 대해서만 탐색을 진행해야한다.

이를 위해서 탐색의 시작 index를 의미하는 start원소를 사용한다. 탐색의 기준을 start로 잡고 재귀호출시 현재 index인 i에 1을 더한 값을 start로 넣어준다.

visited를 이용해서 방문한 원소들을 순서대로 확인하면 곧 선택된 조합이다.

결과는 ❓

1 2 
1 3 
2 3

🦖 중복 조합

서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수

public class AlgorithmStudy {
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}

조합과의 차이점은 중복이 가능하다는 것이므로 중복을 체크하기 위해 사용한 visited를 제거해준다.

현재 선택한 원소보다 뒤의 것만 선택가능하지 않고 현재 선택한 원소를 포함한 뒤의 것들을 선택가능한 것이므로 재귀 호출에서 start로 i+1을 넘기던 조합코드를 그냥 i를 넘기는 것으로 수정해준다.

조합과 다르게 중복이 가능하므로 선택한 원소를 저장하는 배열이 필요함

결과는 ❓

1 1 
1 2
1 3
2 2 
2 3
3 3

📑 References

코드와 설명은 golucky.log님의 포스트를 참조

Summer/Winter Coding(~2018)

🔥 소수 만들기 🔥

👀 문제

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하자. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return하도록 solution을 완성해보자.

✔️ 조건

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

import java.util.*;

class Solution {
    1️⃣
    static int  answer = 0;

    2️⃣
    public int solution(int[] nums) {
        int r=3; 

        combination(nums, new boolean[nums.length], 0, 0, r);

        return answer;
    }

    3️⃣
    public static void combination(int[] arr , boolean[] visited, int start, int depth, int r){

        List<Integer> sum = new ArrayList<>();
        int s = 0;
        int n = 0;

        4️⃣
        if(depth == r){ 
            for(int i=0;i<arr.length;i++){ 
                if(visited[i]) {
                    s += arr[i];                    
                }
            }
            sum.add(s);

            5️⃣
            for(int i=1;i<=sum.get(0);i++){
                if(sum.get(0)%i==0){
                    n++;                
                }
            }
            6️⃣
            if(n==2){
                answer += 1;
            }

            7️⃣
            return;
        }

        8️⃣
        for(int i=start;i<arr.length;i++){ 
            if(!visited[i]){

                visited[i] = true; 

                combination(arr,visited,i+1,depth+1,r); 

                visited[i] = false; 
            }
        }
    }
}

이번 문제는 소수를 구하는 것보다 조합을 구현하는 부분이 제일 어려웠다.

조합은 서로 다른 n개에서 순서 없이 r개를 뽑는 경우의 수로 순서가 달라도 [1,2]와 [2,1]을 동일한 경우의 수로 본다.

1️⃣ Solution클래스 내에서 모두 사용할 수 있도록 static으로 answer를 선언

2️⃣ nums라는 이름의 숫자배열을 매개변수로 받고 서로다른 3가지를 고를것이기 때문에 r을 3으로 대입해준다.

    combination메서드를 호출
        - nums : 주어진 숫자 배열
        - new boolean : visited / 중복을 방지하기 위한 배열
        - 0 : start / 현재 선택한 원소보다 뒤에 잇는 원소에 대해서만 탐색하기 위함
        - 0 : depth / r과 비교하기 위해서
        - r : 3개씩 뽑을 것

3️⃣ 조합으로 구한 경우의 수들의 합을 저장하기위한 List : sum

4️⃣ 만약 depth의 값이 r과 같다면 arr의 길이만큼 반복문을 돌린다.
여기서 visited의 i번째의 값이 true라면 s에 arr의 i번째 값을 더해준다.
그리고 sum에 s를 add해준다.

5️⃣ 그리고 소수여부를 파악하기 위해서 반복문을 돌리고 소수라면 n++을 실행한다.

6️⃣ 이후 n이 2개라면 소수이기에 answer에 +1을 해준다.

7️⃣ for문이 마무리 되거나 if문이 일치하지 않았을 경우 return문으로 나온다.

8️⃣ i를 start부터 arr의 길이까지 반복하면서 만약 visited의 i번재의 값이 false라면 true로 바꿔준다.
그리고 combination 메서드를 재귀호출 한다. 
start의 값은 i+1을 depth의 값도 기존의 depth에 +1을 해주고 호출한다.

재귀호출에서 돌아온 후 i번째의 값을 false로 바꿔준다.

💬 다른 풀이

import java.util.Arrays;

class Solution {
    public int solution(int[] nums) {
        int ans = 0;

        for(int i = 0; i < nums.length - 2; i ++){
            for(int j = i + 1; j < nums.length - 1; j ++){
                for(int k = j + 1; k < nums.length; k ++ ){        
                    🐛
                    if(isPrime(nums[i] + nums[j] + nums[k])){
                        ans += 1;  
                    } 
                }
            }
        }
        return ans;
    }
    public Boolean isPrime(int num){
        int cnt = 0;
        for(int i = 1; i <= (int)Math.sqrt(num); i ++){
            if(num % i == 0) cnt += 1; 
        }
        return cnt == 1;
    }
}

프로그래머스 사이트가 개편되면서 백준허브가 작동하지 않는다... 그래서 실행시간을 확인할 수는 없지만 제출해보면 내 코드로는 13초 14초 훨씬 넘게 나오는것들이 위의 코드로는 10초 안에 끝나더라 ㅎㅎ

isPrime함수는 소수찾기에서 공부했듯이 제곱근을 이용해서 소수여부를 판단한다.

그렇다면 위에 반복문들은 뭘까 🐛가 있는 위치에서 i, j, k의 값들을 출력해보면

i는 0 j는 1 k는 2
i는 0 j는 1 k는 3
i는 0 j는 2 k는 3
i는 1 j는 2 k는 3

i가 0이고 j가 1일때 k의 반복문이 돌고 k반복문이 다 돌면 j반복문이 j가 마무리되면 마지막에 i의 반복문이 마무리된다.

👏 마무리

뭐야... 조합 안써도 풀 수 있는 거였어... 조합 너무 어려웠는데

저 코드가 왜 통과인지 알 수 없지만 이왕 이렇게 된거 조합 순열 공부해야지

조합 순열 공부 ❗️

코딩테스트 고득점 Kit_해시

🔥 완주하지 못한 선수 🔥

👀 문제

수많은 마라톤 선수들이 마라톤에 참여했다. 단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주했다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return하는 solution을 완성해보자.

✔️ 조건

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

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 첫번째 풀이

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";

        for(int i=0;i<participant.length;i++){
            for(int j=0;j< completion.length;j++){
                if(participant[i].equals(completion[j]) && completion[j] != "-1"){
                    participant[i] = "-1";
                    completion[j] = "-1";
                }      
            }
            if(participant[i]!="-1"){              
                answer = participant[i];
            }
        }
        return answer;
    }
}

1. participant의 길이만큼 반복문을 돌리면서 participant의 길이만큼 반복문을 돌린다.
2. 만약 participant의 i번째가 completion의 j번째와 같고 completion의 j번째의 값이 -1이 아니라면 participant와 completion의 i와j번째의 값을 -1로 대입해준다.
3. participant의 i번째의 값이 -1이 아니라면 answer에 해당 값을 대입해준다.

즉 participant와 completion에 동시에 존재하는 선수들의 값을 -1로 변경해주는 것이다.

하지만 이런 풀이로 풀면 테스트는 통과하지만 효율성은 전부 실패이다...

예상하기로는 이 문제는 해시를 이용해서 푸는 문제이다. 물론 나는 그렇게 풀지 않았다. 그게 문제다 문제

🙋‍♀️ 두번째 풀이

import java.util.HashMap;
import java.util.Map.Entry;


class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
           1️⃣
        HashMap<String,Integer> player = new HashMap<>();

        2️⃣
        for(String p : participant) player.put(p, player.getOrDefault(p,0)+1);

          3️⃣
        for(String c : completion) player.put(c,player.get(c)-1);

        4️⃣
        for(String key : player.keySet()){
            if(player.get(key) != 0){
                answer = key;
            }
        }
        return answer;
    }
}

위의 코드를 통해서 Map을 사용하는 것에 익숙해져보자

1️⃣ player라는 이름의 HashMap을 선언
    key : String
    value : Integer

2️⃣ 반복문을 돌리는데 participant의 각 요소를 String p라고 하자
    * put
        - hashmap에 값을 업데이트하거나 삽입할때 사용
        - replace와 큰 차이점은 키값이 없을때 put은 hashmap안에 삽입하지만 replace는 null을 반환

    * getOrDefault(Object key, V Default Value)
        - key : 값을 가져와야하는 요소의 키
        - defaultValue : 지정된 키로 매핑된 값이 없는 경우 반환되어야하는 기본값
       찾는 key가 존재하면 해당 key에 매핑되어 있는 값을 반환하고, 그렇지 않으면 디폴트 값이 반환됨

    따라서 player에 p의 값이 있다면 p에 매핑되어있는 값에 +1 없다면 0+1의 값을 put 해준다.

    해당위치에서 System.out.println(player);를 수행하면 아래와 같다
               {leo=1, eden=1, kiki=1}
            {marina=1, filipa=1, nikola=1, josipa=1, vinko=1}                    
            {ana=1, mislav=2, stanko=1}


3️⃣ completion의 각 요소를 String c라고 하자
    * get(key)
        - map안의 값 가져오기

    키값 c에 매핑되어있는 값을 가져와서 -1을 해주고 player에 다시 put해준다.

    그렇다면 completion에 이름이 있는 사람들의 값은 0이 될 것이다.

4️⃣ 반복문을 돌려서 key의 값이 0이 아닌 선수를 데려오자

    * keySet
        - key의 값만 출력해줌
    keySet메소드를 이용해서 player의 key의 값을 반복문을 돌려서 해당하는 곳의 key의 값이 0이 아닌 선수를 answer에 대입

📑 References

getOrDefault hashmap.put() 사용방법과 출력 keySet

코딩테스트 고득점 Kit_정렬

🔥 K번째 수 🔥

👀 문제

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려한다. 배열 array,[i,j,k]를 원소로 가진 2차원배열 commands가 매개변수로 주어질 때, 결과를 배열에 담아 return하는 solution을 완성해보자

✔️ 조건

• array의 길이는 1 이상 100 이하입니다.
• array의 각 원소는 1 이상 100 이하입니다.
• commands의 길이는 1 이상 50 이하입니다.
• commands의 각 원소는 길이가 3입니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

import java.util.Arrays;
import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        //List<Integer>list = new ArrayList<>(); 

        for(int i=0;i<commands.length;i++){
            int[] n = Arrays.copyOfRange(array,commands[i][0]-1,commands[i][1]);
            Arrays.sort(n);
            answer[i] = n[commands[i][2]-1];
            //list = Arrays.stream(n).boxed().collect(Collectors.toList());
            //list.sort(Comparator.naturalOrder());                
            //answer[i] = list.get(commands[i][2]-1);
        }

        return answer;
    }
}

주석이 많은 이유는 너무 쓸데없는 짓을 많이 했기 때문이다. 굳이 list로 바꾸지 않아도 되는 것을 바꿔서 문제를 해결해버려서 점수도 1점을 받았다.

제출하는데 급한것이 아니라 잘 짜여진 코드인지 한번 더 확인하고 제출해야겠다.

배열 복사하기

• Arrays.copyOfRange(oldArray, startIndex, endIndex)

코딩테스트 고득점 Kit_완전 탐색

🔥 모의고사 🔥

👀 문제

수포자들이 모의고사에서 수학문제를 전부 찍으려 한다. 1번 수포자 : 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자 : 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answer가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return하는 solution을 완성해보자

✔️ 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 풀이

import java.util.*;

class Solution { //answers의 길이만큼 나머지 1,2,3의 크기가 달라져야지
    public int[] solution(int[] answers) {
        int[] answer = {}; 

        int[] a = {1,2,3,4,5};
        int[] b = {2,1,2,3,2,4,2,5};
        int[] c = {3,3,1,1,2,2,4,4,5,5};

        int aCnt=0;
        int bCnt=0;
        int cCnt=0;

        for(int i=0;i<answers.length;i++){
            if(a[i%a.length] == answers[i]) aCnt++;
            if(b[i%b.length] == answers[i]) bCnt++;
            if(c[i%c.length] == answers[i]) cCnt++;
        }

        int  max = Math.max(aCnt,Math.max(bCnt,cCnt));

        ArrayList<Integer> list = new ArrayList<>();
        if(max == aCnt){list.add(1);}
        if(max == bCnt){list.add(2);}
        if(max == cCnt){list.add(3);}

        answer = list.stream().mapToInt(i-> i.intValue()).toArray();

        return answer;
    }
}

위의 풀이는 스스로 작성한 코드가 아니다.

다음에 다시 풀어보고 난 후에 다시!

👏 마무리

코딩테스트 고득점 Kit_탐욕법(Greedy)

🔥 체육복 🔥

탐욕법 알고리즘에 대한 설명은 다른 post 참고!

👀 문제

점심시간에 도둑이 들어서 일부 학생들의 체육복을 도난당했다. 여벌이 있는 학생들이 이들에게 체육복을 빌려주려하는데 학생들의 번호는 체격순으로 매겨져 있어 바로 앞과 뒷번호의 학생들에게만 체육복을 빌려줄 수 있습니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reverse가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return하도록 solution을 완성해보자

✔️ 조건

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

👩‍💻 입력 & 🧙 출력

🙋‍♀️ 첫번째 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {


        int answer = n;

        answer = n-lost.length;

        //도난당했지만 여분이 있는 경우
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                 //System.out.println(lost[i]+"와 "+reserve[j]);
                if(lost[i] == reserve[j]){
                    reserve[j] = -1;
                    lost[i] = -1;
                    answer = answer+1;
                    //도난당했지만 여분이 있는 학생은 빌려줄수 없지만 체육시간에 참여가능하니까 제외
                   System.out.println(lost[i]+"와 "+reserve[j]);
                }                
            }
        }

        //reserve에 있는 학생들의 앞뒤번호 학생이 lost에 있다면
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                if(lost[i] != -1 && reserve[j] !=-1){
                    if(lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1){
                        System.out.println(lost[i]+"가 "+reserve[j]+"꺼를 빌려");
                        lost[i] = -1;
                        reserve[j] = -1;

                        answer +=1;
                    }    
                }

            }
        }
        return answer;
    }
}

처음에는 lost와 reserve가 정렬되어있지 않을 것이라고는 생각하지 못해서 정렬을 하지 않고 코드를 작성해서 실패가 발생했다.

🙋‍♀️ 두번째 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reserve) {
        Arrays.sort(lost);
        Arrays.sort(reserve);

        int answer = n-lost.length;


        //도난당했지만 여분이 있는 경우
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                 //System.out.println(lost[i]+"와 "+reserve[j]);
                if(lost[i] == reserve[j]){
                    reserve[j] = -1;
                    lost[i] = -1;
                    answer = answer+1;
                    //도난당했지만 여분이 있는 학생은 빌려줄수 없지만 체육시간에 참여가능하니까 제외
                   System.out.println(lost[i]+"와 "+reserve[j]);
                }                
            }
        }

        //reserve에 있는 학생들의 앞뒤번호 학생이 lost에 있다면
        for(int i=0;i<lost.length;i++){
            for(int j=0;j<reserve.length;j++){
                if(lost[i] != -1 && reserve[j] !=-1){
                    if(lost[i] == reserve[j]-1 || lost[i] == reserve[j]+1){
                        System.out.println(lost[i]+"가 "+reserve[j]+"꺼를 빌려");
                        lost[i] = -1;
                        reserve[j] = -1;

                        answer +=1;
                    }    
                }

            }
        }



        return answer;
    }
}

1. Arrays.sort를 통해서 lost와 reserve를 정렬해주었다.
2. answer의 초기값을 전체 학생수에서 잃어버린 학생수 만큼 뺀값으로 대입한다.
3. 첫번째로 도난당했지만 여분이 있는 학생들을 찾아서 해당 인덱스의 값을 -1로 변경해준다. 그리고 해당 학생들은 여분이 있어서 체육수업에 참여할 수 있으므로 answer에 값을 +1해준다.
4. 두번째로는 reserve에 있는 학생들의 앞뒤 번호 학생이 lost한 학생일 경우를 구해준다. 여기서 중요한 점은 lost[i]와 reserve[ㅓ]의 값이 -1인 학생은 제외시켜야한다는 점이다. 그후, lost의 i번째가 reserve의 j번째 -1 번째 또는 +1 번째에 존재한다면 해당 인덱스번째의 값을 -1로 대입해주고 answer에 +1을 해준다.

👏 마무리

체육복 도둑질 하지 마세요