20200229 알고리즘

1. 회문 문자열 검사

N개의 문자열 데이터를 입력받아 앞에서 읽을 때나 뒤에서 읽을 때나 같은 경우(회문 문자열) 이면 YES를 출력하고 회문 문자열이 아니면 NO를 출력하는 프로그램을 작성한다. 단 회문을 검사할 때 대소문자를 구분하지 않습니다.

▣ 입력설명 첫 줄에 정수 N(1<=N<=20)이 주어지고, 그 다음 줄부터 N개의 단어가 입력된다. 각 단어의 길이는 100을 넘지 않는다.

▣ 출력설명 각 줄에 해당 문자열의 결과를 YES 또는 NO로 출력한다.

▣ 입력예제 1

5
level
moon
abcba
soon
gooG

▣ 출력예제 1

#1 YES
#2 NO
#3 YES
#4 NO 
#5 YES

Solution

import sys
sys.stdin = open("input11.txt", "rt")
n = int(input())

for i in range(n):
    tmp = input().upper()
    size = len(tmp)
    for j in range(size//2):
        if tmp[j] != tmp[-1-j]: # -1로 뒤 부터 인덱스 접근.
            print('#%d NO' %(i+1))
            break
    else:
        print('#%d YES' %(i+1))

Solution2

import sys
sys.stdin = open("input11.txt", "rt")
n = int(input())

for i in range(n):
    tmp = input().upper()
    if tmp == tmp[::-1]:
      print('#%d NO' %(i+1))
    else:
      print('#%d YES' %(i+1))

tmp[::-1] : 문자열 reverse

2. 숫자만 추출

문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2h0er”에서 숫자만 추출하면 0, 0, 1, 2, 0이고 이것을 자연수를 만들면 120이 됩니다.즉첫자리0은자연수화할때무시합니다. 출력은120를출력하고,다음줄에120 의 약수의 개수를 출력하면 됩니다.

추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다.

▣ 입력설명 첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 50을 넘지 않습니다.

▣ 출력설명 첫 줄에 자연수를 출력하고, 두 번째 줄에 약수의 개수를 출력합니다.

▣ 입력예제 1

g0en2Ts8eSoft

▣ 출력예제 1

28 6

Solution

import sys
sys.stdin = open("input12.txt", "rt")

string = input()
res = 0
cnt = 0
for a in string:
    if a.isdecimal():
        res = res*10 + int(a)
        
for i in range(1, res+1):
    if res % i == 0:
        cnt += 1
print(res)
print(cnt)

isdigit : 문자열에 포함된 숫자 판별( 0~9포함 모든 숫자 제곱수도 판별한다. )

isdecimal: 문자열에 포함된 숫자중 0~9 만 판별

3. 카드 역배치

카드 역배치(정올 기출)

1부터 20까지 숫자가 하나씩 쓰인 20장의 카드가 아래 그림과 같이 오름차순으로 한 줄로 놓 여있다. 각 카드의 위치는 카드 위에 적힌 숫자와 같이 1부터 20까지로 나타낸다.

이제 여러분은 다음과 같은 규칙으로 카드의 위치를 바꾼다: 구간 [a, b] (단, 1 ≤ a ≤ b ≤ 20)가 주어지면 위치 a부터 위치 b까지의 카드를 현재의 역순으로 놓는다. 예를 들어, 현재 카드가 놓인 순서가 위의 그림과 같고 구간이 [5, 10]으로 주어진다면, 위치 5부터 위치 10까지의 카드 5, 6, 7, 8, 9, 10을 역순으로 하여 10, 9, 8, 7, 6, 5로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림과 같다.

이 상태에서 구간 [9, 13]이 다시 주어진다면, 위치 9부터 위치 13까지의 카드 6, 5, 11, 12, 13을 역순으로 하여 13, 12, 11, 5, 6으로 놓는다. 이제 전체 카드가 놓인 순서는 아래 그림 과 같다.

오름차순으로 한 줄로 놓여있는 20장의 카드에 대해 10개의 구간이 주어지면, 주어진 구간의 순서대로 위의 규칙에 따라 순서를 뒤집는 작업을 연속해서 처리한 뒤 마지막 카드들의 배치 를 구하는 프로그램을 작성하시오.

▣ 입력설명 총 10개의 줄에 걸쳐 한 줄에 하나씩 10개의 구간이 주어진다. i번째 줄에는 i번째 구간의 시 작 위치 ai와 끝 위치 bi가 차례대로 주어진다. 이때 두 값의 범위는 1 ≤ ai ≤ bi ≤ 20이다.

▣ 출력설명 1부터 20까지 오름차순으로 놓인 카드들에 대해, 입력으로 주어진 10개의 구간 순서대로 뒤집 는 작업을 했을 때 마지막 카드들의 배치를 한 줄에 출력한다.

▣ 입력예제 1

5 10
9 13
1 2
3 4
5 6
1 2
3 4
5 6
1 20
1 20

▣ 출력예제 1 1 2 3 4 10 9 8 7 13 12 11 5 6 14 15 16 17 18 19 20

Solution

import sys
sys.stdin = open("input13.txt", "rt")
res = list(range(21)) 

for _ in range(10):
    p, q = map(int, input().split())
    for i in range((q-p+1)//2):
        res[p+i], res[q-i] = res[q-i], res[p+i]
res.pop(0)
for a in res:
    print(a, end=' ')

• list(range(number)): 0 ~ number를 원소로 갖는 리스트 생성
• _ : 반복문에서 변수 대입에 소모하는 수행시간 배제
• a, b = b, a : 값 교환에 자주 사용 됌
• list.pop(0) : pop 함수는 인자를 0으로 받으면 첫번째 원소를 pop

Solution2

res = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

for i in range(10):
    p, q = map(int, input().split())
    tmp = res[p-1:q]
    tmp = tmp[::-1]
    res = res[0:p-1] + tmp + res[q:]

for a in res:
    print(a, end=' ')

4. 두 리스트 합치기

오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로 그램을 작성하세요.

▣ 입력설명 첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다. 세 번째 줄에 두 번째 리스트의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어집니다. 각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

▣ 출력설명 오름차순으로 정렬된 리스트를 출력합니다.

▣ 입력예제 1

3
135
5
2 3 6 7 9

▣ 출력예제 1

1 2 3 3 5 6 7 9

Solution

import sys
sys.stdin = open("input14.txt", "rt")

a = int(input())
list1 = list(map(int, input().split()))
b = int(input())
list2 = list(map(int, input().split()))

p1 = p2 = 0
res = []

while p1 < a and p2 < b:
    if list1[p1] >= list2[p2]:
        res.append(list2[p2])
        p2 += 1
    else:
        res.append(list1[p1])
        p1 += 1
if p1 < a:
    res = res + list1[p1:]
else:
    res = res + list2[p2:]

for x in c:
  print(x, end=' ')

• sort() 함수를 사용해서 푸는 문제 아님!

  • sort() 함수 수행시간은 : nlogn
  • 퀵소트도 nlogn

5. 수들의 합

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

▣ 입력설명 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

▣ 출력설명 첫째 줄에 경우의 수를 출력한다.

▣ 입력예제 1

8 3 
1 2 1 3 1 1 1 2

▣ 출력예제 1

5

Solution

import sys
sys.stdin = open("input15.txt", "rt")
n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
lt = 0
rt = 1
tot = a[0]

while True:
    if tot < m:
        if rt < n:
            tot += a[rt]
            rt += 1
        else:
            break
    elif tot == m:
        cnt += 1
        tot -= a[lt]
        lt += 1
    else:
        tot -= a[lt]
        lt += 1

Solution2

import sys
sys.stdin = open("input15.txt", "rt")

n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0

for i in range(1, n):
    start = 0
    while start + i < n+1:
        tmp = sum(a[start : start+i])
        if tmp == k:
            cnt += 1
        start += 1
print(cnt)