문제링크 : https://www.acmicpc.net/problem/1038


아이디어

  • N번째까지 순회하면서 숫자를 확인
  • 순회할때 조건
    • 1자리수는 통과
    • 자리수 올라갈떄, 10 곱한뒤에, 가장 마지막 수보다 작은것들만 추가
    • 그럼 이전에 감소한 수를 재사용해야함 > 큐를 사용해서 이전에 계산한 값 넣어주기
  • 일의 자리 일때 조심!

시간복잡도 계산

  • N까지 순회 : O(N)
  • 마지막 일의자리 10개 순회 : O(10)

자료구조

  • queue <long long>
    • 최대 숫자 될수 있는수 10자리 > long long 사용
    • 감소하는 수이기 때문에 숫자가 총 10개

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <queue>
 
using namespace std;
typedef long long ll;
 
int main() {
    int N; cin >> N;
    
    // 1의 자리 미리 출력
    // 큐에 넣은 후 출력하려고하면 복잡해짐
    if(N <=9) {
        cout << N << '\n';
        return 0;
    }
    
    queue<ll> q;
    for(int i=0; i<=9; i++) q.push(i);
    
    int cnt=9;
    
    while(!q.empty()) {
        ll eq = q.front(); q.pop();
        
        // 일의자리 구해서 작은수까지 순회
        int lastNum = eq%10;
        for(int i=0; i<lastNum; i++) {
            
            ll ev = eq*10 + i;
            q.push(ev);
            cnt++;
            if(cnt==N) {
                cout << ev << '\n';
                return 0;
            }
        }
    }
    
    cout << -1 << '\n';
    
    return 0;
}
 
cs

문제유형

  • 브루트포스 - 큐
    • 특정 순번의 값을 확인해야할때
    • 이전에 사용한 값을 재활용 할수 있을 때
    • 큐에 넣고, 뽑으면서 다음 값을 구함

'알고리즘 > 백준' 카테고리의 다른 글

백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13

세줄 정리

  • 상태에 따라서 다르게 동작해야할 때
  • 케이스가 추가될 때마다 코드를 수정하는 것이 복잡해짐
  • 상태를 각각의 클래스로 만들고, 각 상태에서 메서드를 제공

디자인 패턴 적용 안한경우

단점

  • if else 구문을 사용하기 때문에, 상태가 추가될 경우, VendingMachine 클래스 수정해줘야함
    (이를 개방 폐쇄의 원칙에 어긋난다고 합니다.)
  • if else 구문을 추가해주고, 그때의 메소드를 추가

상황

  • 자판기 소프트웨어에서
  • 제품이 판매 가능하면 상품이 나오고,
  • 제품이 매진되었으면 상품이 나오지 않고 빨간 불빛을 표시

if else로 구현할 경우

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class VendingMachine {
private String state = “AVAILABLE”; // SOLDOUT or AVAILABLE
    
    public void select() {
        if(state.equals(“AVAILABLE”)) provideProduct();
        else if(state.equals(“SOLDOUT”)) redRight();
    }
 
    private void provideProduct() {
        ...
    }
 
    private void redRight() {
        ...
    }
}
 
cs

제품이 한개 남았을때는 초록색 불빛 기능 추가 될때

1
2
3
4
5
6
7
8
9
10
11
public class VendingMachine {
private String state = “AVAILABLE”; // SOLDOUT or AVAILABLE or ONELEFT
    
    public void select() {
        if(state.equals(“AVAILABLE”)) provideProduct();
        else if(state.equals(“SOLDOUT”)) redRight();
        else if(state.equals(“ONELEFT”)) greenRight();
    }
 
}
 
cs

상태 패턴

State Pattern UML

개념

  • 각각의 상태 객체가 기능을 제공
  • 콘텍스트는 상태 객체를 가지고, 상태 객체에서 기능을 실행

장점

  • 상태가 많아져 클래스 개수는 증가하지만, 코드의 복잡도는 증가하지 않음
  • 상태별 동작을 수정하기가 쉬움
    • if else의 경우 각각의 상태에서 실행하는 메소드를 찾아서 수정해줘야함

VendingMachine(Context)

1
2
3
4
5
6
7
8
9
10
11
12
public class VendingMachine {
    private State state;
 
    public VendingMachine(State state) {
        this.state = state;
    }
 
    public void select() {
        state.select();
    }
}
 
cs

상태 인터페이스

1
2
3
4
public interface State {
    public void select();
}
 
cs

상태 인터페이스 구현한 상태 클래스

1
2
3
4
5
6
7
8
9
10
11
public class AvailableState implements State {
    @Override
    public void select() {
        provideProduct();
    }    
 
    private void provideProduct() {
        ...
    }
}
 
cs

상태 패턴 vs 전략 패턴

사전지식 : 전략패턴

두 패턴 모두 각각의 상황에 따라서 다른 동작을 할때, 각 상황을 별도의 클래스로 다루는 것이 동일하다
상태 패턴의 경우 상태를 클래스로 다루고, 전략 패턴은 전략을 클래스로 다룬다는 것이 동일하다
하지만, 결국 두개가 같은게 아닐까? 라는 의문이 들었고, 찾아본 결과 답은 다음과 같다.

상태 패턴은 상태 객체에서 상태를 바꿀 수 있고, 전략 패턴은 불가능하다

상태 패턴을 먼저 살펴보자. 위의 예제에서 ONELEFT(음료수 하나 남은 상황) 상태에서 자판기에서 음료수를 뽑는다면, 상태가 SOLDOUT으로 바뀌어야한다. (위 코드에서 구체적으로 구현하지는 않았다… 여러분의 이해를 돕기위해서 ㅎㅎ) 이와 같이 상태패턴은 상태 객체에서, 콘텍스트 객체의 상태 변경까지 포함한 개념이다.

전략 패턴을 보자.
별도의 상태를 관리하지 않고, 한번 전략이 선택되면 실행되고 끝이다. 바뀌지 않는다.
예를들면, 고객의 등급에 따라 다른 할인 혜택을 적용할경우

정리하자면,

  • 공통점 : 상태 패턴과 전략 패턴은 각각 상태와 전략을 객체화 해서 관리
  • 차이점 : 상태 패턴은 상태를 관리하고, 전략 패턴은 전략을 관리하지 않음

출처

- https://defacto-standard.tistory.com/47

- https://en.wikipedia.org/wiki/State_pattern

- 개발자가 반드시 정복해야할 객체 지향과 디자인 패턴(최범균 저) Ch.07

'객체 지향 프로그래밍 > 디자인 패턴' 카테고리의 다른 글

[디자인 패턴] 템플릿 메서드 패턴(Template Method Pattern)  (0) 2021.03.13
[디자인 패턴] 전략 패턴(Strategy Pattern)  (0) 2021.03.13

세줄 정리

  • 상속을 통해 상위 클래스의 기능 확장할때 사용하는 대표적 방법
  • 전체 흐름은 동일한데 일부 기능이 다른 경우, 템플릿 메서드 정의 후 상속받은 클래스에서 다른 메서드 정의
  • 자바에서는 추상클래스를 사용해서 구현
    template method pattern uml

예시

상황

  • 손님이 결제를 할때 현금, 카드로 계산하는 경우
  • 결제수단을 받아오고 돌려주는 방법은 똑같음
  • 하지만 현금이냐, 카드냐 결제 하는 방법이 다름

추상클래스 Calculator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public abstract Calculator {
 
    // 탬플릿 메서드
    public void pay(int price) {
        takePayment(); // 결제 수단 받아옴
        doPayment(); // 결제 수행
        returnPayment(); // 결제 수단 돌려줌
        
    }
 
    protected void takePayment() {
        ...
    }
 
    protected void doPayment() {
        ...
    }
 
 
    // 클래스마다 달라지는 부분
    protected abstract void doPayment();
    
}
 
cs

클래스 CashCalculator

1
2
3
4
5
6
7
public class CahCalculator extends Calculator {
    @Override
    protected void doPayment() {
        ...
    }
}
 
cs

특징

특징1. 부모 클래스가 흐름 제어

  • 템플릿 메서드 패턴은 부모 클래스의 템플릿 메서드가 자식 클래스의 메서드를 호출
  • 일반적인 경우, 자식 클래스가 흐름 제어(자식 클래스가 부모 클래스 기능 재사용할지 결정)
  • 예시 : SuperCar 클래스의 turnOn() 메소드는 부모 클래스의 turnOn() 재사용 여부를 결정
1
2
3
4
5
6
7
public class SuperCar extends ZetEngine {
    @Override
    public void turnOn() {
        if(notReady) beep();
        else super.turnOn(); // 자식 클래스에서 부모 클래스 기능 재사용여부 결정
    }
}
cs

특징2. 템플릿 메서드 접근제어자

  • 템플릿 메서드 안에서, 자식 클래스마다 달라지는 메서드의 경우 하위 타입에서만 재정의 할수 있어야해서 protected 사용

특징 3. hook 메소드

  • hook 메서드
    • 부모클래스에서 default 기능을 정의해두거나, 비워둬서
    • 자식클래스에서 오버라이드 하도록 만들어준 메소드
  • 자식 클래스마다 달라지는 메서드의 경우, 기본구현을 제공할 수도 있고 안할수도 있는데
  • 기본구현을 제공하는 메서드를 hook 메서드라고 함

자바에서 사용하는 경우 : AbstractMap<K,V> 클래스

  • HashMap, TreeMap은 AbstractMap을 상속받아 구현하며
  • AbstractMap(추상클래스)는 Map 인터페이스를 implements해서 get 메소드 구현해야함
  • AbstractMap 상속받은 HashMap, TreeMap은 get() 메소드 가지지만 자신만의 구현방법으로 다르게 구현되어있음

출처

'객체 지향 프로그래밍 > 디자인 패턴' 카테고리의 다른 글

[디자인 패턴] 상태 패턴(State Pattern)  (0) 2021.03.13
[디자인 패턴] 전략 패턴(Strategy Pattern)  (0) 2021.03.13

+ Recent posts

티스토리툴바