GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

문제 풀이

from math import gcd
import sys


'''
GCD = 최대 공약수
'''
t = int(sys.stdin.readline())

ans = [] 
for i in range(0,t):
    num = list(map(int, sys.stdin.readline().split()))
    n = num[0]
    num.pop(0)
    total = 0
    for j in range(0,n):
        for k in range(j+1, n): 
            total += gcd(num[j], num[k])
    ans.append(total)

for j in ans:
    print(j)

국영수

문제

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

문제 풀이

import sys


N = int(sys.stdin.readline())
ans = []
for i in range(0,N):
    name, kor, eng, math =map(str, sys.stdin.readline().split())
    ans.append([name, int(kor), int(eng), int(math)])

ans = sorted(ans, key=lambda x: (-x[1], x[2], -x[3], x[0]))
for i in ans:
    print(i[0])

문제에서 주어진 정렬 기준 순서대로 (-x[1], x[2], -x[3], x[0]) 로 작성한다. -가 붙으면 역순서로 정렬이 가능하다.

연결 요소의 개수

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

문제 풀이

import sys


sys.setrecursionlimit(10 ** 6)
# python은 재귀호출 횟수가 1,000회로 제한되어있어서 제한을 늘려준다

N , M = map(int ,sys.stdin.readline().split())
uv = [[False] * (N+1) for _ in range(N+1)]

for i in range(M):
    u, v = map(int, sys.stdin.readline().split())
    uv[u][v] = True
    uv[v][u] = True

ans = 0
chk = [False] * (N+1)

def dfs(i):
    for j in range(1, N+1):
        if uv[i][j] and not chk[j]:
            chk[j] = True
            dfs(j)

for i in range(1, N+1):
    if not chk[i]:
        ans += 1
        chk[i] = True
        dfs(i)

print(ans)

'''
무방향 그래프 = 양방향 그래프
a->b , b->a 가 가능하다

'''

수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

문제 풀이

import sys
from bisect import bisect_left, bisect_right


M = int(sys.stdin.readline())
num = sorted(list(map(int, sys.stdin.readline().split())))

M2 = int(sys.stdin.readline())
num_2 = list(map(int, sys.stdin.readline().split()))

ans = [0] * M2
for i in range(0,M2):
    a = bisect_left(num,num_2[i])
    b = bisect_right(num,num_2[i])
    if abs(a-b) != 0:
        ans[i] = 1

for j in ans:
    print(j)

암호제작

문제

원룡이는 한 컴퓨터 보안 회사에서 일을 하고 있다. 그러던 도중, 원룡이는 YESWOA.COM 으로부터 홈페이지 유저들의 비밀키를 만들라는 지시를 받았다. 원룡이는 비밀 키를 다음과 같은 방법으로 만들었다.

개인마다 어떤 특정한 소수 p와 q를 주어 두 소수의 곱 pq를 비밀 키로 두었다. 이렇게 해 주면 두 소수 p,q를 알지 못하는 이상, 비밀 키를 알 수 없다는 장점을 가지고 있다.

하지만 원룡이는 한 가지 사실을 잊고 말았다. 최근 컴퓨터 기술이 발달함에 따라, 소수가 작은 경우에는 컴퓨터로 모든 경우의 수를 돌려보아 비밀 키를 쉽게 알 수 있다는 것이다.

원룡이는 주성조교님께 비밀 키를 제출하려던 바로 직전에 이 사실을 알아냈다. 그래서 두 소수 p, q 중 하나라도 K보다 작은 암호는 좋지 않은 암호로 간주하여 제출하지 않기로 하였다. 이것을 손으로 직접 구해보는 일은 매우 힘들 것이다. 당신은 원룡이를 도와 두 소수의 곱으로 이루어진 암호와 K가 주어져 있을 때, 그 암호가 좋은 암호인지 좋지 않은 암호인지 구하는 프로그램을 작성하여야 한다.

입력

암호 P(4 ≤ P ≤ 10100)와 K (2 ≤ K ≤ 106) 이 주어진다.

출력

만약에 그 암호가 좋은 암호이면 첫째 줄에 GOOD을 출력하고, 만약에 좋지 않은 암호이면 BAD와 소수 r을 공백으로 구분하여 출력하는데 r은 암호를 이루는 두 소수 중 작은 소수를 의미한다.

문제 풀이

import sys

P,K = map(int, sys.stdin.readline().split())
# --- 시간 초과 발생 ---
# ans = []
# for i in range(2,int(P ** 0.5)+1): # 2부터 P의 제급근까지의 숫자에서 소수 찾기
#     if P % i ==0 :
#         ans.append(i)


# if max(ans) <= K:
#     print("BAD", min(ans))
# else:
#     print("GOOD")

a = [False, False] + [True] * (K - 2)
for i in range(2, int(K ** 0.5) + 1):
    if a[i]:
        for j in range(i * 2, K, i):
            if a[j]:
                a[j] = False
flag = True
for i in range(2, K):
    if a[i]:
        if P % i == 0:
            flag = False
            break

if flag:
    print("GOOD")
else:
    print("BAD", i)

'''
에라토스체테네스의 체를 사용
소수 출력은 K보다 작은 소수일때만
K보다 작은 소수들의 집합을 구한후 그 집합을 P와 나눠가며 나누어 떨어지는 최소의 수를 출력
떨어지지 않는다면 Good 출력
'''

숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

문제 풀이

배열을 하나씩 다 비교해보려고 했는데 시간초과가 발생했다. 이럴때 쓰는게 이분탐색이라고

# -----------------------------------------------------------------
# 이분탐색
# from bisect import bisect_left, bisect_right
# a = [2,3,6,6,6,10,12,15]
# l = bisect_left(a,6)
# print(l)
# r = bisect_right(a,6)
# print(r)
# # right - left 하면 배열에 목표 값이 몇 개가 있는지 알 수 있음.
# -----------------------------------------------------------------
import sys
from bisect import bisect_left, bisect_right

N = int(sys.stdin.readline())
n_list = sorted(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

ans = []
for i in m_list:
    l = bisect_left(n_list, i)
    r = bisect_right(n_list, i)
    ans.append(r-l)

print(' '.join(map(str,ans)))

덱

문제

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

명령은 총 여덟 가지이다.

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

입력

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

출력

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

문제 풀이

import sys
from collections import deque


N = int(sys.stdin.readline())
dq = deque()

for i in range(0,N):
    order = list(map(str, sys.stdin.readline().split()))

    if order[0] == "push_front":
        dq.appendleft(order[1])
    elif order[0] == "push_back":
        dq.append(order[1])
    elif order[0] == "pop_front":
        if dq : # dq 가 있다면,
            print(dq.popleft())
        else:
            print(-1)
    elif order[0] == "pop_back":
        if dq : # dq 가 있다면,
            print(dq.pop())
        else:
            print(-1)
    elif order[0] == "size":
        print(len(dq))
    elif order[0] == "empty":
        if dq : # dq가 있다면,
            print(0)
        else:
            print(1)
    elif order[0] == "front":
        if dq :
            print(dq[0])
        else:
            print(-1)
    else : # back
        if dq :
            print(dq[-1])
        else:
            print(-1)

백설 공주와 일곱 난쟁이

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

문제 풀이

from itertools import combinations
import sys

num =[]
for i in range(0,9):
    num.append(int(sys.stdin.readline()))

for j in combinations(num, 7):
    if sum(j) == 100:
        for k in j:
            print(k)
        break

조합(combination) 문제 다루기 n개의 수 중에서 r개를 뽑는 가지 수 = nCr

from itertools import combinations

arr = [0,1,2,3]
for i in combinations(arr,2):
    print(i)

키로거

문제

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

문제 풀이

import sys

L = int(sys.stdin.readline())
ans =[]
for i in range(0,L):
    left =[]
    right =[]
    for j in str(sys.stdin.readline().rstrip()):
        if j == "<":
            if left:
                # left라는 배열이 비어있지 않다면,
                right.append(left.pop())
        elif j == ">":
            if right:
                # right가 비어있지 않다면,
                left.append(right.pop())
        elif j == "-":
            if left:
                left.pop()
        else: # 그냥 문자열일때,
            left.append(j)

    ans.append(''.join(left)+''.join(reversed(right)))
    # right에 대해서 reversed를 하는 이유는
    # 스택은 filo = 먼저들어간게 나중에 나오기때문에 
    # right 는 역순으로 출력한다.

for k in ans:
    print(k)

회사에 있는 사람

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

예제 입력 1

4 Baha enter Askar enter Baha leave Artem enter

예제 출력 1

Askar Artem

문제 풀이

import sys

n = int(sys.stdin.readline())
log = set()
for i in range(0,n):
    name, stay = map(str, sys.stdin.readline().split())
    if stay == "enter":
        log.add(name)
    else:
        if name in log :
            # log에 name이 있다는 가정
            log.remove(name)

log = sorted(log, reverse=True)
for j in log:
    print(j)

시도했지만 정답이 아닌 풀이 비슷하게 배열로 접근해보았지만 시간초과가 발생했다.

# 1. 시간초과
# import sys

# n = int(sys.stdin.readline())

# log = []
# for i in range(0,n):
#     name, stay = map(str, sys.stdin.readline().split())
#     if not(name in log):
#         # log에 들어가있지 않으면 
#         if stay == "enter":
#             log.append(name)
#         else:
#             pass
#     else:
#         # log에 들어가있고, 상태가 stay 라면
#         if stay == "leave":
#             log.remove(name)

# log = sorted(log, reverse=True) # 현재 회사에 있는 사람의 이름을 사전순의 역순으로 정렬

# for j in range(len(log)):
#     print(log[j])
# ----------------------------------------------------------------
# 2. 시간초과
# import sys

# n = int(sys.stdin.readline())

# log = []
# for i in range(0,n):
#     name, stay = map(str, sys.stdin.readline().split())
#     if stay == "enter":
#         log.append(name)
#     else: # leave
#         if name in log:
#             log.remove(name)
#         else:
#             pass

# log = sorted(log, reverse=True) 

# for j in range(len(log)):
#     print(log[j])
# ----------------------------------------------------------------

베스트셀러

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

문제 풀이

import sys

N = int(sys.stdin.readline())
b = dict()

for i in range(0,N):
    book = str(sys.stdin.readline())
    if book in b:
        b[book] += 1
    else:
        b[book] = 1

max = max(b.values())
ans = []
for key, value in b.items():
    if max == value:
        ans.append(key)

ans = sorted(ans) # 여러개일경우 사전순으로 가장 앞에있는 제목 == 정렬하기
print(ans[0])

book 이름을 입력받고 b라는 딕셔너리에 해당 책이름이 있다면 +1 해주고 없다면 1로 넣어준다.

b값들에서 value의 최댓값을 추출하고 딕셔너리 b에서 max 값과 같은 value를 가진 key값을 새로운 배열에 저장한다.

max 값이 여러개일 경우 사전순으로 가장 앞에있는 제목의 책을 출력한다고하니 ans라는 배열을 정렬해주고 해당 배열의 0번 인덱스를 출력한다.

절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

문제 풀이

import sys
import heapq

h = []
N = int(sys.stdin.readline())

for i in range(0,N):
    x = int(sys.stdin.readline())

    if x != 0:
        # x가 0이 아니라면 배열에 x값 넣기
        heapq.heappush(h, (abs(x), x))
        # 절댓값과 원본값을 튜플로 넣는다
    else:
        # x == 0
        # h가 비지 않았다면 h에 튜플로 들어가있으니 1번째를 출력한다
        # 비어있다면 0을 출력한다
        print(heapq.heappop(h)[1] if len(h) else 0) 

카드2

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

6

예제 출력 1

4

문제풀이

from collections import deque
import sys


N = int(sys.stdin.readline())
dq = deque()
for i in range(1,N+1):
    dq.append(i)

while len(dq) >1: 
    #제일 마지막에 남게되는 카드를 구하는거니까 len(dq)가 1개는 남아있어야
    dq.popleft() # 먼저들어온거부터 나가고
    dq.append(dq.popleft()) # 가장 안쪽(왼쪽)에있는 카드를 위로 올린다(=오른쪽으로 옮겨준다.)

print(dq[0])

올바른 괄호

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

입출력 예

문제 풀이

def solution(s):
    s = list(s)
    ans = []
    for i in range(len(s)):
        if s[0] == ")":
            return False
        else:
            if len(ans) == 0:
                ans.append(s[i])
            else:
                ans.append(s[i])
                if (ans[-2] =="(") and (s[i] ==")") :
                    ans.pop()
                    ans.pop()
                else:
                    pass
    if not ans:
        return True
    else:
        return False

입력된 문자열 s를 list로 끊어 저장하고 ) - 닫힌괄호로 시작한다면 return False ans 라는 리스트를 선언해주고 이 리스트에 넣어가며 올바른 괄호를 판단한다. 올바른 괄호라면 pop을 사용해 ans 리스트에서 제거해준다. 마지막에 list가 비어있다면 괄호가 모두 올바르게 짝지어져서 pop된것이니 True를 리턴 그렇지 않으면 False를 리턴한다.

문제

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

입력

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

출력

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

문제 풀이

import sys

N = int(sys.stdin.readline())
loc =[0] * N 

for i in range(0,N):
    x,y = map(int, sys.stdin.readline().split())
    loc[i] = [x,y]

loc.sort(key=lambda x: (x[1], x[0]))
# 1번 인덱스에 대해서 먼저 정렬을 진행한 뒤,
# 0번 인덱스를 정렬한다. 
# -> 0 4가 맨 뒤에 나오기에 1번째 인덱스에서부터 정렬을 진행

for j in range(len(loc)):
    print(loc[j][0], loc[j][1])

2차원 배열에서의 정렬
- 첫번째 값 이용
    lst = [[2, 1], [3, 4], [1, 2], [1, 3], [3, 2]]
    lst.sort(key=lambda x:x[0])
    print(lst)

    # [[1, 2], [1, 3], [2, 1], [3, 4], [3, 2]]
    -> lambda를 사용하여 x:x[0] 으로 0번째 인덱스에 대해서 정렬
        0번째 인덱스에 대해서 오름차순으로 정렬을 진행,
        1번째 인덱스에 대해서는 정렬이 되지 않는다.

- 두번째 값 이용
    lst = [[2, 1], [3, 4], [1, 2], [1, 3], [3, 2]]
    lst.sort(key=lambda x: (x[0], -x[1]))
    print(lst)

    # [[1, 3], [1, 2], [2, 1], [3, 4], [3, 2]]
    -> x: () 처럼 괄호안에 튜플 형식으로 집어넣는다.
        이때 -를 하면 역으로 정렬시킬 수 있다고한다.
        위 예제의 경우, 먼저 0번 인덱스에 대해서 오름차순으로 정렬하고
        동일한 값의 경우 내림차순으로 재정렬한다고한다.
    ---------------------------------------------------------------

    lst = [[2, 1], [3, 4], [1, 2], [1, 3], [3, 2]]
    lst.sort(key=lambda x: (x[1], x[0]))
    print(lst)

    # [[2, 1], [1, 2], [3, 2], [1, 3], [3, 4]]  
    -> 순서바꾸어 정렬도 가능.
        위 예제는 1번 인덱스에 대해서 먼저 오름차순으로 정렬을 진행하고   
        같은 1번인덱스의 경우 0번째 인덱스에 대해서 오름차순으로 정렬을 진행한다.
    ---------------------------------------------------------------

    2차원 배열에서 sort의 기본은 
    0번째 인덱스를 오름차순으로 정렬하고, 1번째 인덱스를 오름차순으로 정렬한다.
    특정 인덱스에 대해 정렬하려면 key를 사용해야한다.

참고한 사이트 : https://haesoo9410.tistory.com/193

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

문제 풀이

infi = 987654321
n = int(input())
dp = [infi] * (n+1)
dp[1]=0

for i in range(2,n+1):
    if i % 6==0:
        dp[i] = min(dp[i//3], dp[i//2]) +1
    elif i % 3 ==0:
        dp[i] = min(dp[i//3], dp[i-1]) +1
    elif i % 2 ==0:
        dp[i] = min(dp[i//2], dp[i-1]) +1   
    else:
        dp[i] = dp[i-1] +1

print(dp[n])

처음풀어보는 DP문제 책의 도움을 받고 이해하며 풀었다..

infi 를 987,654,321 로 설정한 이유는 1,000,000,000 을 쓰려면 0을 헷갈려 틀릴 수도 있고 10억보다 조금 작은 값이라서 대부분의 문제에서 충분히 큰 값으로 사용할 수 있다. int의 최대 범위인 21억의 절반보다 더 작은 값이라서 이 값끼리 더해져도 오버플로우가 발생하지 않는다.

'무한'을 의미하기 위해 충분한 큰 수로 사용한다고 한다.

1463번 - DP 문제 Bottom-up 풀이 방식 재귀가 아닌 반복문으로 구현하며, 작은 X에 대해서부투 부분 문제를 구해서 입력받은 수까지 수행한다. DP 테이블을 채우는 타뷸레이션 수행

n이 10일경우 문제를 풀어보자면,
i=2)
    dp[2] = min(dp[1], d[1]) +1
    **dp[1]이 0이라고 설정해두었으니
    dp[2] = 0+1 
i=3)
    dp[3] = min(dp[1], dp[2]) +1
    dp[3] = 0+1
i=4)
    dp[4] = min(dp[2], dp[3]) +1
    dp[4] = 1+1
i=5)
    dp[5] = dp[4] +1
    dp[5] = 2+1
i=6)
    dp[6] = min(dp[2], dp[3]) +1 
    dp[6] = 1+1 
i=7)
    dp[7] = dp[6] +1
    dp[7] = 2+1 
i=8)
    dp[8] = min(dp[4], dp[7]) +1
    dp[8] = 2+1
i=9)
    dp[9] = min(dp[3], dp[8]) +1
    dp[9] = 1+1
i=10)
    dp[10] = min(dp[5], dp[9]) +1
    dp[10] = 2+1

--> dp[10]일 경우, 3이 출력된다.

문제 설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2 A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10) 이 경우가 최소이므로 10을 return 합니다.

문제 풀이

1)

  def solution(A,B):
      answer=[]
      A = sorted(A)
      B = sorted(B, reverse=True)

      for j in range(len(A)):
          answer.append(A[j] * B[j])

      return sum(answer)

2)

  #     answer = []
  #     for i in range(len(A)):
  #         answer.append((min(A) * max(B)))
  #         A.remove(min(A))
  #         B.remove(max(B))

  #     return sum(answer)

처음엔 2번으로 풀었다가 효율성에서 아예 통과하지 못했었다. 정렬을 미리 해주지 않으면 min, max를 찾을때 값을 전체를 훑어야해서 효율적이지 않다고 판단하는것같다.

A에서 min 값을 찾고 B에서 max 값을 찾는 로직을 A는 오름차순 B는 내림차순으로 정렬한 뒤 같은 인덱스 번호끼리 곱하니 효율성에서 잘 통과가 되었다.

JadenCase 문자열 만들기

문제 설명

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 단, 첫 문자가 알파벳이 아닐 때에는 이어지는 알파벳은 소문자로 쓰면 됩니다. (첫 번째 입출력 예 참고) 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

제한 조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
  • 숫자는 단어의 첫 문자로만 나옵니다.
  • 숫자로만 이루어진 단어는 없습니다.
  • 공백문자가 연속해서 나올 수 있습니다.

입출력 예

문제 풀이

def solution(s):
    word = list(map(str, s.split(" ")))
    answer =[]
    for i in word:
        w =''
        if i=='':
            answer.append(w)
        else:
            if i[0].isdigit():
                w += i[0]
                w += i[1:].lower()
                answer.append(w)
            else:
                w += i[0].upper()
                w += i[1:].lower()
                answer.append(w)

    return ' '.join(answer)

최댓값과 최솟값

문제 설명

문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다.

제한 조건

• s에는 둘 이상의 정수가 공백으로 구분되어 있습니다.

입출력 예

문제 풀이

def solution(s):
    s_list = list(map(int, s.split()))

    return str(min(s_list))+ " "+ str(max(s_list))

예산

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

입출력 예

입출력 예 설명

입출력 예 #1

각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.

• 1원, 2원, 3원을 신청한 부서의 물품을 구매해주려면 6원이 필요합니다.
• 1원, 2원, 5원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
• 1원, 3원, 4원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
• 1원, 3원, 5원을 신청한 부서의 물품을 구매해주려면 9원이 필요합니다.

3개 부서보다 더 많은 부서의 물품을 구매해 줄 수는 없으므로 최대 3개 부서의 물품을 구매해 줄 수 있습니다.

입출력 예 #2

모든 부서의 물품을 구매해주면 10원이 됩니다. 따라서 최대 4개 부서의 물품을 구매해 줄 수 있습니다.

문제 풀이

def solution(d, budget):
    answer = 0
    d.sort()
    for i in range(len(d)):
        if d[i] <= budget:
            answer +=1
            budget -= d[i]
        else:
            pass

    return answer