say repository

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 하고 또 꺼낸다.

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

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

import sys
n,k = map(int,sys.stdin.readline().split())
q=[]
result = []
for i in range(1,n+1):
    q.append(i)

index = 0
while q:
    index += k-1
    if index >= len(q):
        index = index % len(q)

    result.append(q.pop(index))

print("<", ', '.join(str(i) for i in result),">",sep="")

풀이

index 는 삭제할 인덱스이고 계속 k만큼 더해주는데 배열의 인덱스이니까 k-1을 더해준다.

삭제할 인덱스가 큐 한바퀴를 돌면, 원 모양이니까 다시 인덱스가 돌아가야한다.

index = index % len(q)

이렇게 하면 돌아갈 수 있다.

마지막 출력은 join()함수를 써서 깔끔하게 작성한다.

', '.join(i for i in result)로 하면 result에 있는 i는 정수여서 str로 바꿔서 join해야한다.

이 때, "<", ">"를 쉼표로 같이 이어붙이면 공백이 발생한다.

정답은 공백을 제거해야하니까 sep = ""로 제거해준다.

import sys
n = int(sys.stdin.readline())
stack = []
op = []
now = 1
possible = 1
for i in range(n):
    num = int(sys.stdin.readline())
    while now <= num:
        stack.append(now)
        op.append('+')
        now+=1

    if stack[-1] == num:
        stack.pop()
        op.append('-')
    else:
        possible = 0
if possible ==0:
    print("NO")
else:
    for i in op:
        print(i)

풀이

push()를 1부터 n까지 오름차순으로 해야한다.

그럼 입력값이 pop() 이 가능할 때까지 1부터 스택에 append() 해준다.

입력값이 pop()가능하면 pop()하고

불가능하면 NO 출력한다.

코드1

import math
import sys
a,b = map(int,sys.stdin.readline().split())
print(math.gcd(a,b))
print(math.lcm(a,b))

풀이

python의 math라이브러리는

최대공약수 math.gcd(a,b) 와

최소공배수 math.lcm(a,b)를 제공한다.

코드2

import math
import sys
a,b = map(int,sys.stdin.readline().split())

def GCD(a,b):
    while b>0:
        a,b = b, a%b
    return a
    
def LCM(a,b):
    return int(a*b / GCD(a,b))
    
print(GCD(a,b))
print(LCM(a,b))

풀이

유클리드 호제법

최대공약수

a,b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

최소공배수는

a,b를 곱한 값을 a,b의 최대공약수로 나눈 값이 최소공배수이다.

외워잉

import sys
import math
n, m = map(int,sys.stdin.readline().split())
arr = [True for i in range(m+1)]
for i in range(2,int(math.sqrt(m))+1):
    if arr[i]==True:
        j=2
        while i*j <= m:
            arr[i*j] = False
            j+=1
for i in range(n,m+1):
    if i>1 and arr[i]:
        print(i)

데이터가 1,000,000 개 이하에서 여러 소수를 구하는 문제는 에라토스테네스의 체 알고리즘을 사용한다.

구해야하는 크기만큼의 True 배열을 만든다.

2부터 구해야하는 크기의 제곱근까지의 자기자신을 제외한 배수를 모두 False을 만든다.

2부터 2를 제외하고 4, 6, 8, 10... False

3부터 3을 제외하고 3, 6, 9, 12 ... False

...

이렇게 하고 True 인 것만 출력하면 소수만 나온다.

마지막에 출력 시, i는 2부터임을 주의하자.