희연's 개발 일기장

https://school.programmers.co.kr/learn/courses/30/lessons/17687

문제 요약

- 사람들이 번갈아가면서 숫자를 하나씩 말하는 게임

- 숫자가 10 이상인 경우, 한 자리씩 끊어서 말한다. 

ex. 123 이면, 1, 2, 3 

- 특정 위치의 사람이 말해야 하는 숫자 순서대로 출력

입력 값

- 진법 n

- 미리 구할 숫자의 개수 t

- 게임 참여 인원 m

- 튜브 순서 p

풀이 방법

- 10진법 숫자를 n진법으로 변환하는 함수 구현 get_convert

- 출력 형식에서 10~15는 대문자 A~F 으로 출력해야 한다.

- 10진법 이상에서만 변환된다.

- 튜브가 말해야 하는 순서를 구해줘서 배열에 담는다.

- 0부터 최대 값까지 숫자를 변환해주고, 튜브가 말해야 하는 순서인 경우 출력 배열에 담아준다.

def get_convert(num, base):
    if num == 0:
        return 0
    
    temp = ''
    while num > 0:
        num, mod = divmod(num, base) # divmod 몫, 나머지
        if base > 10 and 10 <= mod <= 15: 
            temp += "ABCDEF"[mod % 10] # 10 ~ 15는 대문자 ABCDEF 변경
        else:
            temp += str(mod)
    return temp[::-1]

def solution(n, t, m, p): # 진법, 미리 구할 숫자의 개수, 게임 참여 인원, 튜브 순서
    answer = ''
    order = []
    numbers = []
    
    # 말해야 하는 숫자 순서
    for i in range(t):
        order.append(p+m*i)
    
    max_value = order[-1]
    idx = 1
    
    for i in range(max_value):
        change_num = str(get_convert(i, n)) # 바꾼 숫자
        
        for j in change_num:
            if idx in order:
                answer += j
            idx += 1    
    return answer

https://www.acmicpc.net/problem/2910

문제 풀이 

- dictionary에 등장 순서, 빈도수를 저장한다.

- 빈도수를 내림차순, 등장 순서를 오름차순으로 정렬

N, C = map(int, input().split())  # N개의 숫자, C보다 작다
num_list = list(map(int, input().split()))  # 메시지 수열
dict_info = {}  # [0] 등장 순서, [1] 빈도수
idx = 1
answer = ''

for num in num_list:
    if num in dict_info:
        dict_info[num][0] += 1
    else:
        dict_info[num] = [1, idx]
        idx += 1

sorted_num = sorted(dict_info.items(), key=lambda x: [-x[1][0], x[1][1]])

for key, value in sorted_num:
    answer += (str(key) + ' ') * value[0]

print(answer[:-1])

📌 12장 : 직렬화

아이템 85. 자바 직렬화의 대안을 찾으라

• 1997년, 자바에 직렬화 도입
• 직렬화의 근본적인 문제
  • 공격 범위가 넓고, 지속적으로 넓어져 방어가 어렵다.
  • ObjectInputStream의 readObject 메서드를 호출하면 객체 그래프가 역직렬화 되기 떄문
• 가젯(gadget)
  • 역직렬화 과정에서 호출되어 잠재적으로 위험한 동작을 수행하는 메서드
• 역직렬화 폭탄(deserialization bomb)
  • 역직렬화에 시간이 오래 걸리는 짧은 스트림을 역직렬화하다 서비스 거부 공격에 쉽게 노출될 수 있다.
• 직렬화 문제 회피 방법
  • 아무것도 역직렬화하지 않는다.
  • 객체와 바이트 시퀀스를 변환해주는 다른 메커니즘을 사용한다.
  • 크로스-플랫폼 구조화된 데이터 표현(cross-platform structured-data representation)
• 크로스-플랫폼 구조화된 데이터 표현
  • 자바 직렬화보다 간단하다.
  • 임의 객체 그래프를 자동으로 직렬화/역직렬화 하지 않는다.
  • 속성-값 쌍의 집합으로 구성된 간단하고 구조화된 데이터 객체를 사용한다.
  • ex. JSON, 프로토콜 버퍼(protocol buffers)
    • JSON : 텍스트 기반이라 사람이 읽을 수 있다.
    • 프로토콜 버퍼 : 이진 표현이라 효율이 좋다.
    • JSON은 데이터를 표현하는 데 사용, 프로토콜 버퍼는 문서를 위한 스키마(타입)을 제공한다.
    • 프로토콜 버퍼는 사람이 읽을 수 있는 텍스트 표현(pbtxt)도 지원한다.

아이템 86. Serializable 을 구현할지는 신중히 결정하라

• 클래스의 인스턴스를 직렬화 하기 위해서는 클래스 선언에 implements Serializable 붙이기
• 선언은 쉬워보이지만 Serializable 을 구현하면 릴리즈한 뒤에 수정이 어렵다.
  • Serializable 구현 후, 직렬화된 바이트 스트림 인코딩은 공개 API가 된다.
• Serializable 구현은 버그와 보안 구멍이 생길 위험이 높아진다.
  • 객체는 생성자를 사용해 만드는데, 직렬화는 기본 메커니즘을 우회하는 객체 생성 기법
  • 역직렬화를 사용하면 불변식 깨짐과 허가되지 않은 접근에 노출된다.
• Serializable 구현은 신버전 릴리즈할 때 테스트할 것이 늘어난다.
  • 직렬화 수정 후, 구버전으로 역직렬화 할 수 있는지 반대도 가능한지 확인해야 한다.
• 상속용으로 설계된 클래스는 대부분 Serializable을 구현하면 안된다. 인스턴스도 대부분 안된다.
• 내부 클래스는 직렬화를 구현하면 안된다.

아이템 87. 커스텀 직렬화 형태를 고려해보라

• 수정이 어렵기 떄문에 고민한 후에 괜찮다고 판단될 때만 기본 직렬화 형태 사용하기
• 객체의 물리적 표현과 논리적 내용이 같으면 기본 직렬화 형태도 무방하다.
• 차이가 클 때 사용시 문제점
  • 공개 API가 현재의 내부 표현 방식에 영구히 묶인다.
  • 너무 많은 공간을 차지할 수 있다.
  • 시간이 너무 많이 걸릴 수 있다.
  • 스택 오버플로를 일으킬 수 있다.

아이템 88. readObject 메서드는 방어적으로 작성하라

• readObject는 어떤 바이트 스트림이 넘어와도 유효한 인스턴스를 만들어야 한다.
• 안전한 readObject 메서드를 작성하는 방법
  • private 이어야 하는 객체 참조 필드는 각 필드가 가리키는 객체를 방어적으로 복사해야 한다.
  • 모든 불변식을 검사해서 어긋나는 게 발견되면, InvalidObjectException 을 던진다.
  • 역직렬화 후 객체 그래프 전체의 유효성을 검사해아 하면, ObjectInputValidation 인터페이스를 사용해라
  • 재정의할 수 있는 메서드를 호출하지 않는다.

아이템 89. 인스턴스 수를 통제해야 한다면 readResolve 보다는 열거 타입을 사용하라

• readResolve 를 인스턴스 통제 목적으로 사용하려면 객체 참조 타입 인스턴스 필드는 모두 transient 으로 선언해야 한다.
  • 그렇게 하지 않으면, readResolve 메서드가 수행되기 전에 역직렬화된 객체의 참조를 공격할 수도 있다.
• 직렬화 가능한 인스턴스 통제 클래스를 열거 타입을 이용해 구현하면 선언한 상수 외의 다른 객체는 존재하지 않는 것을 보장해준다.
• 열거 타입 싱글턴 예시

public enum Elvis { 
    INSTANCE;
    private String[] favoriteSongs =
        { "Hound Dog", "Heartbreak Hotel" };
    public void printFavorites() {
        System. out.println(Arrays.toString (favoriteSongs));
    } 
}

private static class SerializationProxy implements Serializable { 
    private final Date start;
    private final Date end;
    
    Serializationproxy(Period p) { 
        this.start = p.start; 
        this.end = p.end;
    }
    private static final long serialVersionUID = 
            234098243823485285L; // 아무 값이나 상관없다. (아이템 87)
}

// 바깥 클래스에 추가 : 직렬화 프록시 패턴용 writeReplace 메서드
// 직렬화가 이뤄지기 전에 바깥 클래스 인스턴스를 직렬화 프록시로 변환
private Object writeReplace() {
    return new SerializationProxy(this); 
}

// 직렬화 프록시 패턴용 readObject 메서드
private void readObject(ObjectlnputStream stream) 
        throws InvalidObjectException {
    throw new InvalidObjectException("프록시가 필요합니다.");
}

// Period.SerializationProxy용 readResolve 메서드
// 역직렬화 시에 직렬화 시스템이 직렬화 프록시를 다시 바깥 클래스의 인스턴스로 변환
private Object readResolve() {
  return new Period(start, end); // public 생성자를 사용한다.
}

📌 11장 : 동시성

아이템 78. 공유 중인 가변 데이터는 동기화해 사용하라

• synchronized
  • 해당 메서드나 블록을 한 번에 한 스레드씩 수행하도록 보장
  • 일반적인 동기화
    • 한 객체가 일관된 상태를 가지고 생성, 객체에 접근하는 메서드는 그 객체에 lock 을 건다.
    • lock 을 건 메서드는 객체의 상태를 확인하고 필요하면 수정한다.
  • 동기화의 중요한 기능
    • 일관성이 깨진 상태를 볼 수 없게 해주고
    • 동기화된 메서드나 블록에 들어간 스레드가 같은 락의 보호하에 수행된 모든 이전 수정의 최종 결과를 보게 해준다.
• 동기화는 배타적 실행뿐만 아니라, 스레드 사이의 안정적인 통신에 필요하다.
• 다른 스레드를 멈추는 올바른 방법
  • 첫 번째 스레드는 자신의 boolean 필드를 폴링하면서 값이 true가 되면 멈춘다.
  • 필드를 false로 초기화하고, 다른 스레드에서 이 스레드를 멈추려고 할 때 true 로 변경
• 적절한 스레드 종료 방법

public class StopThread {
    private static boolean stopRequested;
    
    private static synchronized void requeststop() { 
        stopRequested = true;
    }
    
    private static synchronized boolean stopRequested() { 
        return stopRequested;
    }
    
    public static void main(String[] args) 
        throws InterruptedException {
            Thread backgroundThread = new Thread(() -> { 
                int i = 0;
                while (!stopRequested()) 
                    i++;
            }); 
            backgroundThread.start();
            
            TimeUnit.SECONDS.sleep(1);
            requestStop();
    } 
}

private static volatile boolean stopRequested;

private static volatile int nextSeriaINumber = 0;

public static int generateSerialNumber() { 
        return nextSerialNumber++;
}

private void notifyElementAdded(E element) { 
    List<SetObserver<E>> snapshot = null; 
    synchronized(observers) {
      snapshot = new ArrayList<>(observers);
    }
    for (SetObserver<E> observer : snapshot)
        observer.added(this, element);
}

private final List<SetObserver<E>> observers = 
        new CopyOnWriteArrayList<>();
public void addObserver(SetObserver<E> observer) { 
    observers.add(observer);
}
public boolean removeObserver(SetObserver<E> observer) { 
    return observers.remove(observer);
}
private void notifyElementAdded(E element) { 
    for (SetObserver<E> observer : observers)
      observer.added(this, element);
}

ExecutorService exec = Executors.newSingleThreadExecutor();
exec.execute(runnable); // 실행자에 실행할 태스크를 넘기는 법
exec.shutdown(); // 실행자를 종료시키는 법

public static String intern(String s) { 
    String result = map.get(s);
    if (result = null) {
      result = map.putIfAbsent(s, s); 
      if (result = null)
        result = s;
    }
    return result; 
}

// synchronizedMap이 반환한 맵의 컬렉션 뷰를순회하려면 반드시 그 맵을 락으로 사용해 수동으로 동기화하라.

Map<K, V> m = Collections. synchronizedMap(new HashMapo()); 
Set<K> s = m.keySet(); // 동기화 블록 밖에 있어도 된다.
        ...
synchronized(m) { // s가 아닌 m을 사용해 동기화해야 한다! 
  for (K key : s)
    key.f();
}
// 이대로 따르지 않으면 동작을 예측할 수 없다.

private final FieldType field = computeFieldValue();
// 지연 초기화가 초기화 순환성(initialization circularity)을 깨뜨릴 것 같을 때 synchronized 접근자 사용하기

private FieldType field;
private synchronized FieldType getFieId() { 
    if (field = null)
        field = computeFieldValue(); 
    return field;
}

private static class FieldHolder {
static final FieldType field = compiiteFieldValue();
}
private static FieldType getFieId() { return FieldHolder.field; }

private volatile FieldType field;

private FieldType getFieId() {
        FieldType result = field;
        if (result != null) { // 첫 번째 검사 (락 사용 안 함)
            return result;
            
        synchronized(this) {
          if (field = null) // 두 번째 검사 (락 사용)
            field = computeFieldValue(); 
          return field;
        }
}

https://www.acmicpc.net/problem/1744

문제 풀이

- 수열이 주어질 때, 값 들을 곱해서 최대 합을 구하기

- 2가지 수를 묶거나 묶지 않을 수 있다.

- 양수값과 음수값을 따로 구해서 곱해준다.

N = int(input())  # 수열의 크기
plus = []
minus = []
res = 0

for _ in range(N):
    num = int(input())
    if num > 1:
        plus.append(num)
    elif num == 1:
        res += 1
    else:
        minus.append(num)

plus.sort(reverse=True)
minus.sort()
plus_size, minus_size = len(plus), len(minus)

if len(plus) % 2 == 0:  # 양수 + 짝수 개수
    for idx in range(0, plus_size, 2):
        res += plus[idx] * plus[idx + 1]
else:  # 양수 + 홀수 개수
    res += plus[plus_size - 1]  # 마지막 값
    for idx in range(0, plus_size - 1, 2):
        res += plus[idx] * plus[idx + 1]

if len(minus) % 2 == 0:  # 음수 + 짝수 개수
    for idx in range(0, minus_size, 2):
        res += minus[idx] * minus[idx + 1]
else:  # 음수 + 홀수 개수
    res += minus[minus_size - 1]  # 마지막 값
    for idx in range(0, minus_size - 1, 2):
        res += minus[idx] * minus[idx + 1]

print(res)

https://www.acmicpc.net/problem/2170

문제 풀이

- 두 가지 값이 주어지면 왼쪽에서 오른쪽으로 선을 그을 수 있다. 

- 중복되는 선은 제외하고 총 선의 길이를 구해준다.

- 선이 이어지는지 최대값과 비교하면서 확인한다.

- 다음 선으로 넘어가면서,  이전에 그었던 선의 (도착점의 최대위치-시작점의 최소 위치) 길이를 더해준다.

import sys

input = sys.stdin.readline
N = int(input())
lines = list(tuple(map(int, input().split())) for _ in range(N))
lines.sort()

left = lines[0][0]
right = lines[0][1]
total = 0

for idx in range(1, N):
    key, value = lines[idx]

    if key < right:
        right = max(value, right)
    else:
        total += right - left
        left, right = key, value

total += right - left
print(total)

https://www.acmicpc.net/problem/11501

문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

문제 풀이

- 주식 가격의 리스트를 맨 뒤에서부터 반복해서 최대 가격과 비교해가면서 계산

- 최대 가격과 현재 가격의 차익을 더해준다.

tc = int(input())

for _ in range(tc):
    day = int(input())
    cost_list = list(map(int, input().split()))

    total = 0
    max_value = 0
    for idx in range(day - 1, -1, -1):
        if cost_list[idx] > max_value:
            max_value = cost_list[idx]
        else:
            total += max_value - cost_list[idx]
    print(total)

https://www.acmicpc.net/problem/1541

문제

- 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

- 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

- 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

문제 풀이

- 최소 값으로 만들기 위해서는 '-' 값을 크게 만들어 주어야 한다.

- split으로 '-' 이 나오는 부분을 쪼개주고 뒤에 나오는 값들을 전부 합해준다.

num = input().split('-')
total = 0

for plus in num[0].split('+'):
    total += int(plus)

for minus in num[1:]:
    sub_sum = sum(map(int, minus.split('+')))
    total -= int(sub_sum)
print(total)