BOJ_11279 최대 힙

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제 출력 1

0
2
1
3
2
1
0
0

해결 코드

'''
1. 아이디어
-x 로 heappush 하여 최대 힙을 만들어서 출력한다
2. 복잡도
O(logn) 복잡도로 출력, O(n)회
3. 자료구조
- Heap
'''


import heapq
import sys
input = sys.stdin.readline

n = int(input())
heap = []
heap_length = 0

for _ in range(n):
x = int(input())
if x == 0:
if heap_length == 0:
print(0)
else:
print(-heapq.heappop(heap)) # -x 로 추가하여 -를 붙여 출력
heap_length = len(heap)
else:
heapq.heappush(heap, -x) # 힙에 원소를 추가할 때 -x로 추가 하여 최대값 정렬
heap_length = len(heap)

 

 

'Etc > PS' 카테고리의 다른 글

BOJ_10026 적록색약 - Python3  (1) 2022.07.14
BOJ_2178 미로 탐색 - Python3  (0) 2022.07.14
BOJ_1927 최소 힙 - Python3  (0) 2022.07.11
BOJ_1996 프린터 큐 - Python3  (0) 2022.07.08
BOJ_1018 체스판 다시 칠하기 - Python3  (0) 2022.07.01

BOJ_1927 최소 힙

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1

9
0
12345678
1
2
0
0
0
0
32

예제 출력 1

0
1
2
12345678
0

해결코드

import heapq
import sys
input = sys.stdin.readline

n = int(input())
heap = []
heap_length = 0

for _ in range(n):    # 1. 배열에 자연수 x를 넣는다.
    x = int(input())
    if x == 0:    # x가 0이라면
        if heap_length == 0:    # 배열이 비었으면 0 출력
            print(0)
        else:    # 있는 경우, 가장 작은 값 출력
            print(heapq.heappop(heap))
            heap_length = len(heap)
    else:
        heapq.heappush(heap, x)
        heap_length = len(heap)

'Etc > PS' 카테고리의 다른 글

BOJ_10026 적록색약 - Python3  (1) 2022.07.14
BOJ_2178 미로 탐색 - Python3  (0) 2022.07.14
BOJ_11279 최대 힙 - Python3  (1) 2022.07.11
BOJ_1996 프린터 큐 - Python3  (0) 2022.07.08
BOJ_1018 체스판 다시 칠하기 - Python3  (0) 2022.07.01
  1. 힙(Heap) 이란?
  • 일종의 트리
  • 수의 집합에서 가장 작은 수(키)나 가장 큰 수만을 자주 꺼내올 때 유용한 자료구조
  • 배열에서는 최소값 탐색시 O(n), 힙에서는 O(logn)으로 시간복잡도에서 유리

 

  1. 힙의 구조
  • 트리 중 완전 이진 트리
  • 항상 자식은 두개 밖에 없다.
  • leaf의 가장 왼쪽부터 채운다
  • 키값의 대소 관계는 부모/자식 간에만 성립
  • 형제노드 사이에는 대소 관계가 정해지지 않는다

 

  1. 최소힙, 최대힙
  • 최소힙: 가장 작은 값이 루트
  • 최대힙: 가장 큰 값이 루트

 

  1. 힙의 구현
  • leftChild = parent*2
  • rightChild = parent*2+1
  • parent = child/2

 

  1. 파이썬에서 heapq 모듈 사용
  • import heapq : 파이썬 heapq 모듈은 heapq (prirority queue) 알고리즘 제공

 

  1. 힙 함수 활용하기
  • heapq.heappush(heap, iteam): item을 heap에 추가
  • heapq.heappop(heap): heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
  • heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N))

 

[mysql] DB 테이블에 칼럼 추가 및 수정 명령어

1. 칼럼 추가 명령어

// 포멧
ALTER TABLE [테이블명]
ADD COLUMN [칼럼명] [데이터타입] [제약조건(기본값, 제약조건)] [코멘트];

// 예시
ALTER TABLE t_user
ADD COLUMN LOCK_YN VARCHAR(20) DEFAULT 'n' NOT NULL COMMENT '계정잠금 여부(Y/N)';

2. 특정 칼러만 수정 명령어

// 포멧
ALTER TABLE [테이블명]
MODIFY [칼럼명] [데이터타입] [제약조건(기본값, 제약조건)] COMMENT '코멘트';

// 예시
ALTER TABLE t_user
MODIFY LOCK_YN int(10) DEFAULT 0 COMMENT '계정 잠금 여부 (1/0)';

롬복이란?

  • 자바 개발자들의 필!수! 라이브러리 롬복, 롬복이란 무엇인지와 어떻게 사용하는지 알아보자.

롬복은 자바 개발할 때 자주 사용하는 코드 Getter, Setter, 기본생성자, toString 등을 어노테이션으로 자동 생성해 줍니다.

인텔리제이에서 프로젝트에 롬복 추가

  1. Build.gradle에 코드 추가
  2. compile('org.projectlombok:lombok')
  3. Gradle 새로고침하여 라이브러리(의존성) 추가
  4. Lombok 플러그인 다운로드 및 인텔리제이 재시작
  5. 롬복에 대한 설정 팝업 클릭 or [Preferences > Build,... > Compiler > Annotaion Processor]에서 Enable annotaion processing 체크

롬록으로 리팩토링하기

Hello Controller 코드 롬복으로 전환하기

  1. web 패키지에 dto 패키지 추가
  • 모든 응답 Dto를 관리
  1. Hello ResponseDto 생성
package com.choee.service.springboot.web.dto; 
import lombok.Getter; 
import lombok.RequiredArgsConstructor; 
@Getter 
@RequiredArgsConstructor 
public class HelloResponseDto { 
	private final String name; 	
    private final int amount; 
}

@Getter

  • 선언된 모든 필드의 get 메소드를 생성해 준다.

@RequiredArgsConstructor

  • 선언된 모든 final 필드가 포함된 생성자를 생성해 준다.
  • final이 없는 필드는 생성자에 포홤되지 않는다.

Dto에 적용된 롬복이 잘 작동하는지 테스트 코드 작성

package com.choee.service.springboot.web.dto;

import org.junit.Test;
import static org.assertj.core.api.Assertions.assertThat;

public class HelloResponseDtoTest {

    @Test
    public void 롬복_기능_테스트() {
        // given
        String name = "test";
        int amount = 1000;

        // when
        HelloResponseDto dto = new HelloResponseDto(name, amount);

        // then
        assertThat(dto.getName()).isEqualTo(name);
        assertThat(dto.getAmount()).isEqualTo(amount);
    }
}

assertThat

  • assertj라는 테스트 검증 라이브러리의 검증 메소드
  • 검증하고 싶은 대상을 메소드 인자로 받는다.
  • 메소드 체이닝이 지원되어 isEqualTo와 같이 메소드를 이어서 사용 가능

isEqualTo

  • assertj의 동등 비교 메소드
  • assertThat에 있는 값과 isEqualTo의 값을 비교해서 같을 때만 성공

Junnit과 비교하여 assertj의 장점

  • CoreMatchesrs와 달리 추가적으로 라이브러리가 필요하지 않다.
  • -> Junit의 asserThat을 쓰게 되면 is()와 같이 CoreMatchers 라이브러리가 필요하다.
  • 자동완성이 좀 더 확실하게 지원된다.
  • -> IDE에서 CoreMatcher와 같은 Matcher 라이브러리의 자동완성 지원이 약하다.

!트러블슈팅!

  • 문제: 그레이들 5에서 롬복을 비롯해서 Querydsl 등의 플러그인 설정 방법 변경
  • 해결: build.gradle 의존성에 annotationProcessor('org.projectlombok:lombok') 추가
  • 비고: gradle 5 이상부터 어노테이션을 구별해서 추가해야 한다.

HelloReponseDto를 사용하여 HelloController에 코드 추가

package com.choee.service.springboot.web;

import com.choee.service.springboot.web.dto.HelloResponseDto;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class HelloController {

    @GetMapping("/hello")
    public String hello() {
        return "hello";
    }

    // 추가된 부분
    @GetMapping("/hello/dto")
    public HelloResponseDto helloDto(@RequestParam("name") String name,
                                     @RequestParam("amount") int amount) {
        return new HelloResponseDto(name, amount);
    }
}
package com.choee.service.springboot.web;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.autoconfigure.web.servlet.WebMvcTest;
import org.springframework.test.context.junit4.SpringRunner;
import org.springframework.test.web.servlet.MockMvc;

import static org.hamcrest.Matchers.is;
import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.get;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.content;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.jsonPath;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.status;

@RunWith(SpringRunner.class)
@WebMvcTest(controllers = HelloController.class)
public class HelloControllerTest {

    @Autowired
    private MockMvc mvc;

    @Test
    public void hello가_리턴된다() throws Exception {
        String hello = "hello";

        mvc.perform(get("/hello"))
                .andExpect(status().isOk())
                .andExpect(content().string(hello));
    }

    // 추가된 API 테스트 코드
    @Test
    public void helloDto가_리턴된다() throws Exception {
        String name = "hello";
        int amount = 1000;

        mvc.perform(
                get("/hello/dto")
                        .param("name",name)
                        .param("amount",String.valueOf(amount)))
                .andExpect(status().isOk())
                .andExpect(jsonPath("$.name",is(name)))
                .andExpect(jsonPath("$.amount",is(amount)));
    }
}

param

  • API 테스트할 때 사용될 요청 파라미터를 설정한다.
  • 단, 값은 String만 허용된다.(숫자, 날짜 등의 데이터도 등록할 때 문자열로 변경해야한다.)

jsonPath

  • JSON 응답값을 필드별로 검증할 수 있는 메소드
  • $를 기준으로 필드명을 명시

Hello Controller 테스트 코드 작성하기

1. 패키지 생성

  • [src > main > java] 에 패키지 생성
  • 패키지명은 웹 사이트 주소의 역순으로 생성이 일반적
  • ex) com.choee.service.springboot

2. 패키지 내에 Java 클래스 생성

package com.choee.service.springboot;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication 
public class Application { // 메인 클래스
    public static void main(String[] args) {SpringApplication.run(Application.class,args);} // SpringApplication.run : 내장 WAS 실행
}

@SpringBootApplication

  • 스프링 부트의 자동 설정
  • 스프링 Bean 읽기와 생성 모두 자동 설정,
  • @SpringBootApplication이 있는 위치부터 설정을 읽어가므로 메인 클래스틑 항상 프로젝트의 최상단에 위치해야한다.

Spring Bean 이란?

  • Spring에 의하여 생성되고 관리되는 자바 객체를 Bean이라고 한다.
  • 참조: melonicedlatte.com/2021/07/11/232800.html

내장 WAS(Web Application Server)란?

  • 별도로 외부에 WAS를 두지 않고 애플리케이션을 실행할 때 내부에서 WAS를 실행하는 것

내장 WAS 이용의 장점

  • 항상 서버에 톰캣을 설치할 필요가 없게 되고, 스프링 부트로 만들어진 Jar 파일(실행 가능한 java 패키징 파일)로 실행하면 된다.
  • 언제 어디서나 같은 환경에서 스프링 부트를 배포할 수 있다.

3. 현재 패키지 하위에 web 패키지 생성

  • 컨트롤러와 관련된 클래스들을 관리하는 패키지

HelloControler 클래스 생성하여 테스트 API 작성

package com.choee.service.springboot.web;

import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class HelloController {

    @GetMapping("/hello")
    public String hello() {
        return "hello";
    }
}

@RestController

  • 컨트롤러를 JSON을 반환하는 컨트롤러로 만들어준다.
  • 이전의 @ResponseBody를 각메소드마다 선언했던 것을 한번에 사용할 수 있게해주는 어노테이션

@GetMapping

  • HTTP Method인 Get의 요청을 받을 수 있는 API를 만들어 준다.
  • 이전엔 @RequestMapping(method = RequestMethod.GET)으로 사용

4. 테스트 코드로 검증

package com.choee.service.springboot.web;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.autoconfigure.web.servlet.WebMvcTest;
import org.springframework.test.context.junit4.SpringRunner;
import org.springframework.test.web.servlet.MockMvc;
import org.springframework.test.web.servlet.ResultActions;
import static org.springframework.test.web.servlet.request.MockMvcRequestBuilders.get;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.content;
import static org.springframework.test.web.servlet.result.MockMvcResultMatchers.status;

@RunWith(SpringRunner.class)
@WebMvcTest(controllers = HelloController.class)
public class HelloControllerTest {

    @Autowired
    private MockMvc mvc;

    @Test
    public void hello가_리턴된다() throws Exception {
        String hello = "hello";

        mvc.perform(get("/hello"))
                .andExpect(status().isOk())
                .andExpect(content().string(hello));
    }
}

@RunWith(SpringRunner.class)

  • 테스트를 진행할 때 Junit에 내장된 실행자 외에 다른 실행자를 실행시킨다.
  • SpringRunner라는 스프링 실행자 사용
  • 스프링 부트와 테스트 JUnit 사이의 연결자 역할을 한다.

@WebMvcTest

  • 여러 스프링 테스트 어노테이션 중, Web(Spring MVC)에 집중할 수 잇는 어노테이션
  • 선언할 경우 @Controller, @ControllerAdvice 등 사용 가능
  • @Service, @Component, @Repository 등 사용 불가

@Autowired

  • 스프링이 관리하는 Bean을 주입 받는다.

private MockMvc mvc

  • 웹 API를 테스트할 때 사용
  • 스프링 MVC 테스트의 시작점
  • 이 클래스를 통해 HTTP GET, POST 등에 대한 테스트를 할 수 있다

mvc.perform(get("/hello"))

  • MockMvc를 통해 /hello 주소로 HTTP GET 요청을 한다.
  • 체이닝일 지원되어(.and) 여러 검증 기능을 이어서 선언할 수 있다.

.andExpect(status().isOk())

  • mvc.perform의 결과를 검증한다
  • HTTP Header의 Status(200,404,500 등)를 검증한다.

.andExpect(content().string(hello))

  • mvc.perform의 결과를 검증한다.
  • 응답 본문의 내용을 검증한다.
  • Controller에서 리턴하는 값이 맞는지 검증

5. 테스트 코드 실행하여 확인

  • 메소드 왼쪽의 화살표 클릭
  • Run 'hello가_리턴된다()' 클릭

+ Recent posts