say repository

코드 1

import sys
t = int(sys.stdin.readline())
#스택
for i in range(t):
    string = sys.stdin.readline().rstrip()
    string += " "

    stack = []
    for j in string:
        if j != " ":
            stack.append(j)
        else:
            while stack:
                print(stack.pop(),end = "")
            print(' ',end="")

풀이 1

문자열을 넣고 거꾸로 출력을 하니까 스택 자료구조로 구현했다.

문자열을 스택에 넣고 " "을 만나면 pop() 한다.

주의할 점은 마지막 문자열 끝에 " "가 안 들어가니까 뒤집기가 안된다. 

그래서 마지막 문자열에도 " "을 넣어준다.

코드 2

import sys
t = int(sys.stdin.readline())

#문자열 슬라이싱
for i in range(t):
    string = sys.stdin.readline().rstrip().split()
    for str in string:
        print(str[::-1],end=" ")
    print()

풀이 2

python은 문자열을 다루기 좋은 언어이다.

python의 장점을 활용해 " "마다 잘라서 str[::-1] 을 사용해 뒤집어줬다.

import sys
t = int(sys.stdin.readline())
def sol(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return sol(n-3) + sol(n-2) + sol(n-1)

for i in range(t):
    n = int(sys.stdin.readline())
    print(sol(n))

풀이

n이

1 일 때 1 -> 총 1가지

2일 때 1+1, 2 -> 총 2가지

3일 때 1+1+1, 1+2, 2+1, 3 -> 총 4가지

4일 때 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 1+3, 3+1, 2+2 -> 총 7가지

5일 때 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+1+3, 1+3+1, 3+1+1, 2+3, 3+2, 2+2+1, 2+1+2, 1+2+2 -> 총 13가지

...

이렇게 구해보면 규칙을 찾을 수 있다.

점화식을 세워 구하면 된다.

f(n) = f(n-3) + f(n-2) + f(n-1) (단, n>3)

import sys
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

def dfs(idx,sum):
    global cnt
    if idx>=n:
        return
    sum += arr[idx]
    if sum == s:
        cnt+=1
    dfs(idx+1, sum)
    dfs(idx+1, sum-arr[idx])

cnt = 0
dfs(0,0)
print(cnt)

풀이 1

백트래킹으로 구현했다. 

완전탐색을 하면서 불필요한 탐색은 가지치기하는 방법이다.

dfs을 하면서

1. 현재 arr [idx] 을 포함하는 경우

2. 현재 arr [idx] 을 포함하지 않는 경우

경우의 수를 가지치기 한다.

코드 2

import sys
from itertools import combinations
n, s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))

#조합
cnt = 0
for i in range(1,n+1):
    comb = list(combinations(arr,i))
    for j in comb:
        if sum(j) == s:
            cnt+=1

print(cnt)

풀이 2

조합을 사용해서 크기가 1부터 n까지의 부분수열을 만들고 그 합이 s일 때 cnt+=1 한다.

import sys
import math

arr = [True for _ in range(1000001)]
for i in range(2,int(math.sqrt(1000001))):
    if arr[i]:
        j = 2
        while i*j<1000001:
            arr[i*j] = 0
            j+=1

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break

    flag = 0
    for i in range(3,len(arr)):
        if arr[i]:
            if arr[n-i]:
                print(n, "=", i, "+", n-i)
                flag = 1
                break
    if flag == 0:
        print("Goldbach's conjecture is wrong.")

주워진 범위 내의 모든 소수를 구할 때는 에라토스테네스의 체 알고리즘을 사용해야 효율적이다.

하지만, 처음에 arr의 크기를 1000001 로 주지 않고 입력받은 값으로 계속 반복문을 돌아서 시간 초과가 났다..

입력값의 조건 중 테스트 케이스의 개수는 100000개를 넘지 않는다고 쓰여 있다.

이 조건을 활용해 에라토스테네스의 체로 구현하면 시간 초과를 겪지 않는다.

import sys
from collections import deque
t = int(sys.stdin.readline())

for i in range(t):
    p = list(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline())
    arr = sys.stdin.readline()[1:-2].rstrip().split(",")

    if n ==0:
        q = deque()
    else:
        q = deque(arr)

    rev = 0
    flag = 0 #error 인지 확인

    for j in p:
        if j=="R":
            rev+=1
        elif j== "D":
            if len(q)==0:
                print("error")
                flag = 1
                break
            else:
                if rev % 2 ==0:
                    q.popleft()
                else:
                    q.pop()
    if flag == 0:
        if rev % 2 ==0:
            print("["+",".join(q)+"]")
        else:
            q.reverse()
            print("[" + ",".join(q) + "]")

풀이 1

입력을 [1,2,3,4] 이렇게 받으니, 아래와 같이 슬라이싱 해서 입력받아야 한다.

arr = sys.stdin.readline()[1:-2].rstrip().split(",")

reverse() 연산과 popleft() 연산이 필요한 것을 보아 deque 라이브러리를 사용해서 덱을 구현했다.

하지만 R이 나올 때마다, reverse()연산을 했더니 시간 초과가 났다.

생각을 더 해보면, R은 짝수이면 뒤집기를 안한 것 과 같아서 홀수 일 때만 뒤집으면 된다.

또한, R이 짝수 이면 뒤집기를 안한 것과 같으니 맨 처음의 원소를 삭제하는 popleft() 연산을 하면 되고, 

R이 홀수 이면 맨 뒤에 원소를 삭제하는 것과 같아서 pop()연산을 한다.

flag 변수는 error 임을 체크하는 변수로 쓰였고 최종적으로 R이 홀수 일 때만 출력 전에 reverse() 연산을 해준다.

코드 2

import sys

t = int(sys.stdin.readline())

for i in range(t):
    p = sys.stdin.readline().rstrip()
    n = int(sys.stdin.readline())
    arr = sys.stdin.readline()[1:-2].rstrip().split(",")
    p = p.replace("RR","")

    rev = 0
    f,b = 0,0
    flag = 0 #error 인지 확인

    for j in p:
        if j=="R":
            rev+=1
        elif j== "D":
            if rev % 2 ==0:
                f+=1
            else:
                b+=1
    if f+b <= n:
        arr = arr[f:n-b]
        if rev % 2 ==0:
            print("["+",".join(arr)+"]")
        else:
            print("[" + ",".join(arr[::-1]) + "]")
    else:
        print("error")

풀이 2

덱 라이브러리를 사용하지 않고 문자열 슬라이싱으로 풀이하는 방법이다.

우선, 풀이1의 방법과 비슷한 점이 있다.

R이 짝수면 앞에서부터 제거 (f+=1 표시)

R이 홀수면 뒤에서부터 제거 (b+=1 표시)

그리고 RR이 연속해 있으면 ""으로 교체해 제거한다.

f+b의 합이 n보다 크면 error 출력하고

이하이면 문자열을 f부터 n-b까지 저장하고 reverse 연산을 한다.

python에서는 리스트를 뒤집는 방법이 reverse()연산 말고도

list[::-1] 방법이 있다.

import math
import sys
n = int(sys.stdin.readline())
tree = []
bet_tree = []
result = 0

#가로수 저장
for i in range(n):
    tree.append(int(sys.stdin.readline().rstrip()))
#가로수 간격 저장
for i in range(n-1):
    bet_tree.append(tree[i+1]-tree[i])

#가로수 간격의 최대공약수 찾기
gcd = bet_tree[0]
for i in range(1,len(bet_tree)):
    gcd = math.gcd(gcd,bet_tree[i])

#가로수 간격 //최대공약수 -1 의 합이 답
for i in range(len(bet_tree)):
    result += bet_tree[i] // gcd -1
print(result)

import sys
T = int(sys.stdin.readline())
for i in range(T):
    n,m = map(int,sys.stdin.readline().split())
    q = list(map(int,sys.stdin.readline().split()))
    check = [0 for _ in range(n)]
    check[m] = 1
    cnt = 0

    while True:
        if q[0] == max(q):
            cnt+=1
            if check[0] != 1:
                del q[0]
                del check[0]
            else:
                print(cnt)
                break
        else:
            q.append(q[0])
            check.append(check[0])
            del q[0]
            del check[0]

풀이

필요한 것 

1) 우선순위 저장

2) 인덱스 저장

3) 찾아야 하는 인덱스 저장

4) 정답 cnt

리스트를 내림차순으로 정렬하는 과정에서 맨 처음 원소가 max값이면 cnt+=1 을 하고 리스트에서 꺼낸다. 

그 다음 max 값을 cnt+=1 하고 또 꺼낸다.

이 때, 원소 값을 꺼낼 때 인덱스를 체크하는 값도 같이 꺼낸다.

인덱스를 체크할 때, 찾고자 하는 인덱스면 끝낸다.