우주의 IT 소행성

주어진 범위 내에서 소수를 찾아, 그 소수들의 합과 최소값을 가지는 소수를 출력하는 문제이다.

에라토스테네스의 체 알고리즘을 이용하여 소수를 구해주면 된다.

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다.

1) 2부터 N까지 모든 자연수를 나열

2) 남은 수 중 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3) 남은 수 중에서 i의 배수를 모두 제거한다.

4) 더이상 반복할 수 없을 때 까지 2, 3을 반복

시간 복잡도는 O(NloglogN)으로 선형 시간에 필적할 수준.

하지만 메모리를 많이 잡아먹는 단점이 있으니 잘 확인해보아야 한다.

수열을 묶어 최대의 값을 가져오는 문제 (그리드)

어떤 경우에 최대 값이 나올 수 있는가에 대해 생각 해보자.

입력 된 값들을 오름차순으로 정렬했을 때

앞부분에 [음수, 0, 1]에 해당하는 값이 나온다면 이 값을 우선 계산해주어야 한다.

0번째와 1번째의 값 비교

음수, 음수 -> 곱한다

음수, 0 -> 곱한다

음수, 양수 -> 더한다

이렇게 앞부분의 양수가 아닌 값( 1 제외 )을 없애준 후

나머지는 뒤에서부터(큰 순서로) 2개씩 묶어 곱해주면 된다.

ex) -1 2 1 3일 경우

정렬하면 -1 1 2 3

-1과 2는 (음수, 양수)이기에 더해준다. -> 0

뒤에 2, 3을 묶어 곱해준다 -> 6

0 + 6 -> 6

n = int(input())
data = list(int(input()) for _ in range(n))
data.sort()

result = 0
while True:
    if len(data) == 0:
        break
    elif len(data) == 1:
        result += data.pop(0)
        break
    elif data[0] == 0 and len(data) >= 2:
        result += data.pop(0) + data.pop(0)
    elif data[0] < 0 and len(data) >= 2:
        tmp1 = data.pop(0)
        tmp2 = data.pop(0)
        if tmp2 < 0:
            result += tmp1 * tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 0:
            result += tmp1 + tmp2
        elif tmp2 > 0 and (len(data) + 2) % 2 == 1:
            data.insert(0, tmp2)
            data.insert(0, tmp1)
            tmp1 = data.pop()
            tmp2 = data.pop()
            result += tmp1 * tmp2

    elif len(data) >= 2:
        tmp1 = data.pop()
        tmp2 = data.pop()
        if tmp1 == tmp2 == 1:
            result += tmp1 + tmp2
        elif tmp1 == 1 or tmp2 == 1:
            result += tmp1 + tmp2
        else:
            result += tmp1 * tmp2
print(result)

입력값이 0 또는 1밖에 없으니 0이나 1중 하나를 선택하여 split 해준다.

1을 split 했다고 가정했을 때

0011100010 -> '00', '', '000', '', '0'

이 되는데 이때 전체 숫자 수 에서 ''의 수를 카운트해서 빼주면 된다.

이때 0011100010보다 1100011101이 더 작을수가 있기에

그 경우의 수를 생각하여준다.

s = input()
s2 = ''

for i in s:
    if i == '0':
      s2 += '1'
    else:
        s2 += '0'

a = s.split('1')
b = s2.split('1')
result = min((len(a) - a.count('')), (len(b) - b.count('')))
print(result)

n = int(input())
num = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
dict_data = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0
             , 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0
             , 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0}
data = []
for _ in range(n):
    data.append(input())
data = sorted(data, key=lambda x: len(x), reverse=True)

for i in data:
    for j in i:
        if dict_data[j] == 0:
            dict_data[j] = num.pop(0)

result = []
for i in data:
    tmp = ''
    for j in i:
        tmp += str(dict_data[j])
    result.append(int(tmp))
print(sum(result))

최초 코드

n = int(input())
num = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
dict_data = {'A': -1, 'B': -1, 'C': -1, 'D': -1, 'E': -1, 'F': -1, 'G': -1, 'H': -1, 'I': -1, 'J': -1
             , 'K': -1, 'L': -1, 'M': -1, 'N': -1, 'O': -1, 'P': -1, 'Q': -1, 'R': -1, 'S': -1, 'T': -1, 'U': -1
             , 'V': -1, 'W': -1, 'X': -1, 'Y': -1, 'Z': -1, '!': 0}
data = []
for _ in range(n):
    data.append(input())
data = sorted(data, key=lambda x: len(x), reverse=True)

max_len = len(data[0])


for i in range(len(data)):
    if len(data[i]) != max_len:
        tmp = max_len - len(data[i])
        for _ in range(tmp):
            data[i] = '!' + data[i]

for i in range(max_len):
    for j in range(len(data)):
        if data[j][i] != '!':
            if dict_data[data[j][i]] == -1:
                dict_data[data[j][i]] = num.pop(0)

result = 0
for i in range(max_len):
    for j in range(len(data)):
        print(dict_data[data[j][i]] * (10 ** (max_len - i - 1)))
        result += dict_data[data[j][i]] * (10 ** (max_len - i - 1))
print(result)

두번째 코드

n = int(input())
result = 0
num = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
dict_data = {'A': 0, 'B': 0, 'C': 0, 'D': 0, 'E': 0, 'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0
             , 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0, 'P': 0, 'Q': 0, 'R': 0, 'S': 0, 'T': 0, 'U': 0
             , 'V': 0, 'W': 0, 'X': 0, 'Y': 0, 'Z': 0, '!': 0}
data = []
for _ in range(n):
    data.append(input())
data = sorted(data, key=lambda x: len(x), reverse=True)
max_len = len(data[0])

for i in range(len(data)):
    if len(data[i]) != max_len:
        tmp = max_len - len(data[i])
        for _ in range(tmp):
            data[i] = '!' + data[i]

for i in range(len(data)):
    for j in range(max_len):
        dict_data[data[i][j]] += (10 ** (max_len - j - 1))

dict_data['!'] = 0
weights = []
for i in dict_data.values():
    if i != 0:
        weights.append(i)
weights.sort(reverse= True)

for i in weights:
    result += i * num.pop(0)
print(result)

최종 코드

매우 고단했던 문제.. 주어진 문자의 각 자리수를 맞추어

해당 자리수에 맞게 차례로 큰 숫자부터 부여하며 동시에 연산하려 했으나, 

abb

bb

bb

bb

bb

bb

bb

bb

등의 input에 에러가 발생된다.

따라서 코드를 아예 전환하여 각 알파벳별로 가중치를 두었다(자리의 수에 따라)

그 가중치를 기준으로 큰 숫자부터 부여하여 계산하니 해결되었다.

문제를 보고 풀이를 도출할 수 있는 사고력을 길러야 한다는 생각이 들었다.

배움이 모자라니 시야가 좁아진다.

다양한 풀이와 더 나은 코드를 위해서는 더 열심히 노력해야한다.

풀었다는 사실에 안주하지 말자. 더 나은 코드로 다시 한번 풀어 내 것으로 만들자.