IPv4

JSON 형식 전송

• POST http://localhost:8080/request-body-json
• content-type = application/json
• message body : {"username" : "hello", "age" : 20 }
• 결과 : messagebody = {"username" : "hello", "age" : 20 }

JSON 형식 파싱 추가

JSON 형식으로 파싱할 수 있게 객체를 하나 생성

테스트 해보기

1) 소스코드는 Text 로 작성하는 것과 같습니다.

@WebServlet(name = "requestBodyJsonServlet", urlPatterns = "/request-body-json")
public class RequestBodyJsonServlet extends HttpServlet {
    @Override
    protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        ServletInputStream inputStream = request.getInputStream();
        String messageBody = StreamUtils.copyToString(inputStream, StandardCharsets.UTF_8);

        System.out.println("messageBody : " + messageBody);
    }
}

2) Postman 에서 JSON 데이터 사용하기

raw 에서 JSON 으로 변경만 해주면 됩니다.

3) 정상 작동 확인

JSON 데이터를 Java 객체로 변환하기

: JSON 을 변환시켜주는 라이브러리 필요

1) ObjectMapper object 객체 생성 ( SpringBoot 에서 기본적으로 지원해줌 )

2) objectMapper.readValue ( 메세지, Class ) 실행

3) 해당 메서드를 통해 자바 객체를 사용할 수 있게 됩니다.

[ 소스코드 ]

private ObjectMapper objectMapper = new ObjectMapper();

@Override
protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        ServletInputStream inputStream = request.getInputStream();
        String messageBody = StreamUtils.copyToString(inputStream, StandardCharsets.UTF_8);

        System.out.println("messageBody : " + messageBody);

        helloData helloData = objectMapper.readValue(messageBody, helloData.class);

        System.out.println("username : "+helloData.getUsername());
        System.out.println("age : "+helloData.getAge());

        response.getWriter().write("ok");
}

정상 출력됨이 확인됩니다.

HTTP 요청 메시지를 통한 데이터 전달 방법

GET

• /url ? username = hello & age = 20
• 메시지 바디 없이 URL 의 쿼리 피라미터에 데이터를 포함해서 전달
• ex. 검색, 필터, 페이징 등에서 많이 사용하는 방식

[ 소스 코드 ]

package servletTest.servlet.request;

import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.io.IOException;

@WebServlet(name = "requestParamServlet", urlPatterns = "/request-param")
public class RequestParamServlet extends HttpServlet {
    @Override
    protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {

        System.out.println("전체 파라미터 조회 - start");
        request.getParameterNames().asIterator().forEachRemaining(paramName -> System.out.println(paramName + " : " + request.getParameter(paramName)));
        System.out.println("전체 파라미터 조회 - end");

        System.out.println("단일 파라미터 조회 - start");
        String username = request.getParameter("username");
        String age = request.getParameter("age");

        System.out.println("username = " + username);
        System.out.println("age = " + age);
        System.out.println();
        System.out.println("단일 파라미터 조회 - end");

        System.out.println("중복되는 복수 파라미터 조회");
        String[] usernames = request.getParameterValues("username");
        for (String i : usernames) {
            System.out.println("username = " + i);
        }

    }
}

* 여기서 주의할 점은 복수 파리미터에 대한 부분입니다.

http://localhost:8080/request-param?username=hello&age=20&username=hello2

와 같은 url 로 username 을 중복해서 부르게 된다면 그 값이 없어지는게 아니라,

username 안에 두 값을 받아오게 됩니다.

그래서 값들을 담는 배열 객체를 만들어 저장 후 출력이 가능합니다.

POST

• content-type : application / x-www.form-urlencoded
• 메시지 바디에 쿼리 피라미터 형식으로 전달 username = hello & age = 20 ( url 형태와 비슷함 )
• ex. 회원 가입, 상품 주문, HTML form 사용

1) POST 를 사용하려면 HTML Form이 필요합니다.

- webapp/basic 경로에 hello-form.html 을 생성해줍니다.

- http://localhost:8080/basic/hello-form.html 로 브라우저 접속

[ 폼 형태 ]

<form action="/request-param" method="post">
    username: <input type="text" name="username" />
    age: <input type="text" name="age" /> <button type="submit"> 전송 </button>
</form>

위의 폼을 보면 다음을 알 수 있습니다.

Form 전송을 누르게 되면 이전에 서블릿 경로로 만들어놨던 "/request-param" 경로로 전송하게 됩니다.

개발자도구를 켜서 폼 데이터를 보면 데이터가 제대로 들어왔음을 확인할 수 있습니다.

2) 위 데이터를 컨텐트 바디에 보내게 됩니다.

다음과 같이 엔코딩되어 전송 됩니다.

3) 데이터 확인

데이터가 정상적으로 출력되고 있음이 확인가능합니다.

[ 중간 정리 ]

1) request.getParameter 형식은 GET / POST 둘 다 지원한다.

2) POST 는 브라우저가 알아서 형식을 만들어서 전송한다.

3) GET 은 사용자가 Url 을 입력한다.

4) 즉, 클라이언트 입장에선 다르게 작성하지만

          서버입장에선 GET/POST 구분없이 조회가 가능합니다.

Q. 그럼 위와 같은 HTTP 메서드 테스트를 할 때, 매번 Html 파일을 만들어야 하는가?

A. 아니다. Postman 을 활용하자 !!

위의 과정을 Postman 을 통해 테스트한 결과, 200 OK가 나오면 정상 작동하는 것입니다.

HTTP message body 에 데이터 직접 담아서 요청

• HTTP API 에서 주로 사용
• JSON, XML, TEXT
• 데이터 형식은 주로 JSON 사용
• POST, PUT, PATCH

[ 소스 코드 ]

@WebServlet(name = "requestBodyStringServlet", urlPatterns = "/request-body-string")
public class RequestBodyStringServlet extends HttpServlet {
    @Override
    protected void service(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException {
        ServletInputStream inputStream = request.getInputStream();// 메세지 바디의 코드를 바이트 코드로 얻을 수 있음
        String messageBody = StreamUtils.copyToString(inputStream, StandardCharsets.UTF_8);// StreamUtils 를 통해 인코딩 정보를 알려주고 바이트 코드로 변환 시켜줌

        System.out.println("messageBody : " + messageBody);
        response.getWriter().write("ok");
    }
}

[ Postman Test ]

정상적으로 출력됨을 볼 수 있습니다.

HttpServletRequest 역할

- HTTP 를 직접 파싱하는 경우

: 메시지를 개발자가 직접 파싱해서 사용해도 되지만, 매우 할 일이 많아집니다.

- 서블릿 필요 이유

서블릿은 개발자가 HTTP 요청 메시지를 편리하게 사용할 수 있도록 개발자를 대신해서 HTTP 요청 메시지를 파싱합니다.

- HttpServletRequest 의 존재 이유

그 요청 메시지에 대한 결과를 HttpServletRequest 객체에 담아서 제공합니다.

HttpServletRequest 예시

- HTTP 요청 메시지

POST /save HTTP/1.1
Host : localhost: 8080
Content-Type : application/x-www-form-urlencoded

username=park&age=20

이와 같은 요청 메시지를 직접 매번 파싱한다는 의미입니다. 

각 문장에 대해 HttpServletRequest 가 하는 역할은

- 첫 번째 줄 : START LINE [ HTTP 메소드, URL, 스키마 ]

- 두, 세 번째 줄 : 헤더 [ 헤더 조회 ]

- 바디 : 한 줄 띄우고 나머지 부분 [ form 피라미터 형식 조회, 메세지 바디 데이터 직접 조회 ]

 HttpServletRequest 객체의 여러가지 기능

- 임시 저장소 기능

HTTP 요청이 시작부터 끝날 때 까지 유지되는 임시 저장소 기능

request.setAttribute ( name, value )

request.getAttribute ( name )

- 세션 관리 기능

request.getSession ( create: true )

HTTP Request 해보기

PostMan 설치 후 HTTP 메서드를 테스트 해봤습니다.

위와 같이 Request 메서드에 대해 print 할 수 있는 메서드를 작성하였습니다.

그 후 POST 로 메세지를 보내면

위와 같이 요청 메시지가 정상적으로 들어옴을 확인할 수 있습니다.

ㅇ WAR 로 패키징하기 ( Spring Initailize )

JAR 가 아닌 WAR 로 패키징하면 톰캣에 직접 넣을 수도 있고, 스프링 부트의 내장 톰캣에서 띄울 수도 있습니다.

그래서 서블릿으로 페이지를 구현하려면 WAR 를 사용해야 합니다.

ㅇ @ServletComponentScan

서블릿을 찾아 자동으로 등록해줍니다.

ㅇ HttpServlet 상속받기

- 서블릿을 구현하려면 HttpServlet 을 상속받아야 합니다.

ㅇ WebServlet ( name = " Servlet name ", urlPatterns = " url 경로 " )

서블릿의 Url 경로를 설정

ㅇ 서비스 메서드 생성

서블릿이 호출되면 서비스 메서드가 호출 됩니다.

ㅇ 서블릿 요청 및 응답 해보기

- 서블릿 요청 :

String username = request.getParameter("username");

위 메서드를 통해 

http://localhost:8080/hello?username=kim 를 브라우저에 입력하게 되면

브라우저에 입력된 값이 요청되는 것을 알 수 있습니다.

- 서블릿 응답 :

response.setContentType("text/plain");
response.setCharacterEncoding("utf-8");
response.getWriter().write("hello" + username);

위 메서드를 통해

이러한 응답 메세지가 전송됨을 알 수 있습니다.

ㅇ 개발 단계에 로깅 찍어보기

logging.level.org.apache.coyote.http11=debug

ㅇ 인덱스 페이지 만들어보기

webapp 경로에 index.html 생성

백엔드 개발자가 서비스를 제공할 때 고려해야할 요소

1. 정적 리소스를 어떻게 제공할 것인지?

2. 동적 HTML 페이지를 어떻게 제공할 것인지?

3. HTTP API 어떻게 제공할 것인지?

서버사이드 렌더링, 클라이언트 사이드 렌더링

1) SSR - Server Side Rendering

• HTML 최종 결과를 서버에서 만들어 웹 브라우저에 전달

즉, 동적으로 생성된 최종 결과물이 서버에서 다 생성되고, 웹브라우저는 다 생성된것을 보여주기만 한다.

• 주로 정적인 화면에 사용
• JSP, 타임리프 -> 백엔드 개발자

2) CSR - Client Side Rendering

• HTML 결과를 자바스크립트를 사용해 웹 브라우저에 동적으로 생성해 적용
• 주로 동적인 화면에서 사용
• 웹 환경을 마치 앱처럼 필요한 부분부분 변경 가능
• ex. 구글 지도, Gmail, Google Calender
• React, Vue.js -> 웹 프론트엔드 개발자

* 참고

- React , Vue.js 를 CSR + SSR 동시에 지원하는 웹 프레임워크도 있음

- SSR 을 사용하더라도, 자바스크립트를 사용해서 화면 일부 동적으로 변경 가능

그렇다면 백엔드 개발자 입장에서는 어디까지 알아야 하는가?

1. 백엔드 - SSR

• JSP , Thymeleaf
• 화면 정적이고, 복잡하지 않을 때 사용
• 백엔드 개발자는 SSR 기술 학습 필수

2. 선택과 집중

• 백엔드 개발자는 CSR 의 기술 학습은 옵션
• 서버, DB, Infra 등 수많은 백엔드 기술 공부해야함

쓰레드

• 애플리케이션 코드를 순차적으로 실행하는 것은 쓰레드
• 자바 메인 메서드를 처음 실행하면 main 쓰레드 실행
• 쓰레드가 없으면 자바 애플리케이션 실행 불가능
• 쓰레드는 한번에 하나의 코드 라인만 수행
• 동시 처리가 필요하면 쓰레드 추가 생성

쓰레드가 하나일 때 발생하는 문제

- 상황 :

1) 요청1이 연결을 요청하고 서블릿 컨테이너에서 처리를 하는데 지연 처리 되는 중

2) 요청2가 연결을 요청하면서 쓰레드를 대기

3) 이러면 요청1, 요청2가 둘 다 죽게 됨

- 해결방법 :

요청2에 대한 신규 쓰레드를 생성해준다.

요청이 올때마다 쓰레드를 생성하면 발생하는 문제

- 장점

1) 동시 요청 처리 가능

2) CPU, Memory 가 허용할 때까지 처리가 가능

3) 하나의 쓰레드가 지연되어도 나머지 쓰레드는 정상 작동함

- 단점

1) 쓰레드는 생성 비용이 비쌈 ( 고객 요청올 때 마다 쓰레드 생성하면 응답속도가 느려짐 )

 ex. 수강신청 사이트에서 학생들이 수강신청을 갑자기 많이하면 쓰레드가 너무 많이 생성되 서버가 터짐

2) 쓰레드는 컨텍스트 스위칭 비용이 발생

3) 쓰레드 생성에 제한이 없음

쓰레드 풀

: 요청마다 쓰레드 생성의 단점 보완

- 특징

1) 필요한 쓰레드를 쓰레드 풀에 보관하고 관리

2) 쓰레드 풀에 생성 가능한 쓰레드의 최대치를 관리 ( 톰캣은 최대 200개가 기본 설정 - 변경가능 )

 ex. tomcat 의 MaxConnection 관련 설정

- 사용

1) 쓰레드가 필요하면, 이미 생성되어 있는 쓰레드를 쓰레드 풀에 꺼내서 사용

2) 사용 종료하면 쓰레드 풀에 해당 쓰레드를 반납

3) 최대 쓰레드가 모두 사용중이어서 쓰레드 풀에 쓰레드가 없으면?

 -> 기다리는 요청을 거절 or 특정 숫자만큼 대기하도록 설정

- 장점

1) 쓰레드가 미리 생성되어 있으므로, 쓰레드를 생성하고 종료하는 비용이 절약됨 ( 응답이 빠름 )

2) 생성 가능한 쓰레드의 최대치가 있으므로 너무 많은 요청이 들어와도 기존 요청 안전하게 처리 가능

쓰레드 풀 실무 적용

• WAS 의 주요 튜닝 포인트는 최대 쓰레드 수이다. ( 튜닝을 잘하는게 중요 !! )
• 최대 쓰레드 수를 너무 낮게 설정하면 [ 리소스는 여유롭지만, 동시 요청의 수가 많아지면 클라이언트 응답이 지연됨 ]
• 최대 쓰레드 수를 너무 높게 설정하면 [ 동시요청이 많아지면, 리소스의 임계점 초과로 서버가 다운됨 ]
• 장애가 발생하면 [ 클라우드면 서버부터 늘리고, 튜닝 ] [ 클라우드가 아니면 그냥 튜닝 ]

쓰레드 풀 적정 숫자 찾는 방법

• 애플리케이션 로직 복잡도, CPU, Memory, IO 리소스 상황에 따라 모두 다름
• 성능 테스트 ( 툴 : 아파치 ab, 제이미터, nGrinder ) - 최대한 실제 서비스와 유사한 성능 테스트 시도

WAS 의 멀티 쓰레드 지원 ( WAS 의 필요성 !! )

• 멀티 쓰레드에 대한 부분은 WAS 가 처리
• 개발자가 멀티 쓰레드 관련 코드를 신경쓰지 않아도 됨
• 개발자는 싱글 쓰레드 프로그래밍을 하듯 편리하게 소스 코드 개발
• 하지만 싱글톤 객체는 주의해서 사용 ( 서블릿, 스프링 빈 )

서블릿을 왜 써야하는가 ?

HTTP, 비지니스 로직을 처음부터 구성하는 경우

- TCP/IP 연결 대기, 소켓 연결

- HTTP 요청 메시지 파싱해서 읽기

- URL 인지

- Content-Type 확인

- 비지니스 로직 실행

- HTTP 메시지 바디 / 응답 메시지 생성

등 위와 같은 코드를 직접 다 써야합니다.

하지만 서블릿을 사용하는 경우 비지니스 로직을 제외한 모든 기능을 다 지원해줍니다.

서블릿 특징

- Url 에 /hello 를 치면 위 코드가 호출되어 서블릿 코드가 실행되게 됩니다.

- HttpServletRequest : HTTP 요청 정보를 편리하게 사용할 수게 해줌

- HttpServletResponse : HTTP 응답 정보를 편리하게 제공할 수 있게 해줌

- 개발자는 service 에 비지니스 로직만 작성함으로써 HTTP 스펙을 편리하게 사용함

서블릿 동작 과정

1) 웹 브라우저에서 localhost:8080/hello 

2) Url 에 HTTP 요청메시지 전송 ( response / request )

3) 서블릿 컨테이너에서 HTTP 요청을 실행

4) 종료와 동시에 웹 브라우저에 reponse 응답 메시지 전송

HTTP 요청시 발생하는 과정들

1) WAS : Reponse / Request 객체 만들어 서블릿 객체 호출

2) 개발자 : Request 객체에서 HTTP 요청 정보 꺼내서 사용

3) 개발자 : Reponse 객체에 HTTP 응답 정보 입력

4) WAS : Reponse 깨체에 담겨 있는 내용으로 HTTP 응답 정보 생성

서블릿 컨테이너

- 서블릿 객체를 생성, 초기화, 호출, 종료하는 생명주기 관리

- 서블릿 객체는 싱글톤으로 관리

• 고객이 요청올 때마다 계속 객체를 생성하는 것은 비효율
• 최초 로딩 시점에 서블릿 객체를 미리 만들어두고 재활용
• 모든 고객 요청은 동일한 서블릿 객체 인스턴스에 접근
• 공유 변수 사용
• 서블릿 컨테이너 종료시 함께 종료

- JSP 도 서블릿으로 변환되어서 사용

- 동시 요청을 위한 멀티 쓰레드 처리 지원

상황 : Controller 에서 Templates 경로의 View 를 반환하는데 404가 발생

다음의 상황에서 localhost:8080/testMain 를 접속하면 404가 뜨는 것을 볼 수 있습니다.

이 경우, 다음과 같은 설정을 해줘야 합니다.

위의 설정을 하나하나 뜯어보도록 하겠습니다.

WebMvcConfigurer

WebMvcConfigurer 을 사용하면 @EnableWebMvc 가 자동적으로 세팅해주는 설정에 개발자가 원하는 설정을

추가할 수 있습니다.

@EnableWebMvc

Spring Framework 에서 여러 Config 값을 알아서 세팅해줍니다.

addResourceHandler

정적인 Resource 를 처리하기 위해 사용되는 Handler 입니다.

기본적으로 서블릿 컨테이너에는 정적인 자원을 처리할 수 있는 서블릿이 등록되어 있습니다.

그래서 프로젝트를 생성하고 아무 설정을 안해도 리소스 요청에 동작을 합니다. ( ex. static Directory )

하지만, 특정 요청에 대한 리소스를 컨트롤해야 한다면 리소스 핸들러를 정의해서 config 에 등록해줘야 합니다.

이때, addResource Handler 메서드를 통해 어느 경로로 들어왔을 때 매핑이 되어줄 것인지를 정의해줍니다.

registry.addResourceHandler("/static/**")

이후 addResourceLocations 메서드를 통해 실제 파일이 있는 경로를 설정해줍니다.

그래서 보면 Main 경로가 있는 templates 와 css/js 파일이 있는 static 을 경로 설정을 해줬습니다.

만약, static 경로를 css / js 등등을 따로 나눠서 잡아야 한다면 다음과 같이 설정해줘야 합니다.

registry.addResourceHandler("/css/**").addResourceLocations("classpath:/css").setCachePeriod(false)
registry.addResourceHandler("/js/**").addResourceLocations("classpath:/js").setCachePeriod(false)

stream 활용해 list 최소, 최대값 구하기

1) IntStream 으로 변환하는 경우

List<Integer> list = Arrays.asList(2,3,6,4,12);
Integer minValue = list.stream().mapToInt(x->x).min().orElseThrow(NoSuchElementException::new);

mapToInt()

stream 에서 Int 원시 스트림으로 변환

min()

최솟값을 구하는데, 결과값을 Optional로 반환한다.

orElseThrow()

결과 값이 없는경우 괄호안의 예외를 throw 한다.

2. IntStream 으로 변환하지 않는 경우

List<Intger> list = Arrays.asList(2,3,7,1,5,4);
Integer maxValue = list.stream().max(Comparator.comparing(x->x)).orElseThrow(~~);

Comparator.comparing(x->x)

두 매개 변수 객체를 비교해주는 것입니다.

자기 자신의 상태가 어떻든 상관없이 피라미터로 들어오는 두 객체를 비교하는 것

* comparable : 자기 자신과 매개변수 객체를 비교하는 것

다음 큰 숫자

	- 문제 : n의 다음 튼 숫자를 정의해라
     1) n 보다 큰 자연수
     2) n 을 2진수로 변환했을 때 1의 갯수
     3) 조건 1,2를 만족하는 수 중 가장 작은 수

     - 과정 :
     1) 2진수로 변환 후 갯수 구한다. (k)
     2) n을 증가시키며 k를 비교한다.

위 과정을 소스코드로 구현하면 다음과 같습니다.

[ 소스 코드 ]

public class 다음큰숫자 {

    /**
     - 문제 : n의 다음 튼 숫자를 정의해라
     1) n 보다 큰 자연수
     2) n 을 2진수로 변환했을 때 1의 갯수
     3) 조건 1,2를 만족하는 수 중 가장 작은 수

     - 과정 :
     1) 2진수로 변환 후 갯수 구한다. (k)
     2) n을 증가시키며 k를 비교한다.
     **/

    public static void main(String[] args) {
        System.out.println(solution(78));
    }

    public static int solution(int n) {
        int answer = 0;
        String s = Integer.toBinaryString(n);
        int nLen = 0;
        for (int i = 0; i < s.length(); i++) {
            if('1' == s.charAt(i)) nLen++;
        }

        int oneLen = 0;
        while(n <= 1000000){
            n += 1;
            String s2 = Integer.toBinaryString(n);
            for (int i = 0; i < s2.length(); i++)
                if('1' == s2.charAt(i)) oneLen++;
            if(nLen == oneLen) break;
            oneLen = 0;
        }

        answer = n;
        return answer;
    }
}

124 나라의 숫자

위 문제를 단순히 나머지3으로 구하려고 하면 문제가 풀리지 않는다는 것을 알 수 있습니다.

	
    - 문제 :
     124 나라에서는 10진법이 아닌 자신만의 규칙으로 수를 표현
     1) 자연수만 존재
     2) 모든 수를 표현할 때, 1/2/4 만 사용
     ex. 3 = 4, 4 = 11, 5 = 12, 6 = 14 ...

     - 출력:
     n 이 입력됬을 때, 124 나라에서 사용하는 숫자로 바꾼 값을 반환해라

     - 공식:
     1) 입력 n이 들어온다.
     2) n의 나머지 3을 구해 k값을 뽑는다.
     3) k 값은 [ 4, 1, 2 ] 배열의 인덱스 값을 의미한다.
     4) n을 3으로 나눠준다.
     5) 이때, 나머지가 0이면 나눠떨어지는 것이므로 n을 3으로 나눈 후 -1을 해준다.

위의 공식을 코드로 구현하면 다음과 같습니다.

[ 소스 코드 ]

public class 나라의숫자 {

    /**
     - 문제 :
     124 나라에서는 10진법이 아닌 자신만의 규칙으로 수를 표현
     1) 자연수만 존재
     2) 모든 수를 표현할 때, 1/2/4 만 사용
     ex. 3 = 4, 4 = 11, 5 = 12, 6 = 14 ...

     - 출력:
     n 이 입력됬을 때, 124 나라에서 사용하는 숫자로 바꾼 값을 반환해라

     - 공식:
     1) 입력 n이 들어온다.
     2) n의 나머지 3을 구해 k값을 뽑는다.
     3) k 값은 [ 4, 1, 2 ] 배열의 인덱스 값을 의미한다.
     4) n을 3으로 나눠준다.
     5) 이때, 나머지가 0이면 나눠떨어지는 것이므로 n을 3으로 나눈 후 -1을 해준다.

     **/

    public static void main(String[] args) {
        System.out.println(solution(5));
    }

    public static String solution(int n) {
        String answer = "";
        String[] number = {"4", "1", "2"};

        while (n > 0) {
            int reminder = n % 3;
            n /= 3;
            if(reminder == 0) n--;
            answer = number[reminder] + answer;
        }

        return answer;
    }
}

[ 입출력 예제 ]

- 캐시 크기 : 3

- 과정

1) seoul, pangyo, jeju : 15

2) newyork, seoul, pangyo : 20

3) la, newyork, seoul : 25

5) jeju, la, newyork : 30

6) pangyo, jeju, la : 35

7) seoul, pangyo, jeju : 40

8) newyork, seoul, pangyo : 45

9) la, newyork, seoul, pangyo : 50

[ 출력 ]

- 실행시간 : 50

[ 소스코드 ]

1) 첫번째 제출

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class 캐시 {

    /**
     - 설명 :
     1. 테스팅 업무는 어피치
     2. 제이지가 작성한 데이터베이스에서 게시물 불러오는 부분의 실행시간이 오래걸림
     3. 어피치는 제이지에게 해당 로직 개선하라고 지시
     4. 제이지는 DB 캐시를 적용하여 성능 개선을 시도하지만 효율적인 캐시 크기를 몰라 난감

     - 입력 형식 :
     캐시 크기 ( cacheSize ), 도시 이름 배열 ( cities )

     - 입력 조건 :
     공백, 숫자, 특수문자 등이 없는 영문자
     대소문자 구분안함
     최대 20자

     - 조건 :
     캐시 교체 알고리즘 > LRU 사용
     cache hit일 경우 실행 시간은 1
     cache miss일 경우 실행 시간은 5

     - 용어 설명 :
     1) 캐시 히트 = 캐시 메모리에 찾는 데이터가 존재했을 때
     2) 캐시 미스 = 캐시 메모리에 찾는 데이터가 존재하지 않았을 때
     **/

    public static void main(String[] args) {
        int cache = 3;
        String[] cities = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        System.out.println(solution(cache, cities));
    }


    public static int solution(int cacheSize, String[] cities) {
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase(Locale.ROOT);
        }
        int answer = LRU(cacheSize, cities);
        return answer;
    }

    public static int LRU(int s, String[] cities){
        List<String> temp = new ArrayList<>();
        int excuteTime = 0;
        int cnt = 0;
        boolean check = false;

        while (cnt < cities.length) {
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i).equals(cities[cnt])) {
                    excuteTime += 1;
                    temp.add(0, cities[cnt]);
                    check = true;
                    break;
                }
            }
            
            if (!check){
                temp.add(0, cities[cnt]);
                excuteTime += 5;
            }

            if (temp.size() > s) {
                temp.remove(temp.size() - 1);
            }

            cnt++;
            check = false;
        }

        return excuteTime;
    }
}

테스트 9번부터 실패가 발생함을 볼 수 있습니다.

그 이유는 기존의 캐시에 같은 값이 있는 경우 기존의 값을 삭제해주고 최신화를 해줘야하는데 이 부분을 놓쳤기 때문입니다.

( 추가된 부분 )

[ 정답 소스 코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;

public class 캐시 {

    /**
     - 설명 :
     1. 테스팅 업무는 어피치
     2. 제이지가 작성한 데이터베이스에서 게시물 불러오는 부분의 실행시간이 오래걸림
     3. 어피치는 제이지에게 해당 로직 개선하라고 지시
     4. 제이지는 DB 캐시를 적용하여 성능 개선을 시도하지만 효율적인 캐시 크기를 몰라 난감

     - 입력 형식 :
     캐시 크기 ( cacheSize ), 도시 이름 배열 ( cities )

     - 입력 조건 :
     공백, 숫자, 특수문자 등이 없는 영문자
     대소문자 구분안함
     최대 20자

     - 조건 :
     캐시 교체 알고리즘 > LRU 사용
     cache hit일 경우 실행 시간은 1
     cache miss일 경우 실행 시간은 5

     - 용어 설명 :
     1) 캐시 히트 = 캐시 메모리에 찾는 데이터가 존재했을 때
     2) 캐시 미스 = 캐시 메모리에 찾는 데이터가 존재하지 않았을 때
     **/

    public static void main(String[] args) {
        int cache = 3;
        int cache2 = 0;
        int cache3 = 2;
        String[] cities = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        String[] cities2 = {
                "Jeju", "Pangyo", "Seoul", "NewYork", "LA"
        };
        String[] cities3 = {
                "Jeju", "Pangyo", "NewYork", "newyork"
        };
        System.out.println(solution(cache3, cities3));
    }


    public static int solution(int cacheSize, String[] cities) {
        for (int i = 0; i < cities.length; i++) {
            cities[i] = cities[i].toLowerCase(Locale.ROOT);
        }
        int answer = LRU(cacheSize, cities);
        return answer;
    }

    public static int LRU(int s, String[] cities){
        List<String> temp = new ArrayList<>();
        int excuteTime = 0;
        int cnt = 0;
        boolean check = false;

        while (cnt < cities.length) {
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i).equals(cities[cnt])) {
                    excuteTime += 1;
                    temp.remove(temp.get(i));
                    temp.add(0, cities[cnt]);
                    check = true;
                    break;
                }
            }

            if (!check){
                temp.add(0, cities[cnt]);
                excuteTime += 5;
            }

            if (temp.size() > s) {
                temp.remove(temp.size() - 1);
            }

            cnt++;
            check = false;
        }

        excuteTime += (s - temp.size());

        return excuteTime;
    }
}

LRU 알고리즘

가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

페이지 교체 알고리즘

페이징 기법으로 메모리를 관리하는 운영체제에서

새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할 지를 결정하는 방법

종류 : FIFO, LFU, LRU

1) FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 때 페이지를 선정하는 기법

2) LFU : 가장 최근에 사용한 프로그램 중 적은 횟수로 참조하는 페이지 교체

3) LRU : 가장 오랫동안 참조되지 않은 페이지 교체

LRU 알고리즘

[ 예시 ]

Input : 12345

Output : 5413

위의 그림에서 참조 스트링이 입력되고, 이에 따른 주기억 장치의 상태를 보면 됩니다.

- 4초 : 1 이 재참조되어 순서가 변경됩니다.

- 6초 : 캐시사이즈가 가득차서 가장 오랫동안 참조되지 않은 2를 제거 후 저장합니다.

[ 문제 ]

캐시 크기가 주어지고, 캐시가 비어 있는 상태에서 N개의 작업을 CPU가 차례대로 처리한다면 N개의 작업을 처리한 후

캐시 메모리 상태를 가장 최근 사용된 작업부터  차례대로 출력하는 프로그램을 작성하시오.

- 입력

1) 첫 번째 줄에 캐시 크기 (S) 와 작업 개수 (N) 이 입력됨

2) 두 번째 줄에 N 개의 작업 번호가 처리순으로 주어짐 ( 1 ~ 100 )

- 출력

마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로  출력

[ 예시 입력 ]

5 9

1 2 3 2 6 2 3 5 7

[ 과정 ]

1) 1

2) 2 1

3) 3 2 1

4) 2 3 1

5) 6 2 3 1

6) 2 6 3 1

7) 3 2 6 1

8) 5 3 2 6 1

9) 7 5 3 2 6

[ 예시 출력 ]

7 5 3 2 6

[ 소스코드 ]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LRU {
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        int s = kb.nextInt();
        int n = kb.nextInt();
        List<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(kb.nextInt());
        }
        myLRU(s, arr);
    }

    public static void myLRU(int s, List<Integer> arr) {
        List<Integer> temp = new ArrayList<>();
        int cnt = 0;
        boolean check = false;

        while (cnt < arr.size()) {
            // 이미 숫자가 있는지 확인
            for (int i = 0; i < temp.size(); i++) {
                if (temp.get(i) == arr.get(cnt)) {
                    temp.remove(i);
                    temp.add(0,arr.get(cnt));
                    check = true;
                    break;
                }
            }
            if(!check){
                temp.add(0,arr.get(cnt));
            }
            // 최대 크기를 넘은 경우
            if(temp.size() > s){
                temp.remove(temp.size() - 1);
            }
            cnt++;
            check = false;
        }
        
        for (Integer i : temp) {
            System.out.print(i + " ");
        }
    }
}

문제 설명

두 배열 각각에서 하나의 숫자를 뽑아 두 수를 곱합니다.
이러한 과정에서 배열의 길이만큼 반복하여 두 수를 곱한 값을 누적하여 더합니다.
이때 최종적으로 누적된 값이 최소가 되는게 목표입니다.

조건

각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자를 다시 뽑을 수 없음

해결 과정

1) 예를 들어, [ 1*2+3*3= 11 ], [ 1*3+3*2 = 9 ] 이와 같이 가장 큰 수에 가장 작은 수를 곱해줘야 합니다.
2) 그래서 두 배열 각각을 오름차순, 내림차순으로 정렬한다.
3) 곱을 누적시킨다.

소스코드

import java.util.*;

public class 최솟값만들기 {

    /**
     - 문제 설명:
     두 배열 각각에서 하나의 숫자를 뽑아 두 수를 곱합니다.
     이러한 과정에서 배열의 길이만큼 반복하여 두 수를 곱한 값을 누적하여 더합니다.
     이때 최종적으로 누적된 값이 최소가 되는게 목표입니다.

     - 조건 :
     각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자를 다시 뽑을 수 없음

     - 해결 과정 :
     1) 예를 들어, [ 1*2+3*3= 11 ], [ 1*3+3*2 = 9 ] 이와 같이 가장 큰 수에 가장 작은 수를 곱해줘야 합니다.
     2) 그래서 두 배열 각각을 오름차순, 내림차순으로 정렬한다.
     3) 곱을 누적시킨다.
     **/

    public static void main(String[] args) {
        int[] A = {1,2};
        int[] B = {3,4};
        System.out.println(solution(A,B));
    }

    public static int solution(int []A, int []B)
    {
        int answer = 0;
        Integer[] Bin = new Integer[B.length];
        Arrays.sort(A);

        for (int i = 0; i < B.length; i++) {
            Bin[i] =Integer.valueOf(B[i]);
        }

        Arrays.sort(Bin,Collections.reverseOrder());

        for (int i = 0; i < B.length; i++) {
            answer += A[i] * Bin[i];
        }

        return answer;
    }
}

문제 설명

: 1 ~ n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기 진행
 1) 1번부터 번호순으로 차례대로 단어 말함
 2) 마지막 사람이 단어를 말한 다음 다시 1번부터 시작
 3) 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어 말함
 4) 이전에 등장했던 단어는 사용 못함
 5) 한 글자 단어는 사용 금지

출력

가장 먼저 탈락하는 사람의 번호, 그 사람이 몇 번째에 탈락하는지를 구함

조건

1) 단어길이 - 2~50
2) 배열길이 - n ~ 100이하
3) 소문자
4) 탈락자가 생기지 않는다면 0,0 반환

해결 방법

1) 경우에 대한 조건문 작성
2) 번호 : i+1 % n
3) 몇 번째 차례 : i / n 보다 큰 첫번째 정수

소스코드

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

public class 영어끝말잇기 {
    /**
    - 문제 설명: 1 ~ n까지 번호가 붙어 있는 n명의 사람이 영어 끝말잇기 진행
     1) 1번부터 번호순으로 차례대로 단어 말함
     2) 마지막 사람이 단어를 말한 다음 다시 1번부터 시작
     3) 앞 사람이 말한 단어의 마지막 문자로 시작하는 단어 말함
     4) 이전에 등장했던 단어는 사용 못함
     5) 한 글자 단어는 사용 금지

     - 출력 :
     가장 먼저 탈락하는 사람의 번호, 그 사람이 몇 번째에 탈락하는지를 구함

     - 조건 :
     1) 단어길이 - 2~50
     2) 배열길이 - n ~ 100이하
     3) 소문자
     4) 탈락자가 생기지 않는다면 0,0 반환

     - 해결 방법 :
     1) 경우에 대한 조건문 작성
     2) 번호 : i+1 % n
     3) 몇 번째 차례 : i / n 보다 큰 첫번째 정수

     **/
    public static void main(String[] args) {
        String[] input = {"hello", "one", "even", "never", "now", "world", "draw"};
        String result = Arrays.toString(solution(2, input));
        System.out.println(result);

    }

    public static int[] solution(int n, String[] words) {
        ArrayList<String> arr = new ArrayList<>();
        int[] answer = new int[2];
        String prev = words[0];
        arr.add(words[0]);

        for(int i=1; i<words.length; i++){
            char CanFirstLetter = prev.charAt(prev.length()-1);
            if(words[i].length() == 1){
                System.out.println("issue oneLetter: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }
            if(CanFirstLetter != words[i].charAt(0)){
                System.out.println("issue not: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }
            if (arr.contains(words[i])) {
                System.out.println("issue contain: "+i);
                answer[0] = (i % n) + 1;
                answer[1] = (i/n)+1;
                return answer;
            }

            prev = words[i];
            arr.add(words[i]);
        }

        answer[0] = 0;
        answer[1] = 0;
        return answer;
    }
}

문제

짝지어 제거하기

문제 설명

> 입력 : 알파벳 소문자로 이뤄진 문자열
> 과정 :
 1) 문자열에서 같은 알파벳 두 개가 붙어있는 짝을 찾음
 2) 과정을 반복해서 문자열 모두 제거하면 짝지어 제거하기가 종료
 3) 성공적인 수행은 1, 아니면 0 을 리턴

해결 방식

1) Stack 활용

[ 반복문 ]
2) 문자열을 순회하며 스택에서 peek()한 요소와 현재 순회중인 문자가 같으면 pop
3) 아니면 push()
4) 만약 스택이 비어있으면 push

[ 출력 ]
5) 만약 스택이 비어 있으면 1 출력
6) 아니면 0 출력

소스코드

import java.util.Stack;

public class 짝지어제거하기 {
    /**
     - 문제 설명:
     > 입력 : 알파벳 소문자로 이뤄진 문자열
     > 과정 :
      1) 문자열에서 같은 알파벳 두 개가 붙어있는 짝을 찾음
      2) 과정을 반복해서 문자열 모두 제거하면 짝지어 제거하기가 종료
      3) 성공적인 수행은 1, 아니면 0 을 리턴

     - 해결 방식:
     1) Stack 활용
     [ 반복문 ]
     2) 문자열을 순회하며 스택에서 peek()한 요소와 현재 순회중인 문자가 같으면 pop
     3) 아니면 push()
     4) 만약 스택이 비어있으면 push
     [ 출력 ]
     5) 만약 스택이 비어 있으면 1 출력
     6) 아니면 0 출력

     **/
    public static void main(String[] args) {
        System.out.println(solution("baabaa"));
    }

    public static int solution(String s)
    {
        int answer = -1;

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if(stack.isEmpty()){
                stack.push(s.charAt(i));
            }
            else if (stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        if(stack.isEmpty()) answer = 1;
        else answer = 0;

        return answer;
    }
}

문제 주제

숫자 n이 주어지고, 1234567 로 나눈 나머지를 리턴하는 피보나치 함수를 작성해라

문제 해결 방법

1. 재귀는 시간 초과

2. 반복문을 사용하되 각 요소 값마다 123456 나머지를 구해서 배열에 넣어줌

3. 입력받은 n의 인덱스에 위치하는 배열 요소 값을 반환

public class 피보나치수열 {

    /*
    - 문제 : 숫자 n이 주어지고, 그 수를 1234567 로 나눈 나머지를 리턴하는 함수를 작성해라

    * */
    public static void main(String[] args) {
        System.out.println(solution(3));
    }

    public static int solution(int n) {
        int[] answer = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if(i==0) answer[i] = 0;
            else if(i==1) answer[i] = 1;
            else{
                int sum = answer[i-2] + answer[i-1];
                answer[i] = sum % 1234567;
            }
        }

        return answer[n];
    }

}

N개의 최소 공배수

문제 요구사항 :

- 배열의 공배수가 되는 가장 작은 숫자를 구해라

문제 해결 과정 :

- 유클리드 호제법 알고리즘으로 최대 공약수를 구한다.
- 첫 번째 원소 * 두 번째 원소 / gcd 의 계산을 해서 배열들의 최소 공배수를 구함

[ 소스 코드 ]

public class n개의최소공배수 {
    /*
    - 배열의 공배수가 되는 가장 작은 숫자를 구해라

    [ 해결과정 ]
    - 유클리드 호제법 알고리즘으로 최소 공배수/최대 공약수를 구한다.
    - 여기서 구한 최소 공배수를 다음 배열에 반복
     */
    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};
        System.out.println(solution(arr));
    }

    public static int solution(int[] arr) {
        int answer = arr[0];

        for (int i = 1; i < arr.length; i++) {
            int gcd = gcd(answer, arr[i]); // 최대 공약수
            answer = answer * arr[i] / gcd; // 최소 공배수
        }
        return answer;
    }

    public static int gcd(int a,int b){
        int max = Math.max(a, b);
        int min = Math.min(a, b);

        while(max % min != 0){
            int r = max % min;
            max = min;
            min = r;
        }
        return min;
    }
}

에러명

error: Pulling is not possible because you have unmerged files.

fatal: Exiting because of an unresolved conflict.

발생 과정

: 깃헙 충돌 과정 테스트 실습 중에 에러가 발생했습니다.

1. 로컬1, 로컬2 에 원격저장소를 클론

2. 로컬1에서 파일 수정 후 푸쉬

3. 로컬2에서 파일 수정 후 푸쉬   -->   에러 발생

해결 과정

- 발생이유

: 해당 에러가 발생한 이유는 로컬2 에 원격저장소와 같은 파일이 있는데, 로컬2 에서 아직 머지가 잘 되지 않았다는 것

- git commit -am "message" 후 다시 pull 을 하면

이렇게 자동으로 머지가 되며

이렇게 텍스트 파일 내부에 수정된 텍스트가 적용됨을 알 수있습니다.

원격 저장소에도 똑같이 푸쉬됨을 알 수 있습니다.

[ 문제 ]

다항식 프로그램 작성

[ Input ]

입력에는 두 개의 식이 순서대로 입력된다. 첫 번째 식은 첫 줄에는 항의 개수 n (1<=n<=20)이 들어온다.  
다음 줄 부터는 최고차항 순서로 (계수, 차수)가 들어오며 공백으로 구분된다. 두 번째 식도 같은 방법으로 입력된다.

[ Output ]

먼저, 두 개의 식을 “(항의 개수) = 다항식”의 형식으로 각 줄에 출력한다. 이때 Sample Output에 맞추어 공백을 구분하는데 유의한다. 각 계수는 소수점 첫째자리 까지 출력하고 계수가 0인 항은 출력하지 않는다 (Sample Output 참고).
그리고 마지막줄에는 두 개의 다항식을 더하여 하나의 다항식으로 출력한다.

Sample Input

3
3 12
2 8
1 0
4
15 11
14 3
2 2
1 1

Sample Output

(3) = 3.0 x^12 + 2.0 x^8 + 1.0 x^0
(4) = 15.0 x^11 + 14.0 x^3 + 2.0 x^2 + 1.0 x^1
(7) = 3.0 x^12 + 15.0 x^11 + 2.0 x^8 + 14.0 x^3 + 2.0 x^2 + 1.0 x^1 + 1.0 x^0

Sample Input

4
3 12
2 8
10 3
1 0
3
15 12
-14 8
2 3

Sample Output

(4) = 3.0 x^12 + 2.0 x^8 + 10.0 x^3 + 1.0 x^0
(3) = 15.0 x^12 + -14.0 x^8 + 2.0 x^3
(4) = 18.0 x^12 + -12.0 x^8 + 12.0 x^3 + 1.0 x^0

Sample Input

4
10 5
32 4
2 3
5 2
5
1 12
2 10
3 5
4 3
5 2

Sample Output

(4) = 10.0 x^5 + 32.0 x^4 + 2.0 x^3 + 5.0 x^2
(5) = 1.0 x^12 + 2.0 x^10 + 3.0 x^5 + 4.0 x^3 + 5.0 x^2
(6) = 1.0 x^12 + 2.0 x^10 + 13.0 x^5 + 32.0 x^4 + 6.0 x^3 + 10.0 x^2

[ 소스코드 ]

#include <cstdio>
#include <iostream>

using namespace std;

#define MAX_DEGREE 80

int degreeArr[MAX_DEGREE]; // degree 입력 배열

class polynomial{
    float coef[MAX_DEGREE]; // 계수 입력 배열 
    int polyNum[MAX_DEGREE]; // 차수 입력 배열

    public:
    int degree;
    polynomial(){
        degree = 0;
    }

    void read(int num){
        scanf("%d",&degree);
        degreeArr[num] = degree;
        for(int i=0; i<degree; i++){
            scanf("%f %d",coef+i, polyNum+i);
        }
    }

    void display(int num){
        printf("(%d) = ",num);
        for(int i=0; i<degree; i++){
            if(i == degree-1){
                printf("%.1f x^%d", coef[i], polyNum[i]);
            }
            else printf("%.1f x^%d + ", coef[i], polyNum[i]);
        }
        printf("\n");
    }

    void add( polynomial a, polynomial b){

        /* 
        차수가 큰 다항식을 자신으로 복사 후 나머지 계수를 자기 계수 배열에
        차수를 맞춰 더한다.

        - 해결할 문제
        1) degree 순이 아닌 높은 차수 순으로 정렬

        - 해결 과정
        1) c에 a를 복사한다.
        2) b의 차수 배열과 c의 차수 배열을 비교해서 c에 넣어준다.
        3) 넣어주는 조건
            > c 차수가 b의 차수보다 큰 경우 b의 해당 원소 앞에 넣어준다.
            > c 차수 배열의 마지막 원소보다 b의 차수가 작다면 뒤로 배열을 다 넣어준다.
            > c 차수와 b차수가 같은 경우 b의 해당 계수을 더해준다.
        */
        *this = a; // c = a의 degree 와 polyNum 이 복사됨
        int degreeCnt = 0;

        for(int i=0; i<b.degree; i++){ // b를 순환

            for(int j=0; j<degree; j++){ // c에서 제 자리를 찾기 위해 c를 순환
                if(polyNum[j] < b.polyNum[i]){ //b의 차수가 c의 차수보다 큰 경우
                    int insertPoef = b.polyNum[i];
                    int insertCoef = b.coef[i];
                    for(int k=degree; k >= j; k--){
                        coef[k+1] = coef[k];
                        polyNum[k+1] = polyNum[k];
                    }
                    polyNum[j] = insertPoef;
                    coef[j] = insertCoef;
                    degreeCnt++; // degree 증가 카운트를 해놓고 반복문이 끝나면 degree에 더해준다.
                    j = j+1; // 자릿수가 늘어남에 따라 j도 증가
                    break;
                }
                else if(polyNum[j] == b.polyNum[i]){ //b와 c의 차수가 같은 경우
                    coef[j] += b.coef[i];
                    break; // 더 해주는게 반복되지 않게 종료시켜줌
                }
            }
            degree += degreeCnt;
            degreeCnt = 0;
        }
    }

    bool isZero(){
        return degree == 0;
    }

    void negate(){
        for(int i=0; i<degree ;i++) coef[i] = -coef[i];
    }
};

int main(){
        polynomial a,b,c;
        a.read(0);
        b.read(1);
        c.add(a,b);

        int num = c.degree;

        a.display(degreeArr[0]);
        b.display(degreeArr[1]);
        c.display(num);
        return 0;
}

위의 문제를 이해하는데에 시간이 조금 걸렸습니다.

[ 문제 해석 ]

1. 문제의 목표

한 행 또는 한 열 전부에서 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 갯수를 구해라

N*N 배열에 각 숫자들이 들어가 있습니다.

그 숫자들은 각각의 높이를 가리킵니다.

아래 배열 표에서 1행은 각각 3 3 3 3 3 3 의 높이를 가집니다.

2. 지나갈 수 있는 조건

 1) 길에 속한 모든 칸의 높이가 같은 경우

 2) 또는 지나갈 수 있는 경사로를 만들어서 지나가는 방법

3. 경사로의 특징

 1) 높이 차이가 항상 1이다.

 2) 경사로는 낮은 칸에 놓는다.

 3) L개의 연속된 칸에 경사로 바닥이 모두 접해야 한다.

 4) 경사로를 놓을 낮은 칸의 높이는 모두 같아야 한다.

4. 경사로를 놓지 못하는 경우

 1) 경사로를 놓은 곳에 또 경사로를 놓는 경우

 2) 낮은 칸과 높은 칸의 차이가 1이 아닌 경우

 3) 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않는 경우

 4) 경사로 때문에 배열의 범위를 벗어난 경우

[ 경사로 놓을 수 있는 예시 ]

[ 경사로를 놓지 못하는 경우 ]

왼쪽부터 1,2,3,4 번으로 부르겠습니다.

- 1번 : 높이 1을 높여도 3까지 닿지 못함

- 2번 : 경사로 바닥이 닿지 않음

- 3번 : 경사로가 겹침

- 4번 : 경사로 바닥이 닿지 않음

[ 문제 풀이 과정 ]

1. 행과 열에서 지나갈 수 있는 길을 구하는 함수를 각각 만들어 준다.

2. 만약 있는 경우 1을 return 하고, 없는 경우 0을 return 하여 각 행렬을 모두 순회한다.

3. 함수 내부에서 N만큼의 크기를 갖는 Buffer 라는 임시 배열을 만든다.

4. 만약 road 배열에서 해당 인덱스 다음 인덱스가 숫자가 더 크면 오르막길이고, 낮으면 내리막길이다.

5. 내리막길인 경우, i인덱스에 올라올 수 있는 길을 만들어야 하므로 i의 다음 인덱스부터 L까지에 해당하는 경사로를 놓아준다.

6. 만약 위의 경사로를 놓을 수 없는 경우가 없다면 Buffer에 해당 자리의 카운트를 증가시킨다.

7. 행을 탐색한 경우 모든 행을 탐색하고 마지막으로 Buffer 내부 원소 값을 비교해 1보다 큰 경우 중첩되는 경우 이므로,

   갈 수 없는 길로 0을 리턴해준다.

8. 모든 조건이 맞는다면 1을 리턴해준다.

이와 같은 방식을 행열에 모두 적용해주면 됩니다.

[ 소스코드 ]

import java.util.Scanner;

public class 경사로 {

    // 백준 코드로 제출시 Main 으로 제출

    // 입력
    static int N, L;
    static int answer = 0;
    static int[][] road;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();

        road = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                road[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < N; i++) {
            answer += roadCol(i) + roadRow(i);
        }

        System.out.println(answer);
    }

    public static int roadCol(int idx) {

        int[] Buffer = new int[N]; // 초기값 : 0

        // 만약 배열이 차이가 없는 경우에는 초기 값이 그대로 유지됨

        for (int i = 0; i < N; i++) {

            //높이 차이가 2이상 나는 경우
            try {
                if (road[idx][i] >= road[idx][i + 1] + 2) {
                    return 0;
                }
                if (road[idx][i] <= road[idx][i + 1] - 2) {
                    return 0;
                }

                if (road[idx][i] > road[idx][i + 1]) { // 내리막
                    int start = i + 1;
                    int j;
                    for (j = start; j < start + L; j++) {
                        if (j >= N) return 0; // 범위를 벗어난 경우
                        if (road[idx][i + 1] == road[idx][j]) { // 다음 블럭의 높이가 같은 경우 버퍼에 넣어줌
                            Buffer[j]++;
                        } else return 0;
                    }
                }
                else if (road[idx][i] < road[idx][i + 1]) { // 오르막
                    int start = i;
                    int j;
                    for (j = start; j > start - L; j--) {
                        if (j < 0) return 0; // 범위가 넘으면 종료
                        if (road[idx][i] == road[idx][j]) {
                            Buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(Buffer[i] > 1) return 0;
        }

        return 1;
    }

    public static int roadRow(int idx) {
        int[] buffer = new int[N];

        for (int i = 0; i < N; i++) {
            try {
                if (road[i][idx] >= road[i + 1][idx] + 2) {
                    return 0;
                }
                if (road[i][idx] <= road[i + 1][idx] - 2) {
                    return 0;
                }

                if (road[i][idx] > road[i + 1][idx]) { // 오르막
                    int start = i + 1;
                    for (int j = start; j < start + L; j++) {
                        if (j >= N) return 0;
                        if (road[i + 1][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }

                if (road[i][idx] < road[i + 1][idx]) { // 내리막
                    int start = i;
                    for (int j = start; j > start - L; j--) {
                        if (j < 0) return 0;
                        if (road[i][idx] == road[j][idx]) {
                            buffer[j]++;
                        } else return 0;
                    }
                }
            } catch (Exception e) {

            }
        }

        for (int i = 0; i < N; i++) {
            if(buffer[i] > 1) return 0;
        }

        return 1;
    }
}

[ 참고 ]

백준에서 코드 제출할 때는 클래스 명을 Main 으로 작성해서 제출해야 합니다.

위의 코드를 그대로 제출할 시 컴파일 에러가 발생합니다.

* 참조 : https://www.youtube.com/watch?v=PCURy3Wv8uU

시뮬레이션

문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 것

종류

• 알고리즘은 간단한데 코드가 지나치게 긴 문제
• 실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제
• 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
• 적정한 라이브러리를 찾아서 사용해야 하는 문제

특징

일반적으로 2차원 공간을 다루는 문제가 많이 나온다.

2차원 공간을 다루기 위해 행렬 개념을 사용하며, 이차원 공간에서의 방향 벡터가 자주 나옴

완전탐색

모든 경우의 수를 다 계산하는 방법

완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지므로 데이터 개수가 100만개 이하일 때 적절합니다.

구현 : [ 완전 탐색, 시뮬레이션 ]

구현으로 묶이는 알고리즘 유형은 모든 경우를 하나씩 직접 수행해서 결과를 도출하는 것이 답이 잘 나옵니다.

그래서 머리속으로 생각하는 것을 코드로 잘 표현할 수 있는가가 풀이의 핵심 입니다.

[ 해결 완료 ]

application.yml 파일의 들여쓰기 문제입니다.

spring:
	datasource:
    	url:~~
        
    jpa:
    	hibernate:
        	ddl-auto:
    
 logging.level:
 	org.hibernate.SQL:~~

이와 같이 띄어쓰기가 잘 되어있는지 확인해보시고 돌려보시길 바랍니다.

* 용어 설명

1) Contributor

프로젝트 핵심 개발 팀이 아닌 외부에서 온 사람으로서 일부 변경을 통해 프로젝트에 기여하고자 하는 사람입니다.

즉, 프로젝트 관리자는 아니지만 프로젝트의 커밋에 관여하는 모든 사람을 의미

 - 특징

   > Push 권한이 없어 Fork하여 프로젝트를 통째로 복사한 후 자신의 복사된 프로젝트에 Push 를 합니다. 

      그 후 원래의 저장소로 Push 내용을 보내는 Pull Request 를 생성합니다.

   > 프로젝트 관리자는 Pull Request 를 검토하고 Merge 또는 Reject 를 한다.

   > 이때, Pull Request 가 받아들여 지면, 이 사람을 Contributor 라고 부른다.

2) Collaborator

프로젝트의 공동 책임자를 의미합니다.

즉, Push/Pull 권한 모두를 가지고 있는 사람입니다.

만약 하나의 프로젝트를 중점적으로 개발하는 개발자들은 Collaborator로 등록해 작업하는 것이 효율적입니다.

Pull Request 를 왜 하는가?

모든 사용자를 Contributor 로 등록할 수 없기 때문입니다.

 - 사용되는 경우

1) 오픈 소스 프로젝트를 고친 경우

2) Collaborate Project 에서 Mege 권한 관리를 하고 싶을 때

 ex) master/release 브랜치로 merge는 무조건 pull request 하고, 팀장이 merge 를 수행

어떻게 사용하는가?

1) 최종 기여할 Repository 를 Fork

2) 내 Repository 로 Fork 된 프로젝트를 내 로컬로 Clone 후 수정

3) 커밋 후 푸쉬하면 기여할 Repository 에서 Merge / Reject 를 결정

[ 문제 설명 ]

문제를 정리하면 다음과 같습니다.

- 문제 설명:
길이가 같은 두 개의 큐가 주어짐
> 하나의 큐를 골라 원소를 추출
> 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
> 그 작업을 통해 각 큐의 원소 합을 같게 만듬
> 이때, 필요한 작업의 최소 횟수를 구해라
> 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주

- 주의
> long type 권장
> 큐 길이 : 30만
> 원소 크기 : 10에 9승

[ 해결 방법 ]

* s1 = 배열1의 합 | s2 = 배열2의 합 | sum = 배열1,2의 합/2

* problem1,2 = pop(), insert() 한 횟수

1) 입력 받은 배열을 Queue 에 넣어준다.

2) 두 배열의 합이 만약 홀수이면 -1을 리턴해준다.

3) 합을 나누기 2를 해준다.

4) 반복문을 통해 아래의 내용을 비교해준다. ( 반복문은 problem1,2 가 큐의 길이가 두배가 되면 종료 )

 - s1 이 sum 과 같으면 problem1 + problem2 를 리턴해준다.

 - s1 이 sum 보다 크면,

s1 에 queue1 에서 peek() 한 값을 빼줌
s2 에는 더해줌
queue2 에 queue1 을 pop() 한 값을 poll() 해줌
problem1 을 하나 증가시킴

- 둘 다 아니면,

s2 에 queue2 에서 peek() 한 값을 빼줌
s1 에 더해줌
queue1 에 queue2를 pop()한 값을 poll() 해줌
problem2 를 하나 증가시팀

[ 소스 코드 ]

import java.util.ArrayDeque;
import java.util.Queue;

public class 큐문제 {

    /**

     - 문제 설명:
     길이가 같은 두 개의 큐가 주어짐
     > 하나의 큐를 골라 원소를 추출
     > 추출된 원소를 다른 큐에 집어 넣는 작업을 수행
     > 그 작업을 통해 각 큐의 원소 합을 같게 만듬
     > 이때, 필요한 작업의 최소 횟수를 구해라
     > 한 번씩 pop,insert 를 하면 작업 수행 1회로 간주

     - 주의
     > long type 권장
     > 큐 길이 : 30만
     > 원소 크기 : 10에 9승

     **/

    public static void main(String[] args) {
        int[] queue1 = {3, 2, 7, 2};
        int[] queue2 = {4, 6, 5, 1};
        int solution = solution(queue1, queue2);
        System.out.println(solution);

    }

    public static int solution(int[] queue1, int[] queue2) {
        Queue<Integer> que1 = new ArrayDeque<>();
        Queue<Integer> que2 = new ArrayDeque<>();

        long s1 = 0, s2 = 0, sum = 0;

        for (int i = 0; i < queue1.length; i++) {
            que1.add(queue1[i]);
            s1 += queue1[i];

            que2.add(queue2[i]);
            s2 += queue2[i];
        }

        sum = s1 + s2;

        // 홀수가 될 경우 풀 수 없음
        if (sum % 2 == 1) return -1;

        sum = sum/2;

        int problem1 = 0;
        int problem2 = 0;
        int limit = queue1.length * 2;

        while (problem1 <= limit && problem2 <= limit) {
            if(s1 == sum) return problem1 + problem2;
            else if(s1 > sum){
                s1 -= que1.peek();
                s2 += que1.peek();
                que2.add(que1.poll());
                problem1++;
            }
            else {
                s1 += que2.peek();
                s2 -= que2.peek();
                que1.add(que2.poll());
                problem2++;
            }
        }
        return -1;
    }
}

[ 문제 해석 ]

갈색 격자수, 노란색 격자 수 yellow 가 매개변수로 주어질 때,
카펫의 가로/세로 크기를 수너대로 담은 배열을 나타내라

- 단, 중앙에는 노란색, 테두리 1줄은 갈색으로 칠해져 있음

[ 풀이 방법 ]

1) 갈색,노란색 격자 수를 더한 값의 약수를 구한다.
2) 그 약수 중에 정답이 있다.
3) (가로-2) * (세로-2) = 노란색의 개수이다.

* 조건 : 가로 길이 >= 세로 길이

[ 처음 시도 한 소스 코드 ]

import java.util.ArrayList;

public class 카펫 {

    /**
    - 문제 해석:
     갈색 격자수, 노란색 격자 수 yellow 가 매개변수로 주어질 때,
     카펫의 가로/세로 크기를 수너대로 담은 배열을 나타내라

     - 단, 중앙에는 노란색, 테두리 1줄은 갈색으로 칠해져 있음

     - 풀이 방법:
     1) 갈색,노란색 격자 수를 더한 값의 약수를 구한다.
     2) 그 약수 중에 정답이 있다.
     3) (가로-2) * (세로-2) = 노란색의 개수이다.

     * 조건 : 가로 길이 >= 세로 길이
    **/

    static int brown;
    static int yellow;

    public static void main(String[] args) {
        brown = 10;
        yellow = 2;
        int[] solution = solution();
        System.out.println(solution[0] + " " + solution[1]);
    }

    public static int[] solution() {
        int[] answer = new int[2];
        int sum = brown + yellow;
        ArrayList<String> calNumber = cal(sum);
        for (String i : calNumber) {
            String[] strArr = i.split(" ");
            int x = Integer.parseInt(strArr[0]);
            int y = Integer.parseInt(strArr[1]);

            if ((x - 2) * (y - 2) == yellow) {
                answer[0] = x;
                answer[1] = y;
            }
        }
        return answer;
    }

    public static ArrayList<String> cal(int n) {
        ArrayList<String> cal = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (i * j == n) {
                    if (i >= j) {
                        cal.add(i + " " + j);
                    }
                }
            }
        }

        return cal;
    }


}

[ 테스트 결과 ]

몇몇 테스트 코드에서 시간 초과가 발생함을 알 수 있습니다.

다른 사람의 코드를 가져와 비교해 보겠습니다.

class Solution {
    public int[] solution(int brown, int yellow) {
        int[] answer = new int[2];
        int sum = brown + yellow;
        
        for (int i = 3; i < sum; i++) {
            // 노란 격자가 가운데에 위치하기 위해 세로,가로가 모두 3이상이여야 하므로 3부터 시작
            int j = sum / i;
            // 가로길이를 바로 합에 나눠줘버려 세로를 구해줌
            
            if (sum % i == 0 && j >= 3) { 
            // 약수가 되고, j 길이도 3이상인 것을 선택
                int col = Math.max(i, j);
                int row = Math.min(i, j);
                // i,j 중 더 큰 값이 가로 길이가 됨
                
                int center = (col - 2) * (row - 2);
				// 가로-2 * 세로-2 = 노란색 격자 수 공식을 사용
                
                if (center == yellow) {
                    answer[0] = col;
                    answer[1] = row;
                    return answer;
                }
            }
        }
        return answer;
    }
}

* 출처 : https://easybrother0103.tistory.com/110

[ 풀이 방법 ]

스택을 이용하면 풀기 쉽습니다.

1) 문자열을 char 배열로 만들어줌

2) '(' 를 만나면 푸쉬

3) ')' 를 만나면 pop

* return false 가 되는 두 가지 경우

1) pop 하는데 스택이 비어 있을 때

2) pop 을 다 했는데 스택에 요소가 남아 있는 경우

import java.util.Stack;

public class 괄호문제 {

    static Stack<Character> stack = new Stack<>();

    public static void main(String[] args) {
        String s = ")()(";
        System.out.println(solution(s));
    }

    static boolean solution(String s) {
        boolean answer = true;

        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '(') {
                stack.push(ch[i]);
            } else if (ch[i] == ')') {
                if(stack.empty()){
                    return false;
                }
                Character pop = stack.pop();
            }
        }

        if(!stack.isEmpty()){
            return false;
        }

        return answer;
    }

}

위 문제는 DFS의 개념을 이해하고 있으면 한결 풀기 편합니다.

https://tjdwns4537.tistory.com/137?category=955960 

1. 재귀로 풀 수 있는가?

경우의 수를 생각해보면 배열의 첫 번째부터 끝까지 더 할 수도 있고, 뺄 수도 있습니다. 그래서 각 원소당 2개의 경우의 수가 발생합니다.

재귀 함수를 사용할 수 있는가에 대해 판단하는 기준은 시간복잡도로 계산하시면 됩니다.

일반적으로 500만 번 이하의 탐색을 하게 되면 재귀함수를 사용할 수 있다고 보고 있습니다.

그러면 최대 20개의 원소를 가진다고 했으므로, 100만 번 정도의 탐색을 하므로 충분히 사용 가능합니다.

2. 재귀로 풀 때 고려사항

재귀로 풀 때 고려해야하는 사항은 크게 두가지가 존재합니다.

- 수행 동작

: 한 번의 동작 안에 어떤 동작을 수행할 것인지를 정의 해야 합니다.

- 언제 탈출 시킬 것인가

: 탈출을 시켜야 재귀 함수가 종료가 되므로 위에 대한 부분도 생각해야합니다.

문제에 대해서는 재귀 함수가 콜 된 인덱스가 배열 길이만큼 되면 탈출 시키면 됩니다.

* 프로그래머스 문제 풀이 팁

: 바뀌지 않을 값들은 멤버 변수로 정의해 사용하는게 편리하다.

[ 소스 코드 ]

public class TargetNumber {

    /**
     1. 문제
     - n개의 음이 아닌 정수들 존재
     - 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟넘버 만들기
     - [ 1,1,1,1 ] 로 숫자3 을 만드는 방법을
        ( -1+1+1+1+1 = 3 )
        ( +1-1+1+1+1 = 3 ) ...
     **/

    static int answer = 0;
    static int[] numbers;
    static int target;

    public static void main(String[] args) {
        int[] numbers1 = {1, 1, 1, 1, 1};
        int[] numbers2 = {4,1,2,1};

        solution(numbers1, 3);
        System.out.println(answer);
    }

    public static int solution(int[] _numbers, int _target) {
        answer = 0;
        numbers = _numbers;
        target = _target;

        dfs(0,0);

        return answer;
    }

    public static void dfs(int index, int sum) {
        
        // 1. 탈출 방법
        if (index == numbers.length) { // 인덱스가 배열 길이가 될 때
            if(sum == target){ // 합이 타겟이 될 때
                answer++;
                return;
            }
        }

        // 2. 구현 동작
        try{
            // 덧셈을 수행
            dfs(index + 1, sum + numbers[index]);
            // 뺄셈을 수행
            dfs(index + 1, sum - numbers[index]);
        } catch (Exception e){

        }

    }
}

이번 블로깅은 DFS 코드에 대해 분석하는 내용이라 DFS에 대한 개념을 어느 정도 아는 상태여야 이해가 됩니다.

1. 그래프의 탐색

그래프의 탐색은 하나의 정점에서 모든 정점을 차례로 한 번씩 방문하는 것을 의미합니다.

그 알고리즘은 DFS 와 BFS가 있습니다.

2. DFS ( Depth First Search ) - 깊이 우선 탐색

루트 노드나 임의의 노드에서 시작해 깊숙히 탐색한 다음 다시 원점으로 돌아가 다른 루트를 탐색하는 방법입니다.

즉, 다음 노드로 넘어가기 전에 완전 탐색을 하는 방법입니다.

일반적으로 재귀, 스택, 인접 행렬, 인접 리스트를 이용해 구현합니다.

주로, 미로 탐색과 같이 한 방향으로 계속 탐색해야 하는 경우에 사용되며, 만약 막 다른 곳에 도달하면 그 길에 표식을 남기고

가장 가까운 갈림길로 돌아와 다시 탐색을 진행합니다.

이러한 방법으로 갈림길을 순차적으로 탐색해 목적지까지의 경로를 구합니다.

 * 특징

1) 깊게 탐색

2) 모든 노드를 방문하고자 하는 경우에 사용

3) 노드의 방문 여부를 반드시 검사해야함 ( 그렇지 않으면 무한 루프에 빠질 수 있음 )

4) BFS 에 비해 구현이 쉬움

5) BFS 에 비해 느림

6) 해가 없는 경우에 대한 예외 발생 코드가 필요

7) 해를 구한다고 해도 최단 경로라는 보장은 못함

위의 그래프를 직접 만들고, DFS를 진행해본다고 가정하고 코드를 작성해 보겠습니다.

[ 소스코드 ]

public class graphDFS {
    private int nV; //정점
    private int[][] dfsGraph; //간선
    private boolean[] visitArr; //방문한 배열

    public graphDFS(int nV) {
        this.nV = nV;

        this.dfsGraph = new int[this.nV + 1][this.nV + 1];
        this.visitArr = new boolean[this.nV + 1];
    }

    // 그래프 리턴
    public int[][] getGraph() {
        return this.dfsGraph;
    }

    // 양방향 그래프 추가
    public void put(int x,int y) {
        this.dfsGraph[x][y] = 1;
        this.dfsGraph[y][x] = 1;
    }

    // 단방향 그래프 추가
    public void putSingle(int x, int y) {
        this.dfsGraph[x][y] = 1;
    }
    //그래프 출력
    public void printGraphToAdjArr() {
        System.out.println("\n"+"[그래프 출력]");
        for (int i = 1; i < dfsGraph.length; i++) {
            for (int j = 1; j < dfsGraph[i].length; j++) {
                System.out.print(this.dfsGraph[i][j]+" ");
            }
            System.out.println();
        }
    }

    // 그래프 탐색
    public void dfs(int vIdx) {
        visitArr[vIdx] = true;
        System.out.print(vIdx + " ");
        for (int i = 1; i <= nV; i++) {
            if(dfsGraph[vIdx][i] == 1 && visitArr[i] == false){
                dfs(i);
            }
        }
    }

    public static void main(String[] args) {
        int nV = 8;

        graphDFS graph = new graphDFS(nV);

        graph.put(1, 2);
        graph.put(1, 3);
        graph.put(2, 4);
        graph.put(2, 5);
        graph.put(3, 6);
        graph.put(3, 7);
        graph.put(4, 8);
        graph.put(5, 8);
        graph.put(6, 8);
        graph.put(7, 8);

        graph.dfs(1);
        graph.printGraphToAdjArr();

    }
}

[ dfs 함수 설명 ]

- visitArr : 탐색을 했다는 걸 알 수 있는 배열

- visitArr[vIdx] = true  : true가 되면 탐색 한 것

- if ( dfsGraph [ vIdx ] [ i ] == 1 : 방문한 인덱스에 다음 정점까지의 경로가 있는 경우

- visitArr[i] : 방문할 정점의 경로가 방문한 적이 없는 경우

- dfs (i) 재귀를 통해 방문한다.

현재까지 풀었던 문제 중 가장 이해가 어려웠던 문제인것 같습니다.

확률과 통계에 대한 개념이 있으신 분들은 쉽다곤 하네요..

[ 풀이 ]

순열을 이용하는 문제입니다.

n이 3이면 3!의 경우의 수만 구하면되지만, 최대값인 20!의 값을 구해야 한다면 모든 경우의 수를 살펴볼 수 없습ㄴ디ㅏ.

따라서 k번째의 순열만 빠르게 구할 수 있는 방법을 찾아봐야합니다.

문제 예시를 먼저 보겠습니다.

1. [1, 2, 3]
2. [1, 3, 2]
3. [2, 1, 3]
4. [2, 3, 1]
5. [3, 1, 2]
6. [3, 2, 1]

n은 3인데 앞자리의 숫자는 2개를 기준으로 변경된다는 것을 알 수 있습니다.

만약 앞자리가 고정되어 있다면 나머지 2개의 숫자들만 사용해서 순열을 구하면 됩니다.

그래서 앞자리 교체주기를 생각해봅시다.

[ 1 ~~ ]

[ 2~~ ]

이렇게 앞자리가 바뀌는 교체주기는 (n-1)! 가 되는것을 알 수 있습니다.

그리고 k는 모든 순열에서 k번째 위치한 순열을 의미합니다.

그래서 만약 k가 5라면

arr [ index / (n-1)! ] 을 하게 되면 현재 주기에서 맨 앞에 위치한 숫자입니다.

여기서 k는 순번을 의미하므로 저희가 필요한 인덱스를 찾으려면 인덱스는 0부터 시작하므로 1을 빼줘야합니다.

따라서 초기 인덱스 값은 k-1로 잡아주면 됩니다.

즉, arr [ k-1 / (n-1)! ] 를 해주면 현재 주기에서의 맨 앞에 위치한 숫자의 인덱스가 됩니다.

예를 들어,

n = 5, k = 110 일 때를 예를 들어 보겠습니다.

- 모든 경우의 수 : 5!

- 맨 앞자리 교체주기 : 4!

- 맨 앞자리 숫자의 인덱스 : 109 / 4!

이제 맨 앞자리를 구했으니 다음 숫자를 구해봅시다.

그러면 맨 앞자리 하나의 숫자를 고정 해줬으므로 다음과 같이 그 다음 숫자를 구할 수 있습니다.

이를 위해선 두가지 작업이 추가적으로 더 구현됩니다.

 1) 인덱스 값을 다음 순열을 위해 재조정

 2) 사용한 배열 원소를 제거

인덱스 값은 현재 주기에서 가장 앞자리의 숫자를 찾아주는 역할을 합니다.

그래서 앞자리 숫자의 인덱스를 찾고 난 후 다음 순열에서도 맨 앞자리를 찾을 수 있도록 k 값을 재조정해줘야 합니다.

(k-1) % (n-1)! 해주면 됩니다.

이렇게하면 자연스레 (n-1)! 를 넘을 수 없고, 다음 경우의 수에서 맨 앞자리 숫자를 가리키는 인덱스를 동일한 로직으로 찾을 수 있습니다.

이때, 만약 k의 값이 0이 되면 정확하게 나눠떨어졌다는 소리이므로 반복문이 종료됩니다.

n = 4, k = 5 라고 예를 들어봅니다.

[ 1,2,3,4 ]
[ 1,2,4,3 ]
[ 1,3,2,4 ]
[ 1,3,4,2 ]
[ 1,4,2,3 ]
[ 1,4,3,2 ]
[ 2,1,3,4 ]

첫 번째 자리 수가 특정 수가 되는 경우 : (n-1)! 단위로 끊어짐

( 단, 앞이 1인 배열은 0번의 위치에 해당됩니다.
ex. [ 1,2,3,4 ] , [1,~~~] : 0
      [ 2,3,4,1 ] , [2,~~~] : 1... )

그래서 해당하는 위치를 구하려면
k / (n-1)! : 배열의 순서의 번호
k % (n-1)! : 배열 순서 내부 번호

import java.util.ArrayList;

public class skillCheck2 {
    /**
     - 문제 해석
     > 일렬로 줄 서 있음
     > 1~n 까지 번호가 매겨져 있음
     > n명의 사람이 줄 서는 방법은 여러가지 있음
     > 사람의 수 n, 자연수 k가 주어질 때, 사람을 나열하는 방법을 사전순으로 정렬
     > k번째 정렬된 수의 배열을 리턴
     **/
    public static void main(String[] args) {

    }
    public int[] solution(int n, long k) {
        int[] answer = new int[n];
        ArrayList<Integer> list = new ArrayList<>();

        int fn = 1;
        for (int i = 1; i <= n; i++) {
            fn *= i; // fac 구하기
            list.add(i);
        }
        k--;
        int idx = 0;
        while (idx < n) {
            fn /= n - idx;
            answer[idx++] = list.remove((int) (k / fn));
            k %= fn;
        }

        return answer;
    }
}

* 참조했던 블로그입니다.

https://gogoma.tistory.com/150