Dasein's ‎Archive

문제 링크: www.acmicpc.net/problem/1094

정답 코드 #1

def div():
    half = int(stick[-1] / 2)
    stick[-1] = half
    
    if sum(stick) < X:
        stick.append(half)
        
    return stick

X = int(input())
stick = [64]

while sum(stick) != X:
    if sum(stick) > X:
        stick = div()

print(len(stick))

문제 풀이 #1

정답 코드 #1은 문제에 제시된 방법 그대로 구현한 정답이다. 막대를 자르는 작업을 div() 함수로 구현하였다.

우선 막대들을 나타내는 리스트 형의 stick에는 처음 64cm인 막대가 1개 저장되어 있다.

문제가 종료되는 시점은 가지고 있는 막대들의 합이 X와 같아지는 순간이므로 while를 통한 반복문을 구현하였으며, 막대를 자르는 조건인 막대들의 길이의 합 sum(stick)가 X 보다 큰 경우 막대를 자르는 div() 함수를 실행시킨다.

div 함수에는 기본적으로 제일 짧은 막대를 반으로 나누는 과정을 거치며, 만약 자른 막대 중 하나를 버리고 남은 막대의 길이의 합이 X 보다 크거나 같다면, 자른 막대 중 하나를 버리는 과정을 역으로 생각하여 stick[-1]을 우선 반으로 나눈 다음에 만약 막대 길이의 합이 X 보다 작은 경우에 제일 짧은 길이의 막대를 append 해 주었다.

그리고 막대 길이의 합이 X와 같아져서 반복문이 종료되면, stick의 갯수를 len()를 이용해서 구하고 출력했다.

정답 코드 #2

X = int(input())
cnt = 0

while X != 0:
    if X % 2 == 1:
        cnt += 1
    X = X // 2
    
print(cnt)

문제 풀이 #2

정답 코드 #2는 비트 마스킹을 활용한 문제 풀이이다.

비트 마스킹은 비트(bit)를 활용한 풀이 기법이다.

비트에 초점을 맞추면 위의 문제는 결국 주어진 X를 2진수로 표기하였을 때, 1의 개수를 출력하는 문제이다.

예를 들어 23을 2진수로 표기하면 10111로 1은 총 4개가 있고. 32를 2진수로 표현하면 100000으로 1은 1개가 있다.

문제 링크: www.acmicpc.net/problem/2635

정답 코드

A = int(input())
result = []
max = 0

for i in range(A+1):
    tmp = [A]
    tmp.append(i)
    
    while (tmp[-2] - tmp[-1]) >= 0:
        tmp.append(tmp[-2] - tmp[-1])
        
        if len(tmp) > max:
            max = len(tmp)
            result = tmp

print(len(result))

for i in result:
    print(i, end=" ")

문제 풀이

두 번째 수는 정해지지 않았으며 모든 경우의 수를 다 검사하는 브루트포스 알고리즘이다. 따라서 0부터 A까지 모든 수를 다 넣어보면서 최대 길이를 비교한다.

결국 배열 내부의 새로운 수를 만들어내기 위해서 배열의 끝부분 부터 접근하는 방법을 택했다.

그리고 while의 조건을 0이상의 수로 설정함으로써 음수가 나오는 경우에 반복을 종료한다.

그렇게 완성된 list의 길이를 비교해서 이전까지의 리스트의 최대길이를 저장하는 max와 비교한 후 max 값을 변경한.

마지막으로, 처음 작성한 코드의 경우 예제 입력인 100을 입력하였을 때, 예제 출력과 동일하게 나왔다.

8

100 62 38 24 14 10 4 6

만약 결과는 동일하게 나오지만 정답을 인정해 주지 않는 경우, 1을 입력한 경우 예제 출력은

4

1 1 0 1

와 같이 나오니 이 부분도 추가로 실행시켜 보는 것을 추천한다.

문제 링크: www.acmicpc.net/problem/7568

정답 코드

N = int(input())
d_list = []

for _ in range(N):
    w, h = map(int, input().split())
    d_list.append((w,h))
    
for i in d_list:
    rank = 1
    
    for j in d_list:
        if i[0]<j[0] and i[1]<j[1]:
            rank += 1
    print(rank)

문제 풀이

자기 자신과 다른 사람의 키와 몸무게를 동시에 비교하면서, 둘 다 큰 사람이 있을 경우에 rank를 1씩 증가시키는 것을 기본으로 한다.

and를 사용함으로써 키와 몸무게 둘 중 하나만 크다고 할지라도 rank가 증가하지 않아서 덩치 등수 계산이 가능하다.

또한 자기 자신과 비교하는 경우를 방지하기 위해서 '<='가 아닌 '<'를 사용했다.

문제 링크 : www.acmicpc.net/problem/4673

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

정답 코드

def d(n):
    x = list(map(int, list(str(n))))
    return n + sum(x)

s = set(range(1,10001))
not_s = set()

for i in range(1, 10001):
    not_s.add(d(i))

s -= not_s
s = list(s)
s.sort()

for i in s:
    print(i)

문제 풀이

우선, 함수 d(n)을 정의한다. n은 d(n)의 생성자로써, 셀프 넘버에 해당하지 않는 수이다.

함수 d(n)에 대해서 자세하게 설명해보면 예를 들어, n = 33이라면 33 + 3 + 3 = 39가 나와야 한다.

def d(n):
    x = list(map(int, list(str(n))))
    return n + sum(x)

여기에서 n = 33이므로 list(str(n))을 실행하게 되면 아래와 같은 결과가 나온다.

33을 각 자리수로 분리하는 것에는 성공했지만, '+' 연산에는 적합하지 않은 문자형으로 분리가 되었으므로, map() 함수를 사용해서 각 element를 정수형으로 변환시켜준다. 

그리고 n에 각 자리수를 모두 더한 값인 n + sum(x)를 반환시켜준다.

이런 셀프 넘버에 해당하지 않는 숫자들을 집합 not_s에 추가하고, 1 이상 10000 이하의 정수를 저장하고 있는 집합 s에서 빼면, 셀프 넘버에 해당하는 숫자들의 집합인 s가 남는다.

set type인 s를 list type로 변환시켜주고 sort() 함수를 통해서 정렬해 준 뒤 순서대로 출력하면 문제를 해결할 수 있다.

문제 링크 : www.acmicpc.net/problem/2751

정답 코드

import sys

N = int(sys.stdin.readline().rstrip())
num = []

for i in range(N):
    num.append(int(sys.stdin.readline().rstrip()))

num.sort()

for i in num:
    print(i)

문제 풀이

해당 문제는 보통 입력받는 방법인 input()로 코드를 짜면 시간 초과가 나온다.

따라서 sys를 import해서 readline()으로 코드를 작성하면 정답으로 처리가 된다.

문제 링크 : www.acmicpc.net/problem/10828

정답 코드

import sys

def push(x):
    stack.append(x)
    
def pop():
    if (not stack):
        return -1
    else:
        return stack.pop()

def size():
    return len(stack)

def empty():
    return 0 if stack else 1
    
def top():
    return stack[-1] if stack else -1

N = int(sys.stdin.readline().rstrip())
stack = []

for _ in range(N):
    text = sys.stdin.readline().rstrip().split()
    
    operator = text[0]
    
    if operator == 'push':
        push(text[1])
        
    elif operator == 'pop':
        print(pop())
        
    elif operator == 'size':
        print(size())
        
    elif operator == 'empty':
        print(empty())
        
    elif operator == 'top':
        print(top())

문제 풀이

해당 문제는 일반적인 스택을 구현하는 문제이다. 구현에 큰 어려움은 없지만 시간제한이 있어서 생각보다 까다로운 문제였다.

N = int(input())
stack = list()

for _ in range(N):
    text = input().split()
    if text[0] == 'push':
        stack.append(text[1])
        
    elif text[0] == 'pop':
        if len(stack) == 0:
            print(-1)
        
        else:
            print(stack[len(stack)-1])
            stack.pop()
        
    elif text[0] == 'size':
        print(len(stack))
        
    elif text[0] == 'empty':
        if len(stack) == 0:
            print(1)
        else:
            print(0)
        
    elif text[0] == 'top':
        if len(stack) == 0:
            print(-1)
        
        else:
            print(stack[len(stack)-1])

제일 처음의 코드 형태이다. 시간 초과로 인하여 실패했으며, 소요시간을 줄이고 코드를 조금 더 Pythonic 하게 변경시켜서 정답 코드의 형태로 변화시켰다.

N = int(input())

text = input().split()

그럼에도 불구하고 계속 시간 초과가 발생했다.

해결법은 생각보다 간단하였다. input()로 입력을 받는 방법에서 sys를 import해서 readline()으로 바꾸었더니 제한 시간 이내에 코드가 실행되었다.

문제 링크 : www.acmicpc.net/problem/1152

정답 코드

text = input().split()

print(len(text))

문제 풀이

해당 문제는 split() 함수를 사용할 수 있는지를 확인하는 문제이다.

text = input().split()

위 코드를 통해서 입력받은 문장을 split()를 통해서 공백(띄어쓰기)을 기준으로 분할하여 리스트 형태로 반환한다.

그 이후 len()함수를 통해서 리스트의 길이를 출력하여 문제를 해결할 수 있다.

문제 링크 : www.acmicpc.net/problem/1157

정답 코드

from collections import Counter

text = input().upper()
c = Counter(text)
M = 0
ans = ''

for i, j in c.items():
    if j > M:
        M = j; ans = i
    
    elif j == M:
        M = j; ans = '?'
        
print(ans)

문제 풀이

해당 문제를 쉽게 풀이하기 위해서 Counter을 import 해서 사용하였다.

우선 대,소문자를 따로 구분하지 않기 위해서 text를 입력받을 때 upper()을 사용하여 모두 대문자로 변환시켜주었다.

그 후 입력받은 text를 Counter 함수를 사용해서 변환시켜 주었으며, for문을 통해서 최대 빈도를 구해서 M에 저장시키며 해당 단어는 ans에 저장하여 주었다.

모든 단어에 대해서 실행을 완료한 뒤 최종적으로 ans를 출력해 주었다.