[TIL]20210729

알고리즘

1934 (백준)

from math import gcd

num=int(input())
for _ in range(num):
  n,m = map(int, input().split())
  print(n*m//gcd(n, m))

유클리드 호제법 (a*b/최대공약수)을 이용한다.

18245 (백준)

풀이 1번
while 1:
    inp = input()

    if inp == 'Was it a cat I saw?':
        break
    a=1
    print(inp[::a+1])
풀이 2번
a = 1

while 1:
    inp = input()

    if inp == 'Was it a cat I saw?':
        break
    for i in range(0, len(inp), a + 1):
        print(inp[i], end="")
    print()
    a += 1

[a:b:c] 에서 a는 시작, b는 끝, c는 간격이다. 이때 c는 조작이 가능하다.

17502 (백준)

num = int(input())
str = list(input())
for i in range(num):
    if str[i]=='?' and str[-(i+1)]=='?':
        str[i]='a'
        str[-(i + 1)]='a'
    if str[i] != str[-(i + 1)]:
        if str[i] == '?':
            str[i] = str[-(i + 1)]
        else:
            str[-(i + 1)] = str[i]
print(''.join(str))

여기서 핵심은 str을 인풋받을때 List로 받는 것이다. str 타입으로 받으면 리스트이기때문에 인덱스 접근은 가능하지만 수정은 불가능해서 자리에 맞는 값으로 바꿀려면 매우 귀찮아질거같아서 애초부터 리스트로 받고 나중에 join을 이용해 합쳤다!

3943 (백준)

시간초과.

cnt = int(input())
for _ in range(cnt):
    i = 0
    num = [0 for i in range(500)]
    inp = int(input())
    num[0] = inp

    while num[i] != 1:
        if int(num[i]) % 2 == 0:
            num[i + 1] = int(num[i]) / 2
        else:
            num[i + 1] = int(num[i]) * 3 + 1
        i += 1

    num.sort(reverse=True)
    print(num[0])

정답

1번. 
import sys
cnt = int(sys.stdin.readline())
for _ in range(cnt):
    i = 0
    num = [0 for i in range(500)]
    inp = int(int(sys.stdin.readline()))
    num[0] = inp

    while num[i] != 1:
        if int(num[i]) % 2 == 0:
            num[i + 1] = int(num[i]) / 2
        else:
            num[i + 1] = int(num[i]) * 3 + 1
        i += 1

    num.sort(reverse=True)
    print(num[0])

2번.
import sys

cnt = int(sys.stdin.readline())
for _ in range(cnt):
    i = 0
    num = []
    inp = int(int(sys.stdin.readline()))

    while 1:
        if 1 in num:
            break
        num.append(inp)
        if inp % 2 == 0:
            inp //= 2
        else:
            inp = inp * 3 + 1
    print(max(num))

시간초과때문에 input 대신 sys.stdin.readline()를 쓰고 제출도 pypy로 했다.

10989 (백준)

오답

import sys
num=int(sys.stdin.readline())
c = []

for _ in range(num):
    c.append(int(sys.stdin.readline()))

for i in sorted(c):
    sys.stdout.write(str(i) + '\n')

조금씩 수정하면서 5번정도 제출했지만 모두 메모리 초과가 떠서 인터넷의 도움을 받았다.

import sys
n = int(sys.stdin.readline())
b = [0] * 10001
for i in range(n):
    b[int(sys.stdin.readline())] += 1
for i in range(10001):
    if b[i] != 0:
        for j in range(b[i]):
            print(i)

어떤차이가 있는지 모르겠어서 백준에 질문을 남겨 이유를 들었다.
입력되는 횟수를 카운트하는 counting sort라는 알고리즘이라고 한다.
리스트를 이용한 시간복잡도는 O(n)이지만 일반적인 정렬은 O(n log n)이다.