728x90

Controller의 핸들러 메서드는 다양한 유형의 Argument(인수)를 지원한다.

그 중에서 REST API 애플리케이션에서 자주 사용되는 유형의 Argument를 간단히 살펴보자! 

만약, 김영한님의 스프링 강의를 들었다면 더더욱 익숙할 것이다.

Method Argument 설명
@RequestParam 쿼리 파라미터, form-data 등의 Servlet request Parameter를 바인딩 해야 할 경우 사용
@RequestHeader request header를 바인딩해서 header의 key/value에 접근 가능
@RequestBody request body를 읽어서 지정한 Java 객체로 deserialization(역직렬화) 해준다
@RequestPart 'multipart/form-data' 형식의 request 데이터를 part 별로 바인딩 가능
@PathVariable @RequestMapping 에 패턴 형식으로 정의된 URL의 변수에 바인딩 가능
@MatrixVariable URL 경로 세그먼트 부분에 key/value 쌍으로 된 데이터에 바인딩 가능
HttpEntity request header와 body에 접근할 수 있는 컨테이너 객체 사용
javax.servlet.ServletRequest, 
javax.servlet.ServletResponse
로우 레벨의 ServeletRequest와 ServletResponse의 정보가 필요할 때 사용

※ 역직렬화란? byte로 변환된 Data를 원래대로 Object나 Data로 변환하는 기술


- @RequestParam

@RequestParam은 클라이언트 쪽에서 쿼리 파라미터, form data, x-www-form-urlencoded 등의 형식으로 전달되는 요청 데이터를 바인딩해서 사용할 수 있도록 해준다.

@Controller
@RequestMapping("/coffees")
public class CoffeeController {
    // ...
    @GetMapping
    public Coffee getCoffee(@RequestParam("coffeeId") int coffeeId) {
       Coffee coffee = coffeeService.getCoffee(coffeeId);
        return coffee;
    }
    // ...
}

 

- @RequestHeader

@RequestHeader는 HTTP request header의 key/value 쌍의 데이터에 접근할 수 있도록 해준다.

@GetMapping("/coffee")
public void getCoffee(
        @RequestHeader("Content-Type") String contentType, 
        @RequestHeader("Content-Length") long contentLength) { 
    //...
}​

 

- @RequestBody

@RequestBody는 HTTP request body를 읽어서 지정한 Java 객체로 변환(deserialization) 해준다.

@PostMapping("/coffees")
public void handle(@RequestBody Coffee coffee) {
    // ...
    coffeeService.save(coffee)
}​

※ @RequestBody는 특히 리소스를 등록하는 @PostMapping에서 주로 사용된다.

 

- @RequestPart

'multipart/form-data' 형식의 request 데이터를 part 별로 바인딩할 수 있도록 해준다.

@Controller
public class CoffeeController {
    @PostMapping("/coffees")
    public String postCoffee(@RequestPart("coffee") Coffee coffee,
           @RequestPart("file") MultipartFile photoFile) {

        if (!photoFile.isEmpty()) {
            byte[] bytes = file.getBytes();
            // TODO 파일 저장
            return "success";
        }
        return "failed";
    }
}​

위 코드에 대해 설명하자면, 예를 들어 클라이언트 쪽에서 커피 사진이 포함된 multpart/form-data 타입의 커피 정보를 전송한다면,   form data를 part별로 나누어서 전달 받을 수 있다.

 

- @PathVariable

@PathVariable은 @RequestMapping 에 패턴 형식으로 정의된 URL의 변수에 바인딩할 수 있도록 해준다.

@GetMapping("/members/{member-id}/coffees/{coffee-id}")
public Pet getCoffee(@PathVariable("member-id") Long memberId,
@PathVariable("coffee-id") Long coffeeId) {
    // ...
}​

위 코드와 같이 '{variable name}'과 같은 형태의 URL 변수가 여러개 있을 경우, @PathVariable을 핸들러 메서드에 순차적으로 추가해서 URL 변수의 값을 받을 수 있다.

 

- @MatrixVariable

@MatrixVariable은 URL 경로 세그먼트 부분에 key/value 쌍으로 된 데이터에 바인딩할 수 있도록 해준다.

@MatrixVariable의 사용은 예제 코드를 보자.

// 클라이언트 요청 URL
// GET /coffees/42;q=11;r=22

@GetMapping("/coffees/{coffeeId}")
public void getCoffee(@PathVariable("coffee-id") coffeeId, 
                      @MatrixVariable int q,
                      @MatrixVariable int r) {

    // coffeeId == 42
    // q == 11
    // r == 22
}​

만약에 클라이언트 쪽 요청 URL이 '/coffees/42;q=11;r=22'와 같다면 세미콜론(;) 뒤에 오는 q, r을 변수로 보고 각 변수의 값을 위와 같이 핸들러 메서드에서 전달 받을 수 있다.

 

- HttpEntity

클라이언트 요청 body와 header 정보를 HttpEntity 객체를 통해 한번에 전달 받을 수 있다.

물론 HttpServletRequest 객체를 통해서도 요청 body와 header에 접근할 수 있지만 HttpEntity 객체를 통해 조금 더 간단하게 두 정보에 접근할 수 있다.

@RestController
@RequestMapping("/v1/coffees")
public class HttpEntityExample {
    @PostMapping
    public Coffee postCoffee(HttpEntity<Coffee> entity) {
        Coffee coffee = entity.getBody();
        HttpHeaders headers = entity.getHeaders();
        
        // coffee 정보 저장
        return coffee;
    }
}​
728x90
728x90

Handler 용어의 의미

우리가 핸들(Handle) 이라고 하면 일반적으로 자동차의 핸들을 제일 먼저 떠올릴 수 있는데, 자동차의 핸들은 운전자가 직접 핸들을 움직이면서 직접적으로 자동차의 주행을 처리하는 역할을 한다.

 

Spring MVC에서는 자동차의 핸들과 마찬가지로 클라이언트의 요청을 처리하는 처리자 Handler라고 한다.

 

그렇다면 Spring MVC에서 Handler는 누구일까?


Spring MVC에서의 요청 Handler는 바로 우리가 작성하는 Controller 클래스를 의미한다. 그리고 Controller 클래스에 있는 @GetMapping@PostMapping 같은 애너테이션이 붙어 있는 메서드들을 핸들러 메서드라고 한다.

 

HandlerMapping이란 의미는 결국 사용자의 요청이 요청을 처리하는 Handler매핑해주는 역할을 하는 것이다.

 

그렇다면, 사용자의 요청과 Handler 메서드의 매핑은 어떤 기준으로 이루어질까?

 

@GetMapping(”/coffee”) 처럼 HTTP Request Method(GET, POST 등)와 Mapping URL을 기준으로 해당 Handler와 매핑이 되는데, Spring 에서는 여러가지 유형의 HandlerMapping 클래스를 제공하고 있다.

 

실무에서는 Spring에서 디폴트로 지정한 ‘RequestMappingHandlerMapping’을 대부분 사용한다고 했고 원한다면 얼마든지 HandlerMapping 전략을 바꿀 수 있다. 


Adapter의 의미

Java에서 사용하는 클래스나 인터페이스의 이름을 살펴보다 보면 흥미로운 용어들이 많이 나온다.
Adapter라는 용어도 그 중에 하나라고 볼 수 있다.

우리말로 아답터, 어댑터(Adapter, Adaptor)하면 220V 전압을 110V 전압으로 또는 그 반대로 바꿔주는 어댑터(일명, 돼지코)나 USB 충전기를 떠올릴 수 있다.

220V를 5V 전압으로 바꿔주는 USB 충전기 예

 

이처럼 Adapter는 무언가를 다른 형식이나 형태로 바꿔주는 역할을 한다.

 

그렇다면 HandlerAdater는 무엇을 바꿔줄까?

 

Spring은 객체지향의 설계 원칙을 잘 따르는 아주 유연한 구조를 가지는 프레임워크이다.

 

따라서 Spring이 제공하는 Spring MVC에서 지원하는 Handler를 사용해도 되지만 다른 프레임워크의 Handler를 Spring MVC에 통합할 수 있다.

 

이처럼 다른 프레임워크의 핸들러를 Spring MVC에 통합하기 위해서 HandlerAdapter를 사용할 수 있다.


ViewResolver의 의미

’Resolve’는 무언가를 해석하고, 해결해주다라는 뜻이 있다.

 

ViewResolver는 DispatcherServlet에서 ‘이런 이름을 가진 View를 줘’ 라고 요청하면 DispatcherServlet에서 전달한 View 이름을 해석한 뒤, 적절한 View 객체를 리턴해주는 역할을 한다.

728x90
728x90

HttpMessageConverter란?

웹 브라우저 같은 클라이언트에서 보여지는 HTML 컨텐츠가 렌더링(Rendering)되는 방식은 크게 두 가지로 나눈다.

 

1. 웹 애플리케이션 서버에서 동적으로 변하는 데이터를 포함하는 HTML을 만들어서 HTML 자체를 한번에 클라이언트 쪽으로 내려주는 방식이다.


이 방식은 JSP나 타임리프(Thymeleaf) 같은 기술을 사용해서 HTML을 템플릿화 한 다음에 Controller의 핸들러 메서드에서 리턴하는 모델 데이터를 템플릿에 동적으로 채워 넣은 후, 최종적으로 완성된 HTML을 클라이언트 쪽으로 내려주는 방식이다. 이 방식을 바로 서버 사이드 렌더링(Server Side Rendering)이라고 한다.

 

2. 클라이언트 쪽을 담당하는 Apache나 NginX 같은 웹 서버에 HTML을 올려 놓은 후, 자바스크립트의 Ajax 기술을 이용해서 웹 애플리케이션 서버에 데이터를 요청한다. 그리고 응답으로 전달받은 데이터를 웹 서버에 올려둔 HTML에 동적으로 채워 넣은 후, 최종적으로 완성된 HTML을 클라이언트 쪽으로 내려주는 방식이다.

 

이 방식을 바로 클라이언트 사이드 렌더링(Client Side Rendering)이라고 한다.

 

위 두가지 방식 중에서 HttpMessageConverter는 두 번째 방식인 클라이언트 사이드 렌더링과 관련이 있다.

 

즉, 클라이언트 사이드 렌더링을 위해 필요한 데이터를 특정 형식으로 변환해 주는 것이 바로 HttpMessageConverter다.


HttpMessageConverter의 사용 목적

HttpMessageConverter는 크게 두 가지 목적으로 사용된다.

 

1. 웹 서버에서 전송된 Reqeust Body를 DTO 같은 클래스의 객체로 변환해서 웹 애플리케이션 서버 쪽에서 사용할 수 있도록 해주는 것이고, 

 

2. 웹 서버 쪽으로 전달할 응답 데이터를 Response Body로 변환해주는 것이다.


HttpMessageConverter의 동작 과정

Spring MVC 요청/응답 동작 과정

 

위 그림은 클라이언트의 요청을 처리하는 Spring MVC의 기본 동작 과정이다.


이 Spring MVC의 동작 과정에서 HandlerAdapter의 동작 과정을 조금 더 구체적으로 설명하겠다.

 

* 요청 처리 시 HandlerAdapter의 동작 과정

  • HandlerMapping을 통해 적절한 HandlerAdapter를 찾으면 HandlerAdapter Controller로 넘겨줄 파라미터를 결정하기 위해 이 작업을 HandlerMethodArgumentResolver에게 위임한다.
  • HandlerMethodArgumentResolver HttpMessageConverter에게 HTTP Request Body를 특정 타입의 객체로 변환해주기를 요청한다.
  • HttpMessageConverter는 HTTP Request Body를 특정 타입의 객체로 변환한다.
  • HandlerMethodArgumentResolver는 변환된 데이터를 전달 받아서 이 데이터를 다시 HandlerAdapter에게 전달한다.
  • HandlerAdapter HandlerMethodArgumentResolver로부터 전달 받은 데이터를 핸들러 메서드의 파라미터로 포함 시킨 후, 핸들러 메서드를 호출한다.

 

* 응답 처리 시 HandlerAdapter의 동작 과정

  • 핸들러 메서드가 응답으로 전달할 데이터를 리턴한다.
  • HandlerMethodReturnValueHandler는 핸들러 메서드로부터 전달 받은 응답 데이터를 HttpMessageConverter에게 전달한다.
  • HttpMessageConverter HandlerMethodReturnValueHandler로부터 전달 받은 데이터를 HTTP Response Body에 포함되는 형식의 데이터로 변환한다.
  • HandlerMethodReturnValueHandler HttpMessageConverter로부터 전달 받은 데이터를 HandlerAdapter에게 전달한다.

REST API에서의 HttpMessageConverter

Spring MVC에서는 기본적으로 아래의 HttpMessageConverter 구현체가 활성화 되어 있다.

  • ByteArrayHttpMessageConverter
  • StringHttpMessageConverter
  • ResourceHttpMessageConverter
  • SourceHttpMessageConverter
  • FormHttpMessageConverter
  • Jaxb2RootElementHttpMessageConverter
  • MappingJackson2HttpMessageConverter
  • MappingJacksonHttpMessageConverter
  • AtomFeedHttpMessageConverter
  • RssChannelHttpMessageConverter

 

만약 우리가 HTTP Request 또는 Response를 위한 통신 프로토콜로 JSON을 사용하는 REST API Controller를 구현했다고 가정해 보자.

 

특정 Controller의 핸들러 메서드 파라미터에 @RequestBody 애너테이션이 추가되거나 파라미터의 타입이 HttpEntity라면 위에서 나열한 HttpMessageConverter가 순서대로 HTTP Request Body를 체크해서 핸들러 파라미터에 지정한 클래스로 변환이 되는지, HTTP Message의 Content Type을 지원하는지 여부를 확인하게 된다.

 

이 두가지 조건을 모두 만족한다면 아마도 MappingJackson2HttpMessageConverter가 Request Body를 해당 클래스의 객체로 변환할 것이고, 조건에 부합하는 HttpMessageConverter가 존재하지 않는다면 예외가 발생할 것이다.

 

이제 응답 데이터를 JSON 형식으로 전달하는 상황을 생각해 보자.

 

핸들러 메서드에 @ResponseBody 애너테이션을 추가하거나 핸들러 메서드의 리턴 타입이 HttpEntity라면 역시 위에서 나열한 HttpMessageConverter가 순서대로 핸들러 메서드의 리턴 값을 체크해서 해당 클래스 타입을 지원하는지, Accept Header에 명시된 MediaType으로 변환이 되는지 여부를 확인하게 된다.


HttpMessageConverter가 동작하는 시점

HttpMessageConverter가 동작하는 시점은 JSON을 DTO로 deserialization 할 때와 DTO를 JSON으로 serialization 할 때가 다르다. 아래는 HttpMessageConverter의 대략적인 동작 흐름이다.

 

* JSON -> DTO로 deserialization

HandlerMethodArgumentResolverComposite.resolveArgument() 

 RequestResponseBodyMethodProcessor.resolveArgument()

 RequestResponseBodyMethodProcessor.readWithMessageConverters() > converter.read()

 objectReader.readValue()

 

* DTO -> JSON serialization

HandlerMethodReturnValueHandlerComposite.handleReturnValue() 
→ HttpEntityMethodProcessor.handleReturnValue() 
→ AbstractMessageConverterMethodProcessor.writeWithMessageConverters() > genericConverter.write() 
→ AbstractGenericHttpMessageConverter.write() 
→ AbstractJackson2HttpMessageConverter.writeInternal() > objectWriter.writeValue(generator, value)
→ write() and flush() 과정을 거친다.
→ ...
→ ...
 CoyoteAdapter.service() > response.finishResponse() // response가 close되면서 클라이언트 쪽에 출력

728x90
728x90

문제 설명

오픈채팅방

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

"[닉네임]님이 들어왔습니다."

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

"[닉네임]님이 나갔습니다."

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

  • 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
  • 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 "Muzi"와 "Prodo"라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

"Muzi님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Muzi님이 나갔습니다."

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Prodo님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

"Prodo님이 들어왔습니다."
"Ryan님이 들어왔습니다."
"Prodo님이 나갔습니다."
"Prodo님이 들어왔습니다."

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항
  • record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
  • 다음은 record에 담긴 문자열에 대한 설명이다.
    • 모든 유저는 [유저 아이디]로 구분한다.
    • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - "Enter [유저 아이디] [닉네임]" (ex. "Enter uid1234 Muzi")
    • [유저 아이디] 사용자가 채팅방에서 퇴장 - "Leave [유저 아이디]" (ex. "Leave uid1234")
    • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - "Change [유저 아이디] [닉네임]" (ex. "Change uid1234 Muzi")
    • 첫 단어는 Enter, Leave, Change 중 하나이다.
    • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
    • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
    • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
    • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.
입출력 예
       record                                                                                                                                       result
["Enter uid1234 Muzi", "Enter uid4567 Prodo","Leave uid1234",
"Enter uid1234 Prodo","Change uid4567 Ryan"]
["Prodo님이 들어왔습니다.",
"Ryan님이 들어왔습니다.",
"Prodo님이 나갔습니다.",
"Prodo님이 들어왔습니다."]
입출력 예 설명

입출력 예 #1
문제의 설명과 같다.


나의 풀이

def solution(record):
    answer = []
    dic = {}
    
    for sentence in record:
        sentence_split = sentence.split()
        if len(sentence_split) == 3:
            dic[sentence_split[1]] = sentence_split[2]
            
    for sentence in record:
        sentence_split = sentence.split()
        if sentence_split[0] == 'Enter':
            answer.append('%s님이 들어왔습니다.' %dic[sentence_split[1]])
        elif sentence_split[0] == 'Leave':
            answer.append('%s님이 나갔습니다.' %dic[sentence_split[1]])
            
    return(answer)

문제를 풀기 전 살펴봐야 하는 것이 있다.

▶ 모든 유저는 [유저 아이디]로 구분한다. 즉, 유저의 "uid"는 변경할 수 없는 고유값이어야 한다.
▶ "닉네임"은 변경이 가능한 값이다.
▶ 닉네임 변경과 관련한 안내문은 나타나지 않는다.
▶ 닉네임을 변경하면 기존에 채팅방에 있던 메시지의 닉네임도 모두 변한다.
▶ 닉네임은 중복이 가능하지만 uid는 고유값이기 때문에 중복될 수 없다.
  1. 따라서 알고리즘을 구현하기 전에 Dictionary 형태로 uid와 닉네임을 묶어두면 다루기 편하겠다고 생각했다.
  2. uid가 고유값이기 때문에 record 리스트 내의 모든 uid를 닉네임과 묶는다면, 중복되는 닉네임도 구분이 가능했다.
  3. 또한 닉네임 변경 안내문을 출력할 필요가 없으므로 Dictionary 값에 각각의 값을 저장하고 출력하기만 하면 됐다.
  4. 그리고 record 리스트가 시계열 순으로 등록되어 있기 때문에, for문을 사용해서 Dictionary 값에 계속해서 저장해 나가면 이전의 닉네임을 삭제하고 변경한 닉네임을 key값에 저장하는 것이 가능했다.

 

  • 5번째 코드를 보면 Dictionary에 데이터를 저장하는 코드를 먼저 구현했다.
  • 'Leave'의 경우 닉네임 변경과 관련된 내용이 없기 때문에 'Enter'와 'Change'에 해당하는 값만 조정했다. (len(sentence_split == 3)

 

Dictionary에 저장된 값을 확인하면 다음과 같다.

{'uid1234': 'Prodo', 'uid4567': 'Ryan'}

 

출력 값에서 알 수 있듯이 각각의 고유 uid에 해당하는 닉네임이 딕셔너리 형태로 저장되었다.
주어진 배열 record가 시계열로 저장된 것이기 때문에 위와 같은 코드로 구현할 수 있었다.
위와 같이 구현한다면 각각의 uid가 가진 최종 닉네임 값이 Dictionary에 저장된다.

 

!! 최종적으로 변경된 아이디가 화면에 출력되면 되기 때문에 닉네임이 'Change'되는 과정은 고려하지 않아도 된다.

 


다른 사람 코드 

def solution(record):
    answer = []
    namespace = {}
    printer = {'Enter':'님이 들어왔습니다.', 'Leave':'님이 나갔습니다.'}
    for r in record:
        rr = r.split(' ')
        if rr[0] in ['Enter', 'Change']:
            namespace[rr[1]] = rr[2]

    for r in record:
        if r.split(' ')[0] != 'Change':
            answer.append(namespace[r.split(' ')[1]] + printer[r.split(' ')[0]])

    return answer

간결해서 가독성이 높았다.

728x90
728x90

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항
  • scoville의 길이는 2 이상 1,000,000 이하입니다.
  • K는 0 이상 1,000,000,000 이하입니다.
  • scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  • 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
입출력 예scovilleKreturn
[1, 2, 3, 9, 10, 12] 7 2
입출력 예 설명
  1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
    가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
  2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
    새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
    가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.


나의 풀이

import heapq

def solution(scoville, k):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    mix_cnt = 0
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1
    return mix_cnt

힙 문제라고 명시되어 있어서 힙을 사용했다. 파이썬에서 힙은 heapq 라이브러리를 사용한다.

 

heapq는 일반적인 리스트와 다르게, 가지고 있는 요소를 push, pop 할때마다 자동으로 정렬해주는 녀석이다.

따라서, 앞서 문제가 되었던 정렬 비용을 감소시킴으로써 효율성 이슈를 해결했다.

 

  • (4) heapq로 사용할 리스트를 초기화한다.
  • (5~6) 기존 리스트에 있던 요소들을 heapq에 넣어준다. heappush 라는 메소드를 이용한다.
  • 맨 앞의 요소를 가져올때 heappop 메소드를 이용한다는 사실을 제외하고 나머지는 똑같다.

 

간단히 heappop() 으로 힙에 데이터를 뺄 수 있고, heappush() 으로 데이터를 넣을 수 있다.

그리고 heapify()로 리스트를 힙으로 만들 수 있다. (오름차순 정렬과 비슷)


힙(Heap)이란?

 

  • 힙은 최소 힙과 최대 힙이 있는데 최소 힙은 루트 노드에 최솟값이 있는 것이고, 최대 힙은 루트 노드에 최대값이 있는 것이다.
  • 파이썬의 heapq에서는 최소힙만 지원된다. (다행히 이 문제는 최소힙을 이용하는 문제이다.)
  • 힙의 루트 노드는 0번 인덱스이다. 즉, 최소값이 0번 인덱스에 존재하는 것이다.
  • 그렇기 때문에 위 문제를 보면 최소 K 이상이 되는지 확인하려면 최소값인 루트노드. 0번 인덱스만 확인하면 된다.
  • 문제의 조건에서 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1을 return 한다고 했기 때문에 scoville에 음식이 단 하나 남았는데도 scoville 지수가 K보다 작다면 -1을 리턴한다.
  • 가장 작은 두 값을 찾기 위해 heappop()을 두 번 수행한다.
  • 그리고 num1 + num2 * 2 를 계산해서 heappush로 다시 넣어준다.
  • 이 과정이 수행되면 count를 1씩 증가시킨다
728x90
728x90

※ DFS/BFS를 알기 전에 밑에 글부터 읽고오자!

 

https://veggie-garden.tistory.com/28


** DFS & BFS


* DFS(Depth First Search)란? == 깊이 우선 탐색

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 

  • dfs는 그래프의 노드를 갈 수 있는 데 까지 끝까지 방문하는 것이다. ==> 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 노드를 순서대로 목적지에 도달할 때 까지 방문하면서, 각 노드에서 또 방문할 수 있는 위치를 저장해 둔다.
  • 노드가 끝까지 갔다가 다시 한칸 뒤로 돌아와, 갈 수 있는 방향을 탐색한다.
  • 정리하면 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
  • 따라서 재귀적이고 / 스택을 이용할 수 있다. ==> 스택 자료구조 이용

 

* BFS(Breadth First Search)란? == 너비우선탐색

자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. 

  • bfs는  노드에서 인접한 노드를 먼저 방문한다. ==> 가까운 노드부터 탐색하는 알고리즘 
  • 한 노드에서 갈수있는 모든 경우의 수를 저장한 후, 순서대로 방문한다.
  • 이를 반복하기 위해서 큐를 사용한다. ==> 선입선출 방식인 큐 자료구조를 이용
  • 큐에 방문할 위치를 저장함으로써 순서대로 방문이 가능하다.

* DFS vs BFS

출처: https://iq.opengenus.org/dfs-vs-bfs/

DFS와 BFS의 차이점은 바로 노드 방문 순서이다. 

 

- BFS : 너비우선탐색

: 동작 방식 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

: 탐색 소요 시간 : O(N) 

 

 

- DFS : 깊이 우선 탐색

: 동작 방식

1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

>> 방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.


- 그래프를 표현하는 2가지 방법

 

1. 인접행렬 ( Adjacency Matrix )

: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

: 메모리가 불필요하게 낭비됨

: 정보를 얻는 속도가 빠르다

 

2. 인접리스트 ( Adjacency List )

: 리스트로 그래프의 연결 관계를 표현하는 방식

: 메모리를 효율적으로 사용 ( 연결된 정보만을 저장 )

: 정보를 얻는 속도 느림 ( 연결된 데이터를 하나씩 확인해야하기 때문 )

 

 

==> 파이썬에서는 단순히 2차원 리스트를 이용하면 된다!

파이썬은 기본 자료형인 리스트 자료형이 append()와 메소드를 제공하기 때문!


** 실습


DFS와 BFS에 대해 더 이해하기 위해서는 직접 관련 코드를 보면서 연습해봐야한다.

나는 밑에 글을 참고하면서 코드 연습을 했기에 따로 작성은 하지 않을거고 밑에 글을 참고하면서 연습하면 될 듯하다.

https://gorokke.tistory.com/131

728x90
728x90

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

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

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

제한사항
  • 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
  • 각 숫자는 1 이상 50 이하인 자연수입니다.
  • 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예numberstargetreturn
[1, 1, 1, 1, 1] 3 5
[4, 1, 2, 1] 4 2
입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4
  • 총 2가지 방법이 있으므로, 2를 return 합니다.

  • deque를 이용한 BFS 풀이
from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

1. 이진 트리의 형태로 구성될 수 있고, 모든 노드를 말단까지 탐색 한 후 target에 만족하는 값이 되는지를 검사해야한다.

따라서 BFS를 사용했다. (DFS도 사용 가능)

2. 다음에 계산할 값을 각각 +, -하고 2개의 노드를 생성해 queue에 담아준다.

# stack을 이용한 dfs여도 마찬가지! 
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

 

이 문제는 아래 링크에서 참고하였다!!

 

 

출처 https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

 

[Python] 프로그래머스 level2 타겟넘버 (BFS/DFS)

타겟넘버 문제를 bfs와 dfs를 이용해서 풀어봤다. 아래 나오는 코드들은 다 모든 테스트케이스를 통과한 코드이다!

velog.io

 

 

 


다른 사람 풀이

def solution(numbers, target):
    sup = [0]
    for i in numbers:
        sub=[]
        for j in sup:
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)
def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
728x90
728x90

1. Queue란?

 

  •  가장 먼저 입력 된 데이터가 가장 먼저 출력되는 구조이다.
  • FIFO(First In, First Out)라고 부르기도 하며 반대로 LILO(Last In, Last Out)이라고 설명하기도 한다.
  • 큐에서 알아두어야 할 용어가 있는데 Enqueue(인큐), Dequeue(디큐)이다.

-. Enqueue : 큐에서 데이터를 입력하는 기능

-. Dequeue : 큐에서 데이터를 꺼내는 기능

  • 추가로 파이썬에서는 queue, deque라는 두가지 내장 모듈을 통해 큐를 구현할 수 있다. 

 

2. queue 내장 모듈을 통한 큐 구현 - 1 

 

  •  파이썬에서는 queue라는 내장 모듈을 제공한다. 아래 예시로 든 그림을 통해 코드를 작성해보았다.
  • put( )은 큐에 데이터를 넣을 때 사용하는 메서드, get( )은 큐에서 데이터를 꺼내는 메서드이다

 

 

<코드>

import queue

#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))

#선언 된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)

#큐 객체에서 입력된 객체 하나씩 꺼내기 :FIFO
print(data.get())
print(data.get())
print(data.get())

 

<결과>

<class 'queue.Queue'>
2
5
8

 

숫자 2,5,8을 순서대로 넣고 get( )을 3번 하면 먼저 입력 된 순서대로 출력된다.

 

 queue 내장 모듈 내에는 기본적인 Queue( ) 클래스 외에도 LifoQueue( ), PriorityQueue( ) 클래스가 존재한다. 여기서 자세히 다루진 않겠지만 LifoQueue( )는 스택과 같은 LIFO 구조, PriorityQueue( ) 는 사용자가 우선순위를 지정한대로 데이터를 꺼낼 수 있는 구조라고 보면 될 것 같다.

 

 

2. deque 내장 모듈을 통한 큐 구현 - 2 

  • 큐를 구현할려면 위의 예시처럼 queue 를 호출해도 되지만,
    일반적으로 deque를 사용하여 큐를 구현하는 것을 추천한다.
  • append(): 큐의 끝에 요소를 추가
  • popleft(): 큐의 맨 앞에서 요소를 제거하고 반환
from collections import deque

queue = deque()

# 큐에 요소 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

print(queue)  # deque([1, 2, 3])

# 큐에서 요소 제거 (dequeue)
front_element = queue.popleft()
print(front_element)  # 1
print(queue)  # deque([2, 3])

 

deque의 장점

  • 양방향 작업의 효율성:
    • deque는 리스트와 달리 양쪽 끝에서 요소를 추가하거나 제거할 때 O(1)의 시간 복잡도를 가진다.
    • 리스트는 한쪽 끝에서만 O(1)의 시간 복잡도를 가지며, 다른 쪽 끝에서는 O(n)의 시간 복잡도를 가진다.
  • 유연성:
    • deque는 스택과 큐의 모든 연산을 효율적으로 지원하므로, 상황에 따라 스택과 큐의 역할을 모두 수행할 수 있다.

 

deque의 주요 메서드

  • 스택 연산
    • append(x): 스택의 맨 위에 요소 x를 추가
    • pop(): 스택의 맨 위에서 요소를 제거하고 반환
  • 큐 연산
    • append(x): 큐의 끝에 요소 x를 추가
    • popleft(): 큐의 맨 앞에서 요소를 제거하고 반환
  • 기타 메서드
    • appendleft(x): 큐의 맨 앞에 요소 x를 추가
    • popright(): 큐의 맨 끝에서 요소를 제거하고 반환

이와 같이 deque는 스택과 큐의 역할을 모두 효율적으로 수행할 수 있는 강력한 자료 구조이다.

 

deque와 queue 모듈의 비교

  • 용도:
    • deque: 양방향에서 빠른 삽입 및 삭제가 필요한 경우에 사용된다. 큐와 스택의 연산을 모두 효율적으로 수행할 수 있다.
    • queue 모듈: 멀티스레딩 환경에서 안전하게 큐를 사용해야 하는 경우에 사용된다. 특히, 스레드 간의 작업을 조정할 때 유용하다.
  • 성능:
    • deque: 대부분의 큐 및 스택 연산이 O(1)로 매우 효율적이다.
    • queue 모듈: 멀티스레딩을 지원하기 위해 추가적인 동기화가 필요하므로 약간의 성능 오버헤드가 있을 수 있다.
  • 사용 편의성:
    • deque: 단순한 큐 및 스택 연산을 수행할 때 간단하고 직관적인 인터페이스를 제공한다.
    • queue 모듈: 멀티스레딩 환경에서 안전하게 사용할 수 있지만, 단일 스레드 환경에서는 다소 복잡할 수 있다.

결론

  • 일반적인 큐 또는 스택 기능이 필요하고 단일 스레드 환경에서 사용한다면 collections.deque를 사용하는 것이 좋다.
  • 멀티스레딩 환경에서 안전하게 큐를 사용해야 한다면 queue 모듈을 사용하는 것이 적합하다.
728x90

+ Recent posts