47일차)알고리즘 문제(큰 수 만들기), 챌린지반 3주차 강의(디자인 패턴, MVVM), 챌린지반 과제

>알고리즘 문제

1. 큰 수 만들기

1)문제

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

2)솔루션

import java.util.*
class Solution {
    fun solution(number: String, k: Int): String {
        val tmp=StringBuilder()
        var del=k
        var idx=0
        val deq=ArrayDeque<Int>()
        
        while(idx!=number.length){
            val num=minOf(del-deq.size+idx,number.length-1)
            while(idx<=num){
                val cur=number[idx++].toString().toInt()
                while(deq.isNotEmpty()&&del!=0&&cur>deq.peekFirst()){
                    deq.removeFirst()
                    del--
                }
                deq.addFirst(cur)
            } 
            tmp.append(deq.removeLast())
        }
        
        repeat(deq.size-del){
            tmp.append(deq.removeLast())
        }
        
        //del남으면 deque의 앞부분을 del만큼 제거=>즉 del만큼 남게 deque에서 뒤로 빼주고 남은건 버림
        return tmp.toString()
    }
}

-덱안에 남아있는 숫자를 포함한 del개씩 비교해서 숫자를 넣을때는 스택방식으로 넣고 넣는 숫자보다 스택 맨위에 있는 숫자가 크면 넣는 숫자 이하가 될때까지 빼준뒤 넣는 방식으로 함.

-이후 덱의 맨 아래 원소를빼서 스트링빌더에 넣음

-위의 둘을 반복해서 모두 삭제될때까지 혹은 끝까지 읽을때까지 반복

-마지막에 삭제해야하는 del변수만큼 제외하고 나머지를 스트링 빌더에 추가

-마지막으로 스트링빌더를 스트링으로 바꾸면 완료

 

 

>챌린지반 3주차 강의

1. 디자인 패턴: 
-개발 과정에서 발견된 설계 노하우를 정리하여 이름붙인것
-자주 발생하는 문제에 대한 검증된 해결책
<1>Singleton: 프로그램 내에서 인스턴스가 하나만 존재하고 어디서든 접근 가능하게 해주는 패턴
(1)장단점
-객체 생성 횟수를 줄임
-전역변수와 달리 사용전까지 객체가 생성되지 않음
-멀티스레드 환경에서 사용시 동기화 보장X : 레이스 컨디션(두 스레드에서 한 자원가지고 경쟁하는상황)에서 기다리지않고 변경시켜서 결과가 잘못나올 수 있음
(2)주로사용
-로그기록 객체
-유저 매니저
-테이터 테이블 정보 저장 클래스
(3)사용

[1]object:

-파라미터 없이 생성하는 싱글톤 클래스

-클래스처럼 선언 가능. class대신 object를 붙인다.

- 예시

object Objects{
	val name="aaa"
    fun printLog(msg:String){
    	Log.d("Sigleton msg", "msg:${msg}")
    }
}

-사용: 변수로 선언 가능하고 프로퍼티 접근 및 변경도 가능하다.

object Objects{
    var property="aaa"
}
fun main(){
    val a= Objects
    a.property="bbb"
    println(a.property) //bbb출력
}

[2]companion object

-생성자를 통해 파라미터를 전달받는 싱글톤 클래스

-객체생성이 가능하나 동일한 주소를 가리킴

-예시

class Singleton private constructor(context: Context) {

    companion object {
        @Volatile
        private var singleton: Singleton? = null

        fun getInstance(context: Context) :Singleton{
        	//singleton이 null인 경우 synchronized로 진입, 현재 싱글톤 객체에대한 모니터락획득
            return singleton ?: synchronized(this) {
            	//싱글톤이 null이면 싱글톤을 생성후 also에서 싱글톤을 자기자신에게 할당
                //또한, also는 전달받은 수신객체를 반환하므로 synchronized는 싱글톤을 반환하게됨
                singleton ?: Singleton(context).also {
                    singleton = it
                }
            }
        }
    }
}

-@Volatile: 값을 캐시에 저장하지 않고 즉시 메모리 상에 반영시

-synchronized(자원): 자원에 대한 동기화 구현 =>자원에 대해 한번에 한 스레드만이 접근할 수 있도록 함

-위의 코드는 처음 접근할때만 객체를 생성하고 이후엔 생성된 객체를 반환하는 식으로 구현

-also는 수신객체를 반환

-synchronized()는 블록내 연산 결과를 반환

-모니터락이란 해당 객체에 대한 접근권한. 권한을 가진 스레드가 사용중인동안 다른 스레드 접근 불가. synchronized(this)로 쓰면 싱크로나이즈드가 포함되어있는 객체에 대해 모니터락 획득

<2>Strategy
-알고리즘을 캡슐화해 교체해 사용하도록 하는것
-알고리즘 인터페이스 정의 후 인터페이스를 상속받을 클래스에 알고리즘 구현해서 캡슐화
-알고리즘 사용할 클래스에 인터페이스를 포함
(1)전략
-동일 계열 알고리즘군을 정의: 
-각각의 알고리즘을 캡슐화: 인터페이스로 추상화
-상호교환 가능하도록 함: 인터페이스를 상속받는 객체로 정의하여 필요에 따라 갈아끼면 되도록함
-단 이때, 알고리즘을 사용하는 클라이언트와는 상관없이 독립적이어야함: 즉 클라이언트 역할하는 코드 수정없이 되도록
=>즉 클라이언트에서 프로퍼티로 존재하는 식이면 됨.

(2)장단점

-상속으로 해결불가능한 코드중복이나 객체의 실시간 알고리즘 변경시에 유용

-신규 알고리즘 추가, 수정이 용이

-OOP디자인적 관점엔 부합하지 않음

(3)사용 상황

-게임룰을 모드별로 변경하고 싶을시

-상황에 따라 길찾기 알고리즘을 바꾸고 싶을시
(4)예시:

interface MovableStrategy{
    fun move()
}

class rail:MovableStrategy{
    override fun move() {
        println("선로로 이동")
    }
}

class load:MovableStrategy{
    override fun move() {
        println("도로로 이동")
    }
}

open class Vehicle{
    lateinit var ms : MovableStrategy

    fun move(){
        ms.move()
    }

    fun setMS(movableStrategy: MovableStrategy){
        this.ms=movableStrategy
    }
}

class Bus: Vehicle() {}

class Train: Vehicle() {}

class Client{
    fun client(){
        val bus=Bus()
        val train=Train()

        bus.setMS(load())
        train.setMS(rail())

        bus.move()
        train.move()

        bus.setMS(rail())
        bus.move()
    }
}

fun main(){
    val tmp=Client()
    tmp.client()
}

-움직임에서 전략 패턴을 이용

-움직임을 묶어서 추상화 시켜 인터페이스를 만들고 (MovablesStrategy) 도로이동과 선로 이동 클래스로 캡슐화

-캡슐화된 객체를 끼워넣기만 하면 작동하도록 디자인함.


<3>Observer
(1)객체 상태변화를 관찰하는 관찰자들을 객체가 가지고 있다가 상태변화있을시 객체가 옵저버에게 통지하는 패턴

=>객체 상태 변화시 객체에 등록된 관찰자들이 연결된 관찰자 클래스에 상태변화를 알림
(2)일대다(one-to-many) 의존성을 정의(객체 하나와 옵저버 여러개)

(3)사용

-GUI

-채팅프로그램

(4)예시

//관찰자에 대한 인터페이스
interface ObserverInterface{
    fun update()
}

class Observer1:ObserverInterface{
    override fun update() {
        println("1:관찰자 상태 변경 관측")
    }
}

class Observer2:ObserverInterface{
    override fun update() {
        println("2:관찰자 상태 변경 관측")
    }
}

//피관찰자에 대한 인터페이스
interface SubjectInterface{
    fun registerObserver(observerInterface: ObserverInterface)
    fun removeObserver(observerInterface: ObserverInterface)
    fun notification()
}

//피관찰자

class Subject:SubjectInterface{
    val list=ArrayList<ObserverInterface>()

    override fun registerObserver(observerInterface: ObserverInterface) {
        this.list+=observerInterface
    }

    override fun removeObserver(observerInterface: ObserverInterface) {
        this.list.remove(observerInterface)
    }

    override fun notification() {
        list.forEach{it.update()}
    }
}

fun main(){
    val subject=Subject()

    val o1=Observer1()
    val o2=Observer2()
    subject.registerObserver(o1)
    subject.notification()
    println()
    subject.registerObserver(o2)
    subject.notification()
    println()
    subject.removeObserver(o1)
    subject.notification()

}

<4>Decorator

-객체에 추가적인 요건을 동적으로 첨가하는 패턴

-기본 클래스의 서브 클래스를 구성하여, 생성시 상속받은 클래스를 넘겨 확장할 수 있도록 함

(1)구조:

-원본 클래스와 장식자 추상 클래스를 모두 묶는 인터페이스 존재=>둘다 해당 인터페이스를 상속받
-장식자 추상클래스를 상속받는 장식자 클래스들 존재

(2)작동 방식

-원본 클래스를 생성

-원본클래스를 인자로 해서 장식자 클래스를 선언하는 방식으로 데코레이트 해줌

(3)예시

interface Component{
    fun operation()
}

//원본 객체
class Origin:Component{
    override fun operation() {
        println("origin")
    }
}

//장식자 추상 클래스
abstract class Decorator(val component: Component):Component{
    override fun operation(){
        component.operation()
    }
}

class Decorator1(component: Component):Decorator(component){
    override fun operation() {
        super.operation()
        deco1operation()
    }
    fun deco1operation(){
        println("deco1")
    }
}

class Decorator2(component: Component):Decorator(component){
    override fun operation() {
        super.operation()
        deco2operation()
    }
    fun deco2operation(){
        println("deco2")
    }
}


fun main(){
    val origin=Origin()

    val deco1=Decorator1(origin)
    deco1.operation()
    println()

    val deco2=Decorator2(origin)
    deco2.operation()
    println()

    val decoBoth=Decorator1(Decorator2(origin))
    decoBoth.operation()
}

2. MVVM(model view viewmodel)
<1>MVC구조: 

-model에서 데이터 저장

-controller로 데이터 저장 삭제, 사용자와 상호작용, view로 데이터 전달

=>컨트롤러는 여러개의 View를 선택할 수 있는 일대 다수 관계 구조

-view로 화면 보여줌

(1)동작구조

[1]사용자 액션이 컨트롤러로 들어옴

[2]컨트롤러는 액션 확인후 모델 업데이트

[3]컨트롤러는 업데이트된 모델을 나타낼 View를 선택

[4]View가 Model을 이용해 화면을 나타냄(이때 컨트롤러는 어떤뷰를 쓸지 선택만 할뿐 직접 업데이트는 안함)

 

(2)단점

-View와 Model사이 의존성이 높아 복잡성이 높아지고 유지보수를 힘들게함

-단일책임원칙에서 벗어남

 

<2>MVP구조: view와 비즈니스 로직을 분리한 형태

-presenter:뷰에서 요청한 정보로 Model를 가공해 뷰에 전달하는 부분

(1)동작순서

[1]사용자 액션이 뷰를 통해 들어옴

[2]뷰는 데이터를 presenter에 요청

[3]presenter는 model에 데이터 요청

[4]model은 presenter에 데이터 응답

[5]presenter는 view에 데이터 응답

[4]뷰는 presenter가 응답한 데이터를 이용해 화면에 나타냄

(2)특징: MVC의 controller와 달리 presenter는 직접 데이터를 view에 전달하며 1대1로 view와 연결되어있다.

(3)장점: view와 model사이 의존성이 없음

=> API가 바뀔때는 persenter만 수정, 디자인이 바뀔때는 view만 수정

(4)단점: Activity와 presenter가 강하게 묶여있어 presenter재활용이 힘들음(둘 사이 의존성이 높음)

<3>MVVM: view가 viewmodel에 옵저버를 등록하고 변경사항만 관찰

-View model: View를 표현하기 위해 만든 모델. View를 나타내기 위한 모델(데이터 저장소)이자 데이터 처리하는 곳

(1)동작

[1]사용자 액션이 view로 들어옴

[2]view에 액션이 들어오면 command패턴으로 view model에 액션 전달

@command 패턴: 요청을 객체형태로 캡슐화해서 사용자가 보낸 요청을 나중에 이용할수 있도록 요청에 필요한 정보를 저장 또는 로깅, 취소할 수 있게 하는 패턴

[3]view model은 model에 데이터 요청

[4]model은 view model에 요청받은 데이터 응답

[5]view model은 응답받은 데이터를 가공하여 저장

[6]view는 view model과 data binding을 하여 화면을 나타냄

@data binding 패턴: UI요소와 데이터를 연결해서 동기화 시킴

=>여기서는 주로 xml에 data를 연결하는 작업

 

(2)특징:Command패턴과 Data Binding패턴을 사용해 View와 View model간의 의존성을 없앰

=>view Model과 View는 일대 다수관계

 

(3)장점: 각 부분이 독립적이라 모듈화해 개발가능

(4)단점: View model 설계가 어려움 

(5)활용: 영역별로 view model를 설계해서 쉽게 특정 기능을 추가, 삭제 수정이 이루어지도록 할 수 있다.

-예시

<3>MVC와 MVVM의 차이

(1)MVC:

-안드로이드 기본 구조로 model - view - controller로 구성

-Activity가 view와 controller를 동시에 담당

 

(2)MVVM:

-ViewModel과 View(Activity)를 나눔

-비즈니스 로직이 담긴 ViewModel의 재사용성을 늘림

 

@비즈니스vs도메인

-도메인 로직: 현실세계의 문제를 해결하기 위한 로직

-비즈니스 로직: 그 외의 것(외부 네트네킹, 데이터관리, UI관리 등)

=>예시:모바일 송금앱

-계좌잔액 확인, 송금 수수료계산, 사용자 잔액  감소 =>도메인 로직

-송금버튼 활성화or에러, 결제를 위한 외부 서비스 요청, 잔액 db저장 =>비즈니스 로직

 

@둘이 섞여있는 경우도 존재

=>예시: 원화를 몇달러인지 변환해 문자열을 만드는 함

-환율을 얼마로 할것인가?, 계산공식을 어떻게 할 것인가 : 도메인 로직

-문자열 생성: 비즈니스 로직

=>둘을 분리해서 구현하는 것이 중요!

 

>챌린지반 과제

https://appdevelopjava.tistory.com/63

챌린지반 3주차 첫번째 과제: 디자인 패턴 구현