[TIL]20210814

알고리즘

11441 (백준)

시간초과

import sys

num=int(sys.stdin.readline())
inp=list(map(int,sys.stdin.readline().split()))
rannum=int(sys.stdin.readline())
for i in range(rannum):
    A,B=map(int,sys.stdin.readline().split())
    print(sum(inp[A-1:B]))

이 문제의 경우 prefix sum(구간합)을 미리 계산해놓고 필요할때 꺼내사용하는 문제이다. 위의 코드처럼하면 시간초과가 발생한다.

정답

import sys

num=int(sys.stdin.readline())
inp=list(map(int,sys.stdin.readline().split()))
rannum=int(sys.stdin.readline())
sum=[inp[0]]
for i in range(1,num):
    sum.append(sum[-1]+inp[i])
for _ in range(rannum):
    i, j = map(int, sys.stdin.readline().split())
    if i==1:
        print(sum[j-1])
    else:
        print(sum[j-1]-sum[i-2])

sum=[10, 30, 60, 100, 150] 로 이뤄져있다.

1676 (백준)

https://ko.numberempire.com/factorialcalculator.php
규칙성 찾기. 5!=120 10!=3628800 이다. 5마다 0이 증가. 그러나 5^2엔 00이 증가. 제곱이 될때마다 규칙이 다르다.

import sys
N=int(sys.stdin.readline())
print(N//5+N//25+N//125)

10815 (백준)

시간초과

import sys

Anum=int(sys.stdin.readline())
Alist=list(map(int,sys.stdin.readline().split()))
Bnum=int(sys.stdin.readline())
Blist=list(map(int,sys.stdin.readline().split()))
cc=[]
for i in range(Bnum):
    check=0
    for j in range(Anum):
        if Blist[i]==Alist[j]:
            check=1
    if check==1:
        cc.append("1")
    else:
        cc.append("0")

print(" ".join(cc))

정답

input()
n = set(map(int, input().split()))
input()
m = list(map(int, input().split()))
for i in m:
    if i in n:
        print(1, end=' ')
    else:
        print(0, end=' ')

set을 이용하면 해결이 쉬워진다.
어떤 값이 배열에 포함됬는지 확인하기위한 x in arr를 보면.
리스트는 구하는데 평균적으로 O(n)의 시간이 들지만 set은 O(1)의 시간이 든다.
m은 왜 여전히 list를 사용하냐면, set은 순서가 없기때문이다.

10773 (백준)

cnt=int(input())
su=[]
B=0
for j in range(cnt):
    A=int(input())
    if A==0:
        #pop
        su.pop()
    else:
        su.append(A)
    B=A
print(sum(su))

11719 (백준)

while True:
    try:
        print(input())
    except:
        break

1259 (백준)

while True:
    A=input()
    if A=="0":
        break
    else:
        if A[:]==A[::-1]:
            print("yes")
        else:
            print("no")

1236 (백준)

A,B=map(int,input().split())
board=[]
a,b=0,0
for _ in range(A):
    board.append(input())
for i in range(A):
    if "X" not in board[i]:
        a+=1
for j in range(B):
    if "X" not in [board[i][j] for i in range(A)]:
        b += 1
print(max(a,b))

코드 설명:
for i 로 시작하는 수식은 가로방향에 X가 없는지 파악,
for j 로 시작하는 수식은 세로방향에 X가 없는지 파악한다.
board[i][j] for i in range(A) 임으로 j는 고정된 상태에서 i값이 변경되면서 값을 찾아내는 방식을 이용한다. 까먹으면 다시 손코딩을 해보자.

자바

웹 백엔드를 배우기위해 필요한 자바를 공부해보자.

상수 선언

final int J처럼 상수를 선언하기 위해 final을 사용함. 또한, 상수는 대문자로 된 명사를 사용하는 것이 관례이다.
C언어는 const 사용함.