Coding 공부

from collections import deque
import bisect
import sys
input = sys.stdin.readline
T = int(input())

for _ in range(T):
    stack = deque()
    stack_dict = dict()
    for _ in range(int(input())):
        command,val = input().split()
        val = int(val)
        if command == 'I':
            if stack_dict.get(val):
                stack_dict[val] += 1
            else:
                bisect.insort_left(stack,val)
                stack_dict[val] = 1
        else:
            if val == 1:
                if stack:
                    last_number = stack[-1]
                    if stack_dict[last_number] == 1:
                        stack_dict.pop(last_number)
                        stack.pop()
                    else: 
                        stack_dict[last_number] -= 1
            else:
                if stack:
                    first_number = stack[0]
                    if stack_dict[first_number] == 1:
                        stack_dict.pop(first_number)
                        stack.popleft()
                    else:
                        stack_dict[first_number] -= 1
    if stack:
        print(stack[-1],stack[0])
    else:
        print('EMPTY')

정렬된 행렬일때 쓸 수 있는 bisect 라이브러리를 이용해서, 이진탐색 후, deque에 넣어주었다.

뺄때 매번 insert, pop을 하면 연산시간이 오래걸리므로, dictionary로 개수를 세주었고, dictionary가 0이 될때 pop을 해주었다.

number_list = [True]*1003002
number_list[0] = False
number_list[1] = False
for number in range(2,1003002):
    if number_list[number]:
        for j in range(number+number,1003002,number):
            number_list[j] = False

N = int(input())
flag = False
for find_number in range(N,1003002):
    if number_list[find_number]:
        string_number = str(find_number)
        if len(string_number)%2:
            if len(string_number) != 1:
                a = string_number[:N//2]
                b = string_number[N//2+1::-1]
                if a == b:
                    result = find_number
                    break
            else:
                result = find_number
                break
        else:
            a = string_number[:N//2]
            b = string_number[N//2::-1]
            if a == b:
                result = find_number
                break
    

print(result)

소수를 구한뒤 앞뒤로 같은지 확인해주면 되는 문제였다.

그리고 최대 입력값 100만일때 나오는 소수& 팰린드롬 수는 1003001 이므로 거기까지만 돌리면 된다.

import math
a=input()
k={}
for i in range(10):
    k[i]=0
for j in a:
    j=int(j)
    k[j]+=1
result1=0
result2=0
for index,value in k.items():
    if index==6 or index==9:
        result2=k[9]+k[6]
    else:
        if result1<value:
            result1=value
            

result2=math.ceil(result2/2)
if result2>result1:
    print(result2)
else:
    print(result1)

간단한 문제이다. 6,9일때와 아닐때를 구분해서 개수를 세준뒤에 둘중 큰걸 출력해주면 된다.

N = input()
room_number = [0]*10

for number in N:
    room_number[int(number)] += 1
a = room_number[6]+room_number[9]
b = (room_number[6]+room_number[9])//2
room_number[6],room_number[9] = b,a-b

print(max(room_number))

이런식으로 구현해도 된다.

a= int(input())
def cal(a):
    temp = []
    for i in a:
        temp.append(i-1)
        if i%3==0:
            temp.append(i/3)
        if i%2==0:
            temp.append(i/2)
    return temp
cnt=0
minimum=[a]
while True:
    if a==1:
        print(cnt)
        break
    temp=minimum[:]
    minimum=[]
    minimum=cal(temp)
    cnt+=1
    if min(minimum)==1:
        print(cnt)
        break

유명한 DP 문제이다.

각각의 연산을 한뒤에 새롭게 옮겨가는 LIST를 따로 만들어주고, 그걸 갱신하면서 횟수가 어느회차인지 알면된다.

N = int(input())
number_list = [N]
cnt = 0
flag = False
if N == 1:
    print(0)
else:
    while True:
        new_number = []
        for numbers in number_list:
            if numbers == 1:
                flag = True
                break

            if not numbers%3:
                new_number.append(numbers/3)
            if not numbers%2:
                new_number.append(numbers/2)
            new_number.append(numbers-1)
        if flag:
            print(cnt)
            break
        cnt += 1
        number_list = new_number[:]

똑같은데 이런식으로도 만들수 있다.

print(''.join(sorted(input())[::-1]))

정렬을 해준뒤 역으로 출력해준다.

T=int(input())
cnt=0
for test_case in range(T):
    sp=list(input())
    total=[]
    for i,v in enumerate(sp):
        if i!=len(sp)-1:
            if sp[i]!=sp[i+1]:
                total.append(sp[i])
        else:
            total.append(sp[i])
    for k in total:
        if total.count(k)>1:
            break
    else:
        cnt=cnt+1
print(cnt)

풀이 방식은 다음과 같다.

 마지막 위치를 제외한 현재위치와 다음위치를 비교를 해서 같지 않을때에 그때 현재위치의 문자열을 total에 넣어준다.

마지막 위치는 total에 넣어준다.

그리고 난뒤에 total을 반복문을 돌리면서 그 개수가 1개를 초과하면, 그룹 단어가 아니므로 멈춰주고, 한번도 만나지 않으면, 그룹 단어이므로 cnt를 늘려준다.

from collections import deque


def dfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    stack = [V - 1]
    
    while stack:
        x = stack.pop()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N - 1, -1, -1):
            if graph[x][k] >= 1:
                graph[x][k] = 0
                graph[k][x] = 0
                stack.append(k)
    
    return result


def bfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    q = deque()
    q.append(V - 1)

    while q:
        x = q.popleft()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N):
            if graph[x][k] >= 1:
                graph[x][k] -= 1
                graph[k][x] -= 1
                
                q.append(k)
    
    return result



N, M, V = map(int, input().split())
arr = [list(map(int ,input().split())) for _ in range(M)]

dfs_res = dfs()
for i in range(len(dfs_res)):
    print(dfs_res[i], end=" ")
print()
bfs_res = bfs()
for i in range(len(bfs_res)):
    print(bfs_res[i], end=" ")
print()

DFS와 BFS 문제이다.

웹개발 중 코테 대비하면서 연습용으로 오랜만에 풀었던 문제라, 코드가 별로이다.

def solution(start,flag):
    global N
    stack = [start]
    visited = [True]*(N+1)
    ind = 0
    if flag:
        ind = -1
    result = []
    while stack:
        node_number = stack.pop(ind)
        if not visited[node_number]:
            continue
        visited[node_number] = False
        result.append(node_number)
        for next_node in sorted(graph[node_number],reverse=flag):
            if visited[next_node]:
                stack.append(next_node)
    return result




N,M,V = map(int,input().split())


graph = [[] for _ in range(N+1)]

for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)



print(*solution(V,True))
print(*solution(V,False))

 기본적인 풀이는 같다. DFS이냐, BFS이냐에 따라 트리거를 주었고, DFS일때는 pop하는 index를 -1로 아니면 0으로 주었다.

그리고 dfs는 뒤에서부터 pop이 되므로, graph를 내림차순으로 정렬해주고, bfs는 오름차순으로 정렬해주는것만 다르다.

N,K=map(int,input().split(' '))
result=[]
temp=K-1
first=list(range(1,N+1))
for i in range(N):
    if temp < len(first):
        result.append(first.pop(temp))
        temp+=K-1
    else:
        temp=temp%len(first)
        result.append(first.pop(temp))
        temp+=K-1
print('<',end='')
for k in result:
    if k==result[-1]:
        print(k,end='')
    else:
        print(k,end=', ')
print('>')

요세푸스 문제이다.

과거에 푼 문제라 정확한 풀이가 기억은 안나지만, 풀이 자체는 단순하게, K를 계속 옮겨가면서 풀었던 기억이 난다.

from collections import deque

N,K = map(int,input().split())

stack = deque(range(1,N+1))
result = []
while stack:
    stack.rotate(-(K-1))
    result.append(str(stack.popleft()))
print(f'<{", ".join(result)}>')
    

지금 푼다면 이렇게 풀 것이다.

단순하게 큐를 만들고 rotate로 회전을 시킨 뒤, 가장 좌측에 있는걸 뺄것이다.