[CLASS 2]백준 1978번, 2108번, 2164번

1978번 : 소수 찾기

 

주어진 수들 중에 소수가 몇 개 있지 찾아 출력하는 문제이다. 어렵지 않다.

 

먼저 첫 번째 방법으로는 모든 숫자마다 해당 숫자보다 작은 수로 나누어 보아서 나누어지면 소수가 아니라고 판단하는 방법이다.

 

내 코드:

import sys
input = sys.stdin.readline

# 모두 검사
def isPrimeNum(number):
    if number == 1:
        return 0
        
    for i in range(2,number):
        if number % i == 0:
            return 0
    
    return 1

# 입출력
n,numbers,count = input(),list(map(int,input().split())),0
for number in numbers:
    count += isPrimeNum(number)

print(count)

 

이 방법이 가장 직관적이다. 그러나 소수라는 것에 대해 조금 더 생각해본다면 해당 숫자보다 작은 숫자를 모두 검사할 필요는 없다.

 

어떤 숫자를 넓이로 가지는 직사각형을 생각해보자. 예를 들어 넓이가 28인 직사각형이 있다고 하면, 이를 가로와 세로 두 정수의 곱으로 나타낸다면 1X28, 2X14, 4X7, 7X4, 14X2, 28X1 로 나타낼 수 있다.

 

여기서 알 수 있는 점은 4X7과 7X4의 중심을 기준으로 양 옆이 대칭이라는 뜻이다.

 

이 문제는 1000 이하의 자연수만 주어지기 때문에 해당 수가 1000의 제곱근을 넘지 않는 수로 나누어지지 않는다면 소수라고 판단할 수 있고, 이런 코드를 작성할 수 있다.

 

내 코드:

import sys
input = sys.stdin.readline

# 소수의 성질 이용
def isPrimeNum(number):
    if number == 1:
        return 0
    
    # 1000의 제곱근보다 작은 소수들
    primes = [2,3,5,7,11,13,17,19,23,29,31]
    for prime in primes:
        if number % prime == 0:
            if number == prime:
                return 1
            return 0
        
    return 1

# 입출력
n,numbers,count = input(),list(map(int,input().split())),0
for number in numbers:
    count += isPrimeNum(number)

print(count)

 

어떤 수가 소수인지 검사할 때, 해당 수가 1000의 제곱근보다 작은 소수들로 나누어 떨어지는지를 검사하면 된다. 만약 나누어 떨어진다면, 해당 수가 그 소수(나누는 수)가 아닌지만 확인한 후 소수가 아니라고 판단하면 된다.

 

참고로 어떠한 소수로도 나누어지지 않는다면 소수들의 곱으로 이루어진 합성수로도 나누어지지 않기 때문에 다른 수들(32, 46 등등..)로 일일이 나누어보지 않아도 된다.

 

2108번 : 통계학

 

그냥 주어진 대로 계산하는 로직을 만들면 된다.

 

내 코드:

import sys
input = sys.stdin.readline

data = []
for _ in range(int(input())):
    data.append(int(input()))
data.sort()

# 평균
avg = round(sum(data) / len(data))

# 중앙값
mid = data[len(data) // 2]

# 최빈값
counts = [0] * 8001
for number in data:
    counts[number+4000] += 1

mod = counts.index(max(counts)) - 4000
if counts.count(max(counts)) > 1:
    mod = counts.index(max(counts),mod + 4000 + 1) - 4000

# 범위
rng = max(data) - min(data)

# 출력
print(avg,mid,mod,rng,sep='\n')

 

평균과 중앙값, 그리고 범위는 파이썬에서 아주 깔ㅡ끔 하게 떨어진다. 최빈값이 조금 문제인데, 최빈값이 하나만 있다는 보장이 있었다면 쉬웠겠지만 그렇지 않아서 조금 까다롭다. 심지어 두 번째로 작은 최빈값이기 때문에...

 

2164번 : 카드2

 

큐를 바로 떠올리긴 했지만 쉽게쉽게(?) 그냥 리스트를 사용하여 먼저 구현해 보았다.

 

내 코드(시간초과):

n = int(input())
cards = [i for i in range(n,0,-1)]
while len(cards) > 1:
    cards.pop()
    cards.insert(0,cards.pop())

print(cards.pop())

 

이렇게 해도 답은 잘 나온다. 그러나 insert의 시간이 너무 많이 들어서 시간 초과가 나온 것으로 보인다.

 

이후에는 파이썬의 Queue를 사용하여 구현해 보았다.

 

내 코드(큐,시간초과):

import queue

n = int(input())
cards = queue.Queue()
for i in range(1,n+1):
    cards.put(i)

while cards.qsize() > 1:
    cards.get()
    cards.put(cards.get())

print(cards.get())

 

그러나 이번에도 시간 초과에 걸렸다. 문제의 의도가 큐가 아닌가? 하고 조금 검색해 보았는데, 파이썬의 queue는 멀티쓰레딩의 용도로 만들어 져서 느리다고 한다. 그래서 좀더 근본적인 라이브러리 collections.deque를 사용하기로 했다. 몰랐는데, deque가 좀더 만능이고 다양한 기능을 구현하기에 더 느릴 줄 알았는데, 오히려 queue보다도 더 빨라서 알고리즘 문제에서는 보통 deque를 쓴다고 한다. 파이썬의 queue도 내장으로 deque라이브러리를 사용하고 있다고 한다.

 

내 코드(덱):

# 덱(deque)을 사용한 풀이
from collections import deque

n = int(input())
cards = deque([i for i in range(1,n+1)])

while len(cards) > 1:
    cards.popleft()
    cards.append(cards.popleft())

print(cards.pop())

 

덱을 사용하니 속도도 잘 나오고 맞았다. 로직도 단순히 문제에 쓰여 있는것을 그대로 코드로 옮기면 된다.

 

규칙성을 찾는 풀이도 있다. 다음은 해당 문제에서 n 을 1부터 32까지 주었을 때의 결과이다.

 

 

잘 보면 매번 2의 거듭제곱 마다, 2, 4, 6, 8, ... , n - 4, n - 2, n 의 형태가 반복되는 것을 확인할 수 있다. 이를 일반화 한다면,

 

임의의 n 에서 해당 n 보다 크지 않은 2의 거듭제곱수를 t 라고 한다면 f(n) = 2(n - t)

 

이점에 착안하여 코드를 작성하면,

 

내 코드(규칙성):

# 규칙성을 찾는 풀이
n,t=int(input()),1
# 1이 입력일 경우 거름
if n == 1:
  print(1)
  exit()
  
while True:
    t *= 2
    if t >= n:
      t //= 2
      break
print((n-t)*2)

 

규칙성을 찾아서 이를 이용하여 코드를 작성할 수 있다면 코드의 속도가 훨씬 빨라진다. 그러나 대부분의 문제에서는 이런 규칙성이 존재하는지도 미지수일뿐더러, 첫 시도에서는 구현하는데 바빠서 찾기조차 힘들다. 한번 문제를 풀어본 뒤에, 결과에 이것저것 수를 대입하여 규칙성을 찾아보는 것도 나쁘지 않은 것 같다.