thdwldud_

<문제>
사파리월드는 인터넷으로만 존재하는 미스테리한 나라이다. 사파리월드에는 2개의 서브도메인이 seunghwan.royal.gov.sw와 kyuhyun.royal.gov.sw 이 있는데, 이것이 couple.royal.gov.sw으로 합쳐질 것이다. 그러나 도메인 관리 센터 SWNIC(센터장: 김동규)에는 엄격한 룰이 있다. 두 서브도메인을 합칠 때, 유명도의 차이가 너무 차이나지 않을 경우에만 두 서브도메인을 결혼시키는 것이다. 서브도메인의 유명도는 정수이다. 두 서브도메인의 유명도가 주어졌을 때, 그 차이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 도메인의 유명도 N과 M이 주어진다. (-2,000,000,000 ≤ N, M ≤ 2,000,000,000)

출력

첫째 줄에 두 유명도의 차이 (|N-M|)을 출력한다.

💡문제 해결 아이디어

• 단순 사칙연산 문제
• abs() 정수 절대값 연산 함수

n, m = map(int, input().split())

print(abs(n - m))

<문제>
재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.
1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,
10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...
총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

💡문제 해결 아이디어

• 컴퓨터가 1번부터 10번까지 번호가 부여된 것이 키 포인트
• a의 1의 자리에 따라 n제곱 했을 경우 1의 자리 패턴이 정해져 있음
  
  • 1, 5, 6 : 그대로 출력. 10의 경우 0이므로 10(컴퓨터번호) 출력 
  • 4, 9 : b를 2로 나누었을 때 나머지가 1일 경우 그대로 출력, 0일 경우 a^2의 1의자리 출력
  • 2, 3, 7, 8: b를 4로 나누어 봤을 때 나머지가 0일 경우 a^4의 1의 자리 출력, 아닐경우 (a의 1의자리) x (b의 나머지)의 1의 자리 출력

# 시간초과 코드
t = int(input())

for _ in range(t):
    a, b = map(int, input().split())
    print((a ** b) % 10)

t = int(input())

for _ in range(t):
    a, b = map(int, input().split())
    aa = a % 10 # a의 1의 자리
    
    # a의 1의자리가 0이라면(a는 10의 배수)
    if aa ==0: 
        print(10)
        
    # a의 1의자리가 1, 5, 6 이라면
    elif aa in [1, 5, 6]:
        print(aa) # 그대로 출력
    
    # a의 1의자리가 4, 9 라면
    elif a in [4, 9]:
        if b % 2 == 0: # 2가지 경우 존재
            print((aa ** 2) % 10)
        else:
            print(aa)

	# a의 1의자리가 2, 3, 7, 8 이라면
	else:
        bb = b % 4 # 4가지 경우 존재
        if bb == 0:
            print((aa ** 4) % 10)
        else:
            print((aa ** bb) % 10)

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

입력

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

출력

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

💡문제 해결 아이디어

• 알고리즘에 이분탐색이 있지만 후에 알고리즘 공부 후 다시 해당 방법으로 풀 예정
• 이번에는 간단하게 set으로 만들어 탐색하는 풀이 사용
  • list를 사용할 경우 시간초과 발생
    • list의 in 연산자를 통한 포함 여부의 시간 복잡도는 O(n)
    • set, dictionary의 in 연산을 통한 포함 여부의 시간 복잡도는 O(1) 
  • 해당 집합에 포함되는지 여부만 확인하면 되므로 set 자료형을 사용

n = int(input())
a = set(map(int, input().split())) # 시간복잡도를 고려하여 set자료형 사용

m = int(input())
array = list(map(int, input().split()))

for num in array:
    print(1) if num in a else print(0)

<문제>
양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

💡문제 해결 아이디어

• 둘째 줄에 N의 약수가 주어지므로 
  • sort() 사용해서 제일 처음, 마지막 약수를 곱하기
  • min(), max() 사용해서 가장 작은 약수, 가장 큰 약수 곱하기

# 약수의 개수
n = int(input())

# N의 진짜 약수
a = list(map(int, input().split()))

# N의 약수 정렬하기
a.sort()

# 맨앞 약수와 맨뒤 약수 곱해서 N구하기
print(a[0] * a[-1])

# 약수의 개수
n = int(input())

# N의 진짜 약수
a = list(map(int, input().split()))

# 최대값과 최소값 곱해서 N 구하기
print(max(a) * min(a))

<문제>
시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.
dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.
이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 "." 그리고 "?"만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

입력

첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 알파벳 소문자와 '.' 로만 이루어져 있다.

출력

첫째 줄에 패턴을 출력하면 된다.

💡문제 해결 아이디어

• 첫번째 파일 이름을 기준으로 비교해서 다를 경우 '?'로 변경해주기

n = int(input())

# 첫번째 파일이름(문자열)을 리스트로 저장
first_str = list(input())
first_len = len(first_str) # 파일 이름의 길이는 모두 같음

# 두번째 파일 이름부터 비교
for _ in range(n - 1):
    next_str = list(input())
    for s in range(first_len):
        if first_str[s] != next_str[s]: # 인덱스로 문자열을 비교. 다를 경우 '?'로 변경
            first_str[s] = '?' 

print(''.join(first_str))

<문제>
옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

5
1 1 1 6 0
2 7 8 3 1

출력

첫째 줄에 S의 최솟값을 출력한다.

18

힌트

예제 1의 경우 A를 {1, 1, 0, 1, 6}과 같이 재배열하면 된다.

💡문제 해결 아이디어

• A를 오름차순 정렬, B를 내림차순 정렬하여 (A의 작은값) x (B의 큰값) 각각 더하면 해결할 수 있지만,
  => "단, B에 있는 수는 재배열하면 안 된다." 의 조건으로 정렬할 수 없음.
• A 배열의 작은 수와 B 배열의 큰 수를 곱해주고, 그 수들을 pop() 함수를 이용해서 배열에서 제외해줌

# n 입력받기
n = int(input())

# 배열 입력받기
a = list(map(int, input().split()))
b = list(map(int, input().split()))

result = 0

for i in range(n):
    result += min(a) * max(b)
    a.pop(a.index(min(a))) # 배열 a의 제일 작은 수 제외
    b.pop(b.index(max(b))) # 배열 b의 제일 큰 수 제외

print(result)

<문제>
세준이는 컵 3개를 탁자 위에 일렬로 엎어놓았다. 컵의 번호는 맨 왼쪽 컵부터 순서대로 1번, 2번 3번이고, 세준이는 이 컵을 이용해서 게임을 하려고 한다.
먼저 1번 컵의 아래에 공을 하나 넣는다. 세준이는 두 컵을 고른 다음, 그 위치를 맞바꾸려고 한다. 예를 들어, 고른 컵이 1번과 2번이라면, 1번 컵이 있던 위치에 2번 컵을 이동시키고, 동시에 2번 컵이 있던 위치에 1번 컵을 이동시켜야 한다. 이때 공은 움직이지 않기 때문에, 공의 위치는 맨 처음 1번 컵이 있던 위치와 같다.
세준이는 컵의 위치를 총 M번 바꿀 것이며, 컵의 위치를 바꾼 방법이 입력으로 주어진다. 위치를 M번 바꾼 이후에 공이 들어있는 컵의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 컵의 위치를 바꾼 횟수 M이 주어지며, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 컵의 위치를 바꾼 방법 X와 Y가 주어지며, X번 컵과 Y번 컵의 위치를 서로 바꾸는 것을 의미한다. X와 Y의 값은 3보다 작거나 같고, X와 Y가 같을 수도 있다.

컵을 이동시킨 후에 공이 컵 바깥에 있는 경우는 없다.

출력

첫째 줄에 공이 들어있는 컵의 번호를 출력한다. 공이 사라져서 컵 밑에 없는 경우에는 -1을 출력한다.

💡문제 해결 아이디어

• list.index(값) 사용

# 바꾼 횟수 입력 받기
m = int(input())
# 첫번째 위치에 공 있음
cup = [0, 1, 0, 0]

for i in range(m):
  a, b = map(int, input().split())
  cup[a], cup[b] = cup[b], cup[a] # 공 위치 변경

print(cup.index(1)) # 공이 있는(1) 인덱스 출력

<문제>
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.
줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

💡문제 해결 아이디어

• 인출하는데 필요한 시간이 가장 적은 사람이 먼저 인출할 수록 총 소요 시간이 짧아짐
• sum 함수 사용

n = int(input())
time = list(map(int, input().split()))

time.sort() # 인출하는 시간 오름차순 정렬
cnt = 0 # 총 소요 시간

for i in range(1, n+1):
  cnt += sum(time[:i]) # 리스트의 0번재 수부터 i번째 수까지 더해줌
print(cnt)