TIL 코딩공장

11/ 09 파이썬 공부
1. 백준 1362번 펫

1) 문제
당신은 게임으로 펫을 기르고 있습니다. 
이 펫은 웃는 표정, 슬픈 표정을 가지고 있으며, 만약 죽는다면 '드러눕습니다.'

펫에게는 적정 체중이 있습니다. 
펫의 실제 체중이 적정 체중의 1/2배를 초과하면서 적정 체중의 2배 미만이라면 펫은 행복합니다. 
펫의 실제 체중이 0 이하일 경우 펫은 사망하게 되며, 그 외의 경우 펫은 슬픕니다.

당신은 콘솔을 통해 펫에게 아래의 두 가지 작용을 할 수 있습니다.

(1) 'E'와 숫자를 입력해 펫을 운동시킬 수 있습니다. 
입력된 숫자(n)만큼의 시간(분; minute)이 지나면 펫의 실제 체중이 n 감소합니다.
(2) 'F'와 숫자를 입력해 펫에게 먹이를 줄 수 있습니다. 
입력된 숫자(n)만큼 펫에게 먹이를 주면 펫의 실제 체중이 n 증가합니다.

각 작용에 입력할 수 있는 숫자는 1 이상, 999 이하의 정수입니다. 
매 작용이 끝날 때마다 펫은 자신의 상태를 표시하며, 펫이 중간에 죽는다면 이후의 작용은 무시됩니다.

2) 입력
입력은 번호를 가진 시나리오들로 구성됩니다. 시나리오는 1번부터 시작되며 1씩 증가합니다.

적정 체중(o)와 실제 체중(w)가 한 줄에 입력됨으로써 시나리오가 시작됩니다(10 ≤ o, w ≤ 1000). 
그 다음 줄부터 펫에 가할 작용이 한 줄에 하나씩 주어지며, 
"# 0"을 마지막 줄로 하여 시나리오가 종료됩니다. 
"# 0"은 처리하지 않습니다.

펫에게 가할 각 작용은 'E' 또는 'F'로 시작하며, 공백을 두고 숫자 n (1 ≤ n ≤ 999)이 주어집니다.

모든 시나리오가 끝나면 "0 0"이 입력되며, "0 0"은 처리하지 않습니다.

3) 출력
각 시나리오에 대하여, 시나리오 번호와 모든 작용이 완료된 후 펫의 상태를 공백으로 구분하여 한 줄씩 출력합니다.

(1) 행복한 경우, ":-)"을 출력합니다.
(2) 슬픈 경우 ":-("을 출력합니다.
(3) 사망한 경우 "RIP"를 출력합니다.

>>>코드

i = 1 # 시나리오 번호
while True:
    o, w = map(float, input().split()) # 적정 체중과 실제 체중 입력받기
    if o == 0 and w == 0: # 0 0 일 경우 break
        break
    while True:
        a, n = input().split() # 작용과 숫자 입력 받기
        n = float(n)
        if a == 'E' and w > 0: # 개가 살아있으면서, 운동을 하는 경우
            w -= n
        elif a == 'F' and w > 0: # 개가 살아있으면서, 밥을 먹는 경우
            w += n
        elif a == '#' and n == 0: # # 0 인 경우 결과 출력후 break
            if w <= 0: # 행복한 경우, 시나리오 번호와 ":-)"을 출력
                print('%d RIP' %(i))
            elif w <= o/2 or w >= o*2: # 슬픈 경우 시나리오 번호와 ":-("을 출력
                print('%d :-(' %(i))
            else: # 행복한 경우, 시나리오 번호와 ":-)"을 출력
                print('%d :-)' %(i))
            i += 1
            break

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

11/ 08 파이썬 공부
1. 백준 1773번 폭죽 쇼

1) 문제
학생들은 3주가 지난 기념으로 매점에서 1월 1일이 지나 싸게 파는 폭죽을 사서 터뜨리고 있다.

폭죽쇼를 하는 동안 N명의 학생들이 폭죽을 터뜨린다. 
그리고 이 N명의 학생은 각각 일정한 주기로 폭죽을 터뜨린다. 
물론 이 주기는 학생들마다 같을 수도, 다를 수도 있다. 
그리고 우리는 초 단위로 관찰을 하고, 폭죽 역시 초 단위로 터진다.

폭죽쇼가 끝날 때까지 얼마나 많은 시간동안 밤하늘에 폭죽이 터지는 것을 볼 수 있는지 궁금해 하는 조교를 도와주자.

2) 입력
첫 줄에 폭죽을 터뜨리는 학생의 수 N(1 ≤ N ≤ 100)과 폭죽쇼가 끝나는 시간 C(1 ≤ C ≤ 2,000,000)가 주어진다. 그 다음 N개의 줄에는 학생들이 폭죽을 터뜨리는 주기가 한 줄에 하나씩 주어진다. 주기는 1보다 크거나 같고, C보다 작거나 같은 자연수이다.

3) 출력
폭죽쇼가 시작되고 끝날 때까지 밤하늘에 폭죽을 볼 수 있는 총 시간을 출력한다.

>>>코드

import sys
n, c = map(int, input().split()) # n, c 입력받기
l = [0] * (c+1) # 0으로 이루어진 c+1 길이의 리스트 생성
for i in range(n):
    p = int(sys.stdin.readline()) # 시간간격 p 입력받기
    t = p
    while t <= c: # p 간격마다 +1
        l[t] += 1
        t += p
print(c+1-l.count(0)) # 리스트 길이에서 0으로 남아있는 요소들의 개수(폭죽 안터진 시간)만 빼기

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

11/ 07 파이썬 공부
1. 백준 10773번 제로

1) 문제
나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 
애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

2) 입력
첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 
정수는 0에서 1,000,000 사이의 값을 가지며, 
정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

3) 출력
재민이가 최종적으로 적어 낸 수의 합을 출력한다. 
최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.

>>>코드: 덱 이용

import sys
from collections import deque
k = int(input())
d = deque()
for i in range(k):
    n = int(sys.stdin.readline()) # 숫자 n 입력받기
    if n == 0: # n이 0이면 마지막으로 입력 받았던 수 삭제
        d.pop()
    else: # n이 0이 아니면 덱에 추가
        d.append(n)
print(sum(d)) # 덱의 총합 출력

import sys를 사용하지 않으면 상당히 느리다.

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

11/ 06 파이썬 공부
1. 백준 2164번 카드2

1) 문제
N장의 카드가 있다. 
각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 
1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 
우선, 제일 위에 있는 카드를 바닥에 버린다. 
그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 
1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 
3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 
마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

3) 출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.

>>>코드

from collections import deque
n = int(input())
d = deque([i for i in range(1, n+1)])
while len(d) != 1:
    d.popleft()
    d.append(d.popleft())
print(d[0])

덱을 사용하면 간단하다.

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

11/ 05 파이썬 공부
1. 백준 11866번 요세푸스 문제 0

1) 문제
요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 
이제 순서대로 K번째 사람을 제거한다. 
한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 
이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 
예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

3) 출력
예제와 같이 요세푸스 순열을 출력한다.

>>>코드1: 리스트만 이용하기

n, k = map(int, input().split()) # n, k 입력받기
l = list(i for i in range(1, n+1)) # 1~n 까지의 숫자로 이루어진 리스트 생성
result = [] # 최종 순서를 기록할 리스트
while l:
    for i in range(k-1):
        l.append(l[0]) # k만큼 앞의 숫자를 뒤에 저장
        del l[0] # 맨 앞 숫자 삭제
    result.append(l[0]) # 결과 저장
    del l[0] # 맨 앞 숫자 삭제
print('<', end = '') # 출력 기준에 맞게 출력
for i in range(len(result)-1):
    print(result[i], end = ', ')
print(result[-1], end = '')
print('>')

n, k 를 입력받아 리스트를 만들고, 

맨 앞의 요소를 뒤로 보내면서 해당 순서의 숫자를 새 리스트에 저장했으나 조금 복잡해 보였다.

그래서 찾아보니 전에 배운 덱을 파이썬에서 사용할수 있는 모듈이 있었다.

>>>코드 2: from collections import deque 이용하기

from collections import deque
n, k = map(int, input().split()) # n, k 입력받기
d = deque([i for i in range(1, n+1)]) # 1~n 까지의 숫자로 이루어진 덱 생성
result = [] # 최종 순서를 기록할 리스트
while d:
    for i in range(k-1):
        d.append(d.popleft()) # k만큼 앞의 숫자를 뒤에 저장 및 맨 앞 숫자 삭제
    result.append(d.popleft()) # 결과 저장 및 맨 앞 숫자 삭제
print('<', end = '') # 출력 기준에 맞게 출력
for i in range(len(result)-1):
    print(result[i], end = ', ')
print(result[-1], end = '')
print('>')

큰 틀은 비슷한데 속도는 빨라진 모습을 확인할 수 있다.

>>> 코드 설명: from collections import deque
덱을 파이썬에서 사용할 수 있는 모듈이다.

1) 덱 만들기
d = deque(덱에 들어갈 요소)

2) 스택 구현
- d.append(): 마지막(오른쪽 끝)에 요소 저장
- d.pop(): 마지막 요소 삭제

3) 큐 구현
- d.appendleft(): 처음(왼쪽 끝)에 요소 저장
- d.popleft(): 처음 요소 삭제

4) 덱 확장
- d.extend(): 오른쪽으로 덱 확장, 마지막에 요소들 추가
- d.extendleft(): 왼쪽으로 덱 확장, 처음에 요소들 추가

5) 리스트 처럼 사용
- d.remove(): 특정 요소 삭제 (중복시 인덱스가 가장 작은 것 하나만 삭제)
- d.insert(인덱스, 요소): 입력한 인덱스에 요소 추가

6) 덱 반전
- d.reverse(): 순서 반대로 만들기

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

11/ 04 파이썬 공부
1. 백준 11650번 좌표 정렬하기

1) 문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

2) 입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 
좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

3) 출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

>>>코드

import sys
l = [] # 입력 받을 리스트 생성
for _ in range(int(input())):
    a, b = map(int, sys.stdin.readline().split()) # x, y좌표 입력 받기
    l.append([a, b]) # 2차원 리스트로 x좌표와 y좌표 짝을 저장
result = sorted(l, key = lambda l: (l[0], l[1])) # lambda 함수로 x좌표(l[0]), y좌표(l[1])를 차례로 기준으로 해서 정렬하기
for i in range(len(result)):
    print(result[i][0], result[i][1]) # 정렬된 리스트 출력

sorted 함수와 key = lambda 함수를 잘 사용하면 쉬운 문제이다.

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

11/ 03 파이썬 공부
1. 백준 9012번 괄호

1) 문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 
그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 
한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 
만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 
그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 
예를 들어 “(())()”와 “((()))” 는 VPS 이지만 
“(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

2) 입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 
입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 
각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 
하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

3) 출력
출력은 표준 출력을 사용한다. 
만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 
아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

>>>코드

# 반복 횟수 입력받기
for _ in range(int(input())):
    l = input() # 괄호 입력받기
    stack = [] # 괄호 검사할 스택 만들기
    t = 0 # 테스트 수 t
    for i in l:
        if i == '(':
            stack.append('(') # 만약 여는 괄호면 스택에 추가
        elif i == ')' and stack:
            stack.pop() # 닫는 괄호면서 스택에 짝이 존재하면 스택에서 여는 괄호 제거
        else:
            t = 1
            break # 만약 닫는 괄호면서 스택이 비었으면 테스트 수 변경 후 break
    if not stack and t == 0:
        print('YES') # 테스트 수도 0이면서 괄호의 짝이 다 맞아 steak이 비어있으면 YES
    else:
        print('NO') # 아니면 NO

전에 배운 스택을 이용하는 방법이다.
스택을 이용하여 짝을 검사. 

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

11/ 02 파이썬 공부
1. 백준 10866번 덱

1) 문제
정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.

- push_front X: 정수 X를 덱의 앞에 넣는다.
- push_back X: 정수 X를 덱의 뒤에 넣는다.
- pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 덱에 들어있는 정수의 개수를 출력한다.
- empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
- front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

2) 입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 
둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

3) 출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

>>>코드

import sys

deque = []
for _ in range(int(sys.stdin.readline())):
    command = sys.stdin.readline().split()
    if command[0] == 'push_front':
        deque = [command[1]] + deque
    elif command[0] == 'push_back':
        deque.append(command[1])
    elif command[0] == 'pop_front':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque[0])
            del deque[0]
    elif command[0] == 'pop_back':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque[-1])
            del deque[-1]
    elif command[0] == 'size':
        print(len(deque))
    elif command[0] == 'empty':
        if len(deque) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == 'front':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque[0])
    elif command[0] == 'back':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque[-1])

- 덱 (큐와 스택을 합친 형태)
덱(deque, "deck"과 발음이 같음 ← double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.
두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 
큐와 스택을 합친 형태로 생각할 수 있다.

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