졍's 기술 블로그

이전 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

예제 입출력

Algorithm

Greedy 이용
1. 입력 순열을 리스트로 받음
2. N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
3. 리스트의 마지막 숫자가 1보다 크면
3.1. 리스트의 끝에서부터 내림차순 정렬되어있는 부분 모두 pop
3.2. 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
4. 리스트의 마지막 숫자가 1이면
4.1. pop하고 리스트의 (마지막 숫자 - 1) % (N+1)을 저장하고 pop한 후 저장된 숫자 append
    ☞ (마지막 숫자 - 1) % (N+1)가 리스트 내에 존재하지 않아야 함
5. 남은 자리수 stack에 포함되어있지 않은 값으로 채우기

Code

N = int(input())
stack = list(map(int, input().split()))

# N이 1이거나 리스트가 오름차순 정렬되어있으면 -1 출력
if N == 1 or stack == list(range(1, N+1)):
    print(-1)
else:
    # 리스트의 마지막 숫자가 1보다 크면
    if stack[-1] > 1:
        # 리스트의 끝에서부터 처음으로 가면서 내림차순 정렬되어있는 부분 모두 pop
        for index in range(N-1, 0, -1):
            if stack[index-1] < stack[index]:
                stack.pop()
            else:
                break
        stack.pop()
        
        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)
    else:
        stack.pop()

        # 다음에 들어가야할 숫자 저장
        next_num = (stack[-1] - 1) % (N+1)
        if next_num == 0:
            next_num = N-1
        while next_num in stack:
            next_num = (next_num - 1) % (N+1)
            if next_num == 0:
                next_num = N-1

        # 리스트의 마지막 원소를 새로운 숫자로 변경
        stack.pop()
        stack.append(next_num)
        
        # 리스트 나머지 자리 채우기
        for num in range(N, 0, -1):
            if num not in stack:
                stack.append(num)

    print(' '.join(list(map(str, stack))))

메모리: 30864 KB
시간: 640 ms

소수

티어 : Silver 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 정수론, 소수 판정

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입출력

Code

# 입력
M = int(input())
N = int(input())

# 소수 찾기
sum_ = 0
min_ = 10000
for i in range(M, N+1):
    count = 0
    if i > 1 and i < 4: # i가 2 또는 3인 경우 소수로 판별
        sum_ += i
        if min_ > i:
            min_ = i
    else: # 그 외의 숫자인 경우
        for j in range(2, i//2 + 1): # 2 ~ i의 절반에 해당하는 숫자까지로 i를 나눠봄
            if i % j == 0: # 나누어 떨어지면 더이상 검사하지 않고 다음 숫자 확인
                break
            else: # 나누어 떨어지지 않는 경우 몇 번 나누어 떨어지지 않았는지 Count
                count += 1
        if count == i//2 - 1: # 나누어 떨어지지 않은 횟수가 j for문을 돈 횟수와 같다면
            sum_ += i # 소수로 판별
            if min_ > i:
                min_ = i
            
if sum_ > 0:
    print(sum_)
    print(min_)
else:
    print(-1)

메모리: 30860 KB
시간: 480 ms

로프

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 192 MB
알고리즘 분류 : 수학, 그리디 알고리즘, 정렬

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 각 로프의 중량을 리스트에 담아 sort
2. 1개 쓸 때부터 N개 쓸 때까지의 최댓값 구하기
    ☞ 각 최댓값은 [N-i] * i

Code

import sys
input = sys.stdin.readline

# 입력
N = int(input())
weights = []
for _ in range(N):
    weights.append(int(input()))

# 중량 리스트 오름차순 정렬
weights.sort()

# 로프 i개 쓸 때부터 N개 쓸 때까지 최댓값 갱신
max_weights = 0
for i in range(1, N+1):
    if max_weights < weights[N-i] * i:
        max_weights = weights[N-i] * i
print(max_weights)

메모리: 34080 KB
시간: 140 ms

다음 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 조합론

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 입력 숫자를 리스트에 받음
2. N이 1이면 -1 출력
3. nums의 마지막 숫자가 N보다 작으면
3.1. 끝에서부터 증가하는 숫자인 경우 모두 pop
3.2. 리스트가 비어있으면 -1 pop
3.3. 리스트가 비어있지 않으면 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
    ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함
4. nums의 마지막 숫자가 N이면
4.1. 2번 pop
4.2. 마지막 값 + 1을 저장해두고 pop후 저장해둔 값 append해서 출력
   ☞ 마지막 값 + 1이 N을 넘지 않아야하고 리스트에 들어있지 않은 숫자여야 함

Code

N = int(input())
nums = list(map(int, input().split()))

# 한자리숫자이면 -1 출력
if N == 1:
    print(-1)
# nums의 마지막 숫자가 N보다 작으면 끝에서부터 1씩 증가하는 부분 모두 pop
elif nums[-1] < N:
    for index in range(N-1, 0, -1):
        if nums[index-1] > nums[index]:
            nums.pop()
            # nums의 길이가 1인데 값이 N이면 -1출력
            if len(nums) == 1 and nums[0] == N:
                print(-1)
                break
        else:
            break
    nums.pop()
    # nums가 빈 리스트가 아니면
    if nums:
        # 다음에 올 숫자 저장
        num = (nums[-1] + 1) % (N + 1)
        if num == 0:
            num += 1
        # 이미 포함되어있는 숫자인지 확인
        while num in nums:
            if num in nums:
                num = (num + 1) % (N+1)
        
        nums.pop()
        nums.append(num)
        
        for num in range(1, N+1):
            if num not in nums:
                nums.append(num)
        print(' '.join(list(map(str, nums))))
# nums의 마지막 숫자가 N이면 2번 pop
else:
    nums.pop()
    num = (nums[-1]+1)%(N+1)
    if num == 0:
            num += 1
    # 이미 포함되어있는 숫자인지 확인
    while num in nums:
        if num in nums:
            num = (num + 1) % (N+1)

    nums.pop()
    nums.append(num)

    # 숫자를 1부터 N까지 확인하면서 들어있지 않은 숫자이면 append
    for num in range(1, N+1):
        if num not in nums:
            nums.append(num)
    print(' '.join(list(map(str, nums))))

메모리: 30864 KB
시간: 996 ms

숫자의 개수

티어 : Bronze 2
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다.

출력

첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

예제 입출력

Code

A = int(input())
B = int(input())
C = int(input())

num = str(A*B*C)
count = [0 for _ in range(10)]
for i in range(len(num)):
    count[int(num[i])] += 1

for i in count:
    print(i)

메모리: 29200 KB
시간: 72 ms

벌집

티어 : Bronze 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

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

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제 입출력

Code

N = int(input())

cum_sum = 1
count = 1
if N == 1:
    print(count)
else:
    while True:
        cum_sum += 6 * count
        count += 1
        if cum_sum >= N:
            print(count)
            break

메모리: 30864 KB
시간: 72 ms

암호 만들기

티어 : Gold 5
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 조합론, 백트래킹

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입출력

Algorithm

back tracking - 재귀
1. 입력받은 문자열을 리스트로 저장해 오름차순 정렬
2. stack에 들어있지 않은 문자열 append
3. stack의 길이가 L이 되면 stack 안에 모음이 1개 이상, 자음이 2개 이상 포함되어있는 것만 출력

Code

def back_tracking():
    
    # stack의 길이가 L이 되면
    if len(stack) == L:
        # stack 안에 모음과 자음 개수 확인
        vowel = 0 # 모음
        consonant = 0 # 자음
        for word in stack:
            if word in ['a', 'e', 'i', 'o', 'u']:
                vowel += 1
            else:
                consonant += 1
                
        # stack 안에 모음 1개 이상, 자음 2개 이상 포함되어있으면 출력
        if vowel > 0 and consonant > 1:
            print(''.join(stack))
    else:
        for word in words:
            # stack이 비어있으면
            if not stack:
                # 바로 append
                stack.append(word)
                back_tracking()
                stack.pop()
            # stack 비어있지 않으면 satck에 없고 stack의 마지막 원소보다 큰 알파벳만 저장
            elif word not in stack and word > stack[-1]:
                stack.append(word)
                back_tracking()
                stack.pop()
                
L, C = map(int, input().split())
words = list(input().split())
words.sort()

stack = []
back_tracking()

메모리: 30864 KB
시간: 148 ms

수 이어 쓰기 1

티어 : Silver 3
시간 제한 : 0.15 초 (Python 0.5 초)
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 구현

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

예제 입출력

Algorithm

1. 입력받은 숫자의 자리수 구하기
2. 1 자리수면 입력받은 숫자 print
3. 2 자리수면 9 + ((N-10) + 1) * 2
4. 3 자리수면 9 + 90 + ((N-100) + 1) * 2
...

Code

N = input()
answer = 0
for i in range(len(N)-1):
    answer += 9 * (10**i) * (i+1)
answer += (((int(N)-10**(len(N)-1)) + 1) * len(N))
print(answer)

메모리: 30860 KB
시간: 68 ms