테크니션

https://www.acmicpc.net/problem/10988

level

1

baekjoon

0

문자를 입력받아 리스트로 만들고

리스트 0번과 -1번을 비교해서

두개가 같으면 pop으로 날리는 과정을 반복해서

입력받은 문자 길이가 홀수면 마지막에 길이가 1인 리스트가 남고

입력받은 문자 길이가 짝수면 마지막에 길이가 0인 리스트가 남는지 확인해서 결과를 출력하였다

import sys
str = list(sys.stdin.readline())[:-1]
for i in range(int(len(str)/2)):
    if str[0] == str[-1]:
      str.pop(0)
      str.pop(-1)
if len(str) ==len(str)%2:
  print(1)
else:
  print(0)

5
5
2
3
4
1

1
2
3
4
5

기본적 sort다

import sys
n = int(sys.stdin.readline())
t = []
for k in range(n):
    j = int(sys.stdin.readline())
    t.append(j)
    if k>0:
        for a in range(1, k+1):
            if t[-a] < t[-a-1]:
                temp = t[-a]
                t[-a]= t[-a-1]
                t[-a-1] = temp
for c in range(n):
    print(t[c])

swap 코드는 암기후 써먹는다

append를 하면 뒤로 붙어서 비교 연산을 뒤에서부터 마이너스를 붙여서 해야한다

마이너스로 연산할때는 range가 달라진다

0 1 2 3 4 ---> -5 -4 -3 -2 -1

range(k) --> range(1, k+1)

https://www.acmicpc.net/problem/11659

5 3
5 4 3 2 1
1 3
2 4
5 5

12
9
1

처음에 리스트의 sum으로 작성한 코드

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    ans = sum(m[(t[0]-1):(t[1])])
    print(ans)

결과 : 시간초과

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

시간복잡도는 O(nm)이 되서 시간 안에 통과가 불가능하다 

- 수정 

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    lllist = [0]*(n[0]+1)
    for k in range(1, n[0]+1):
        lllist[k] = lllist[k-1]+m[k-1]
    print(lllist[t[1]]-lllist[t[0]-1])

결과 : 시간초과

구간 합을 미리 구해놓지 않고 구간을 받을때마다 합을 새로 구해서 연산이 늘어났다

이미 m 리스트는 받았기 때문에 구간 합을 먼저 구해놓고 나서 

구간을 받을때 서치만 하는 방향으로 코드를 수정했다

import sys
n = list(map(int, sys.stdin.readline().split()))
m = list(map(int, sys.stdin.readline().split()))
lllist = [0]*(n[0]+1)
for k in range(1, n[0]+1):
    lllist[k] = lllist[k-1]+m[k-1]
for i in range(n[1]):
    t = list(map(int, sys.stdin.readline().split()))
    print(lllist[t[1]]-lllist[t[0]-1])

구간 합

[ a, b, c, d, e] 리스트가 있으면

누적 합의 리스트는

[0, a, ab, abc, abcd, abcde] 

길이가 1개 늘어난 리스트가 된다

2번부터 4번까지 bcd 합을 구하고 싶으면

미리 구해놓은 구간합 리스트에서

abcd - a 의 값을 찾는 방법으로 구할수 있다

1번부터 3번까지 abc 합은 

abc는 abc - 0 의 값이 어디있는지 연산이 필요없이 찾기만 하면 된다