[컴] sbt 사용

 scala  / build system

sbt 사용

ref. 1 내용을 일부 정리했다. 자세한 내용은 아래 링크의 내용을 확인하자.

sbt 설치

  • sdkman: https://sdkman.io/install
  • sbt install : https://www.scala-sbt.org/1.x/docs/Installing-sbt-on-Linux.html
curl -s "https://get.sdkman.io" | bash
source "$HOME/.sdkman/bin/sdkman-init.sh"
sdk install java $(sdk list java | grep -o "8\.[0-9]*\.[0-9]*\.hs-adpt" | head -1)
sdk install sbt

sbt 로 project 생성

  1. project directory 생성 및 이동
  2. build.sbt 생성
  3. sbt 실행 --> exit : prject, target 폴더가 만들어진다.
  4. example package 생성
    • <proj_root>\src\main\scala\example\ directory 생성
  5. library 추가

mkdir kbdumpna
cd kbdumpna
touch build.sbt

sbt
sbt> scalaVersion
sbt> set ThisBuild / scalaVersion := "2.12.12"

sbt> reload
sbt> test

sbt> compile
sbt> run


sbt> reload
sbt> compile

template 에서 project 시작하기

boilerplate 에서 시작할 수 있다. 아래처럼 sbt new 를 사용하자.

  • sbt new akka/akka-scala-seed.g8
Microsoft Windows [Version 10.0.19041.450]
(c) 2020 Microsoft Corporation. All rights reserved.

D:\a\prog\scala\akka\simple-chat>sbt new akka/akka-scala-seed.g8
[info] [launcher] getting org.scala-sbt sbt 1.3.13  (this may take some time)...
downloading https://repo1.maven.org/maven2/org/scala-sbt/main_2.12/1.3.13/main_2.12-1.3.13.jar ...
...
[info] resolving Giter8 0.13.1...

Akka is a toolkit and runtime for building highly concurrent,
distributed, and fault tolerant event-driven apps. This simple
application will get you started building Actor based systems with
Scala. This app uses Akka, Scala, and ScalaTest.

name [akka-quickstart-scala]: simple-chat
akka_version [2.6.8]: 
package [com.example]: com.schat

Template applied in D:\a\prog\scala\akka\simple-chat\.\simple-chat 

sbt interactive shell 에서 명령어

sbt compile처럼 사용할 수도 있고, 또는 sbt 를 실행한 이후에 intereactive shell 에서 compile 명령어를 상요할 수도 있다.

  1. compile
    • compile
    • ~compile 는 watch 와 같다. code 가 변경되면 알아서 compile 하도록 할 수 있다.
  2. 실행
    • run
  3. 변수 정의
    • set ThisBuild / scalaVersion := "2.12.7"
  4. session save
    • sbt interactive shell 에서 정의한 변수들을 session save 명령어를 이용해서 build.sbt 에 저장해 놓을 수 있다.
  5. build.sbt 가 변경된 이후 내용을 reload
    • reload

주의할점

ref.1 에서는 build.sbtThisBuild / scalaVersion := "2.12.7" 라고 적었는데,

sbt 1.3.13 (Oracle Corporation Java 14) 에서 2.12.7 은 아래 이슈가 발생했다. 그래서 2.12.10 을 사용했다.

C:\a\prog\scala\nchat>md nchat
C:\a\prog\scala\nchat>cd nchat

build.sbt 생성


C:\a\prog\scala\nchat>sbt
[warn] Neither build.sbt nor a 'project' directory in the current directory: "C:\a\prog\scala\nchat"
c) continue
q) quit
?c
[info] [launcher] getting org.scala-sbt sbt 1.3.13  (this may take some time)...
downloading https://repo1.maven.org/maven2/org/scala-sbt/main-settings_2.12/1.3.13/main-settings_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/actions_2.12/1.3.13/actions_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/run_2.12/1.3.13/run_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/logic_2.12/1.3.13/logic_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/main_2.12/1.3.13/main_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/sbt/1.3.13/sbt-1.3.13.jar ...
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
:: loading settings :: url = jar:file:/C:/Program%20Files%20(x86)/sbt/bin/sbt-launch.jar!/org/apache/ivy/core/settings/ivysettings.xml
downloading https://repo1.maven.org/maven2/org/scala-sbt/command_2.12/1.3.13/command_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/collections_2.12/1.3.13/collections_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#sbt;1.3.13!sbt.jar (1202ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/scripted-sbt-redux_2.12/1.3.13/scripted-sbt-redux_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#run_2.12;1.3.13!run_2.12.jar (1238ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/scripted-plugin_2.12/1.3.13/scripted-plugin_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#logic_2.12;1.3.13!logic_2.12.jar (1339ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/zinc-lm-integration_2.12/1.3.13/zinc-lm-integration_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#command_2.12;1.3.13!command_2.12.jar (1500ms)
downloading https://repo1.maven.org/maven2/org/scala-lang/modules/scala-xml_2.12/1.3.0/scala-xml_2.12-1.3.0.jar ...
        [SUCCESSFUL ] org.scala-sbt#actions_2.12;1.3.13!actions_2.12.jar (1685ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/launcher-interface/1.1.4/launcher-interface-1.1.4.jar ...
        [SUCCESSFUL ] org.scala-sbt#collections_2.12;1.3.13!collections_2.12.jar (1696ms)
downloading https://repo1.maven.org/maven2/io/get-coursier/lm-coursier-shaded_2.12/2.0.0-RC6-4/lm-coursier-shaded_2.12-2.0.0-RC6-4.jar ...
        [SUCCESSFUL ] org.scala-sbt#scripted-plugin_2.12;1.3.13!scripted-plugin_2.12.jar (561ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/librarymanagement-core_2.12/1.3.4/librarymanagement-core_2.12-1.3.4.jar ...
        [SUCCESSFUL ] org.scala-sbt#zinc-lm-integration_2.12;1.3.13!zinc-lm-integration_2.12.jar (695ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/librarymanagement-ivy_2.12/1.3.4/librarymanagement-ivy_2.12-1.3.4.jar ...
        [SUCCESSFUL ] org.scala-sbt#scripted-sbt-redux_2.12;1.3.13!scripted-sbt-redux_2.12.jar (921ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/completion_2.12/1.3.13/completion_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#main_2.12;1.3.13!main_2.12.jar (2188ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/task-system_2.12/1.3.13/task-system_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#launcher-interface;1.1.4!launcher-interface.jar (676ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/tasks_2.12/1.3.13/tasks_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-lang.modules#scala-xml_2.12;1.3.0!scala-xml_2.12.jar(bundle) (873ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/testing_2.12/1.3.13/testing_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#task-system_2.12;1.3.13!task-system_2.12.jar (574ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/test-agent/1.3.13/test-agent-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#librarymanagement-core_2.12;1.3.4!librarymanagement-core_2.12.jar (1343ms)
        [SUCCESSFUL ] org.scala-sbt#testing_2.12;1.3.13!testing_2.12.jar (764ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/protocol_2.12/1.3.13/protocol_2.12-1.3.13.jar ...
downloading https://repo1.maven.org/maven2/org/scala-sbt/core-macros_2.12/1.3.13/core-macros_2.12-1.3.13.jar ...
        [SUCCESSFUL ] org.scala-sbt#completion_2.12;1.3.13!completion_2.12.jar (1142ms)
downloading https://repo1.maven.org/maven2/org/scala-sbt/ivy/ivy/2.3.0-sbt-839fad1cdc07cf6fc81364d74c323867230432ad/ivy-2.3.0-sbt-839fad1cdc07cf6fc81364d74c323867230432ad.jar ...
        [SUCCESSFUL ] org.scala-sbt#test-agent;1.3.13!test-agent.jar (577ms)
        [SUCCESSFUL ] org.scala-sbt#tasks_2.12;1.3.13!tasks_2.12.jar (1038ms)
        [SUCCESSFUL ] org.scala-sbt#librarymanagement-ivy_2.12;1.3.4!librarymanagement-ivy_2.12.jar (1558ms)
        [SUCCESSFUL ] org.scala-sbt#core-macros_2.12;1.3.13!core-macros_2.12.jar (604ms)
        [SUCCESSFUL ] org.scala-sbt#protocol_2.12;1.3.13!protocol_2.12.jar (730ms)
        [SUCCESSFUL ] io.get-coursier#lm-coursier-shaded_2.12;2.0.0-RC6-4!lm-coursier-shaded_2.12.jar (2933ms)
        [SUCCESSFUL ] org.scala-sbt#main-settings_2.12;1.3.13!main-settings_2.12.jar (6066ms)
        [SUCCESSFUL ] org.scala-sbt.ivy#ivy;2.3.0-sbt-839fad1cdc07cf6fc81364d74c323867230432ad!ivy.jar (3345ms)
:: retrieving :: org.scala-sbt#boot-app
        confs: [default]
        81 artifacts copied, 0 already retrieved
[warn] No sbt.version set in project/build.properties, base directory: C:\a\prog\scala\nchat
[info] welcome to sbt 1.3.13 (Oracle Corporation Java 14)
[info] set current project to nchat (in build file:/C:/a/prog/scala/nchat/)
[info] sbt server started at local:sbt-server-251924dafe1d3bf2356b
sbt:nchat> exit
[info] shutting down sbt server
sbt:Hello> about
[info] This is sbt 1.3.13
[info] The current project is ProjectRef(uri("file:/C:/a/prog/scala/test2/"), "hello") 0.1.0-SNAPSHOT
[info] The current project is built against Scala 2.12.10
[info] Available Plugins
[info]  - sbt.ScriptedPlugin
[info]  - sbt.plugins.CorePlugin
[info]  - sbt.plugins.Giter8TemplatePlugin
[info]  - sbt.plugins.IvyPlugin
[info]  - sbt.plugins.JUnitXmlReportPlugin
[info]  - sbt.plugins.JvmPlugin
[info]  - sbt.plugins.SbtPlugin
[info]  - sbt.plugins.SemanticdbPlugin
[info] sbt, sbt plugins, and build definitions are using Scala 2.12.10
sbt:Hello>   

Scala REPL

sbt:Hello> console
[info] Starting scala interpreter...
Welcome to Scala 2.12.10 (OpenJDK 64-Bit Server VM, Java 14).
Type in expressions for evaluation. Or try :help.

scala> println("test")
test

scala> :q

[success] Total time: 444 s (07:24), completed 2020. 8. 14. ?ㅼ쟾 11:31:366
sbt:Hello>

Reference

  1. sbt Reference Manual — Getting Started with sbt

[컴] scala 시작하기

vscode debug / debugging

scala 시작하기

Simple Build Tool(sbt) 설치

choco install sbt

scala 시작하기

scala 바로 해보기

ScalaFiddle 에 가서 바로 code 를 작성하고, 실행해 볼 수 있다.

vscode

Visual Studio Code · Metals 라는 것을 제공한다. Metals 은 language server 이다.(Scala (Metals) - Visual Studio Marketplace)

Build Tools Overview · Metals 를 보면, 빌드는 Bloop 이라는 Scala build server 로 보내게 된다.

scala project 생성 및 실행

직접설정해서 외부 library 를 쓸 수도 있겠지만, dependency 관리를 위해서는 sbt 를 쓰는 것이 낫다고 한다.


https://search.maven.org/ 에서 원하는 library 를 검색할 수 있다.

C:\a\programming\scala\>sbt new sbt/scala-seed.g8

C:\a\programming\scala\>sbt new sbt/scala-seed.g8
[info] welcome to sbt 1.3.13 (N/A Java 11.0.8)
[info] set current project to scala-crawl (in build file:/C:/a/programming/scala/)
[info] set current project to scala-crawl (in build file:/C:/a/programming/scala/)
[info] resolving Giter8 0.13.1...

A minimal Scala project.

name [Scala Seed Project]: scala-crawl

Template applied in C:\a\programming\scala\scala-crawl\.\scala-crawl


C:\a\programming\scala\>sbt run

debug mode in vscode

play framework

sbt -jvm-debug 5005 run
// launch.json
{
    "type": "scala",
    "request": "attach",
    "name": "attach 5005",
    "buildTarget": "root",
    "hostName": "localhost",
    "port": 5005
},

simple http client

  1. How to write a simple HTTP GET request client in Scala (with a timeout) | alvinalexander.com


See also

  1. Older Migration Guides • Akka Documentation
  2. Migration Guide 1.3.x to 2.0.x — Akka Documentation
  3. Migration Guide 2.1.x to 2.2.x — Akka Documentation
  4. Migration Guide 2.3.x to 2.4.x — Akka Documentation 
  5. Migration Guide 2.5.x to 2.6.x • Akka Documentation  
  6. Using TCP • Akka Documentation
  7. Routers • Akka Documentation 



[컴][유틸] Powertoys run 을 더 잘 쓰는 법

파워토이즈 팁, tips / power toys tips / how to restrict search indexing / 서치  / 검색 인덱싱 설정 방법 / 줄이는 법 / 메모리 줄이기 / 빠르게 하기 / 최적화

Powertoys run 을 더 잘 쓰는 법

위의 글을 보면, Product-Launcher 가 "Windows 검색"(Searching Windows) 의 DB 를 사용하는 듯 하다.

그러므로 search 의 설정을 윈도우즈의 검색 '세팅'에서 하면 된다.

기본적으로 검색을 빠르게 하기위해서 indexing 하는 양을 줄이면 된다. 그래서 "제외된폴더"(Exculded Folder) 를 더 많이 설정하면 된다.

좀 더 자세한 설정을 "더 많은 검색 인덱서 설정"에서 할 수 있다.(type 별 검색등)

기본적으로 "AppData"를 indexing 한다. 개인적으로는 이 부분을 제외한다. 이것으로 개인적으로 30MB 정도 메모리를 줄였다. 하지만 여전히 높은 메모리 사용률을 보인다.

  • Total : 약 105MB
    • PowerToys.exe : 약 11MB
    • PowerLauncher.exe : 약 93MB


See Also

  1. windows 10 에서 검색에서 start menu 의 결과가 표시 되지 않을 때
  2. windows 에서 launchy 대신 사용할 수 있는 program


[컴][유틸] Dockerfile


도커 / 다커 / 도커파일

Dockerfile

기본적으로 Dockerfile 의 syntax 는 아래와 같은 모양을 갖는다.

  • Dockerfile 에 적힌 순서대로 실행된다.
  • INSTRUCTION 이나 #(comment) 앞에 공백은 없어야 한다.(가능은 하지만, 이건 backward compatibility 때문이다.)
  • \ 은 Line continuation characters 이다.
  • # directive=valueparser directives 이다.
# Comment
INSTRUCTION arguments

# example
RUN echo 'we are running some # of cool things'
RUN echo hello \
world

parser directives

말그대로 parser 에게 "어떻게 해라" 라고 가르치는 지시자 같은 것이다.

현재 아래 2가지를 지원한다.

  • syntax
  • escape : escape 문자를 어떤것으로 할지 정한다. window 등에서는 이미 \가 쓰이기 때문에, \ 를 다른 것으로 정해서 사용해야 하는데, 이럴때 이 directive 를 사용하면 된다.
# syntax=docker.io/docker/dockerfile:1
# escape=\ (backslash)

변수지정

  • ${foo:-word} : foo 변수가 없으면 word 를 사용
  • ${foo:+word} : foo 변수가 있으면 word 를 사용
ENV foo /bar
WORKDIR ${foo}    # WORKDIR /bar

.dockerignore file

docker CLI 가 docker deamon 에 context 를 보내기 전에, .dockerignore file 을 확인한다.

아래처럼 작성하면 된다. 이 match rule 은 Go의 filepath.Match rules 을 따른다고 한다.

# comment
*/temp*     --> root 의 모든 level 1 의 subdirectory 의 temp* file
*/*/temp*
temp?       --> tempa, tempb 등 temp뒤에 character 1개가 붙은 file

# 순서대로 읽으면 된다. 
# - 아래는 모든 .md 를 exclude 한다.
# - README.md 는 exclude 에서 제외한다.
# - README-secret.md 는 exclude 한다.
*.md
!README.md
README-secret.md

Instructions

  • FROM

  • RUN : image 를 생성할때 실행할 명령어

    • RUN apt-get update && apt-get install -y x11vnc xvfb firefox
  • CMD : container에서 실행할 명령어

  • LABEL

  • MAINTAINER (deprecated)

  • EXPOSE

    • EXPOSE 5900 : container 에게 tcp 5900 번 port 를 listen 하라고 알려준다.
    • EXPOSE 80/tcp
    • docker run -p 80:80/tcp, 이렇게 -p option 으로 override 된다.
    • docker run -P : -P option 에 의해 EXPOSE 에 적힌 port 가 실제로 publish 된다.
  • ENV

  • ADD

    • ADD --chown=myid:mygroup home.txt relativeDir/
    • file 을 image 로 copy
    • 자동으로 recursive 하게 copy 를 해준다.
    • Best practices ADD or COPY : copy 가 더 선호된다.
  • COPY

    • COPY --chown=myid:mygroup home.txt relativeDir/
    • file 을 container 로 copy
  • ENTRYPOINT

    • docker 를 실행파일처럼 사용하게 해준다. docker run <image> -d 라는 명령어를 실행하면, -d 가 entrypoint 의 parameter 로 전달된다.
    • 예를 들어 ENTRYPOINT 를 'python3' 로 해놨다면, docker run <image> a.py 라고 치면, docker 가 load 되고 나서, python3 a.py 가 실행된다.
  • VOLUME

  • USER

  • WORKDIR

  • ARG

  • ONBUILD

    • image 에 trigger instruction 을 넣을 수 있다. 이 trigger instruction 은 추후에 사용된다. 예를 들면 docker image 가 다른 build 의 base build 로 사용되는 경우에, 즉, docker image 를 하나 받고 나서, 그 것을 기반으로 build 를 하려는 경우에 쓰일 수 있다.
  • STOPSIGNAL

  • HEALTHCHECK

  • SHELL

examples

# Firefox over VNC
#
# VERSION               0.3

FROM ubuntu
ENF myName2 Gaed
ENV myName="John Doe" myDog=Rex\ The\ Dog \
    myCat=fluffy
WORKDIR /home/gaga

# Install vnc, xvfb in order to create a 'fake' display and firefox
RUN apt-get update && apt-get install -y x11vnc xvfb firefox
RUN mkdir ~/.vnc
RUN echo ${myName2}
# Setup a password
RUN x11vnc -storepasswd 1234 ~/.vnc/passwd
# Autostart firefox (might not be the best way, but it does the trick)
RUN bash -c 'echo "firefox" >> /.bashrc'

# home.txt file 을 docker image 내의 /home/gaga/relativeDir 로 copy
# --chown 은 linux 에서만 쓰이는데, file 에 대해 소유자를 변경시켜준다.
# --chown 이 없다면, 0 에대한 UID, GID 를 사용한다.(아마도 root)
ADD --chown=myid:mygroup home.txt relativeDir/

EXPOSE 5900
EXPOSE 80/tcp
CMD    ["x11vnc", "-forever", "-usepw", "-create"]

See Also

  1. 쿠...sal: [컴][유틸] kali linux 에서 Docker 설치 및 사용
  2. 쿠...sal: [컴] docker 에서 /etc/hosts 변경
  3. 쿠...sal: [컴] docker commands
  4. 쿠…sal: [컴] 간단한 Jekyll Dockerfile 만들기
  5. 쿠…sal: [컴] Dockerfile 내의 VOLUME command 와 -v 의 차이
  6. 쿠…sal: [컴][웹] nginx build 방법

Reference

  1. Dockerfile reference | Docker Documentation

[컴][유틸] kali linux 에서 Docker 설치 및 사용

debian linux docker 사용 / docker 사용 / 도커 / 다커 /

kali linux 에서 Docker 설치 및 사용

환경

  • os : kali-linux-2019.4

Docker engine 설치

kali 는 debian base 의 linux 여서 debian 에서 docker 를 설치하는 방식(ref. 1) 을 참고하면 된다.

그런데 kali 자체에서도 docker 를 쉽게 설치할 수 있게 해놨다. 그래서 ref.2 를 참고하면 된다.

$ sudo apt update
$ sudo apt install -y docker.io
$ sudo systemctl enable docker --now
$ docker

hello world

$ sudo docker run hello-world
Unable to find image 'hello-world:latest' locally
latest: Pulling from library/hello-world
0e03bdcc26d7: Pull complete 
Digest: sha256:49a1c8800c94df04e9658809b006fd8a686cab8028d33cfba2cc049724254202
Status: Downloaded newer image for hello-world:latest

Hello from Docker!
This message shows ...
...

Docker image 실행과정

  1. docker file(Dockerfile) 이 존재하면,(Dockerfile 예제)
  2. image 를 build 하고,
  3. image 를 실행하게 된다. (Run your image as a container)
$ sudo docker build --tag name:tag <dir>
$ sudo docker run --publish 8000:8080 --detach --name <name>:<tag>

삭제

$ sudo docker stop <name>
$ sudo docker rm <name>

## 또는 굳이 stop 을 안하려면, --force 를 사용하면, 알아서 stop 시켜준다.
$ sudo docker rm --force <name>

Dockerfile 작성

docker commands

alias

alias dockrm='docker rm -f'
alias dockrmi='docker rmi -f'
alias dockls='docker ps -a'
alias docklsi='docker image ls'
alias dockbuild='docker build -t'

function docksh() { docker run -it $1 sh; }

See Also

Reference

  1. Install Docker Engine on Debian | Docker Documentation
  2. Installing Docker on Kali Linux | Kali Linux Documentation

[컴][알고리즘] skyline problem

divide and conquer /


작성중...

skyline problem

merge sort 와 비슷한방법으로 해결한다.(divide & conquer)

merge sort 가 값을 만들어가는 모양처럼, array 가 있으면 일단 개개별로 분할될 때까지 내려가고, 그 개개의 값들을 merge 하면서 값을 처리한다.(Merge sort gif 참고)

이 문제에서는 x 를 다시 정렬할 필요가 있다. 아래 그림처럼 값을 새로운 모양으로 바꾸면서, 정렬이 안된 상태가 되기 때문이다. 그러므로 이런 merge sort 방식이 잘 어울린다.

merge 부분

들어온 input 에 대해서 length 가 1일때(base condition)
"merge 할때 최종적으로 표현하려는 모양"을 return 한다.

여기서는 [[left, height], [left2, hegith2], ...] 이런 모양이다.


핵심은 두개의 배열을 돌면서 하나의 배열이 끝날때까지만 돈다.
그러면서 필요한 처리를 하고, 그 이후의 배열의 원소는 전부 append 한다.
element 단위에서부터 이 작업을 하기에 남아서 뒤에 붙이게 되는 값들은 전부 정렬이 된 이후의 값들이다.

while i < len(arr1) and j < len(arr2):
  ...
  i++
  j++

res.extend(arr1[i:])
res.extend(arr2[j:])

  • 여기서 계속해서 x 를 움직이고, 
  • x 에 해당하는 height 를 비교한다. 
  • merge 가 되면서, x 는 정렬이 되어 간다. 
  • 그러면서 x 지점의 height 가 좋은지 더 높은지 확인한다.
빌딩이 끝나는 곳에 해당하는 x 에서는 height 가 0 이기 때문에, x 위치에서 가장높은 height 만 선택하면 된다.(max(h1, h2))



python code

source from : ref. 1

def skyline(buildings):
    # building = [[left, right, height], [2, 9, 10], ...]
    if not buildings:
        return []
    if len(buildings) == 1:
        # [[left, height], ...]
        return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

    mid = len(buildings) // 2
    left = skyline(buildings[:mid])
    right = skyline(buildings[mid:])
    return merge(left, right)

def merge(left, right):
    h1, h2, hcurrent = 0, 0, 0
    i, j = 0, 0
    result = []

    while i < len(left) and j < len(right):
        x0 = left[i][0]
        x1 = right[j][0]
        if left[i][0] < right[j][0]:
            # 현재의 x 에 해당하는 h 를 선택한다.
            h1 = left[i][1]
            curX = left[i][0]
            i += 1
        elif right[j][0] < left[i][0]:
            h2 = right[j][1]
            curX = right[j][0]
            j += 1
        else:
            h1 = left[i][1]
            h2 = right[j][1]
            curX = right[j][0]
            i += 1
            j += 1
        # 현재의 h 는 h1, h2 중 하나이다. 그중에 큰 값을 선택한다.
        # x 가 변하면, h 도 같이 변한다. 
        # 건물이 끝나는 x 에선 h가 0 이 된다.
        if max(h1, h2) != hcurrent:
            hcurrent = max(h1, h2)
            result.append([curX, hcurrent])
    result.extend(right[j:])
    result.extend(left[i:])
    return result


See Also

  1. [컴][알고리즘] Merge sort

Reference

  1. performance - Python program to solve the "skyline problem" - Code Review Stack Exchange