★BF Intermediate I - 14 Solved★

★ 1436 영화감독 숌 ★

 

N = int(input())
cnt = 0
start = 666

while 1:
    if '666' in str(start):
        cnt += 1
        if N == cnt:
            print(start)
            break        
        start+=1
    else:
        start+=1

 

🧕🏼 말 그대로 brutal하게 일일이 모든 경우의 수에서 666 포함 여부를 따지는 문제 

→ 최소한의 시간 단축을 위해 break를 넣었고, 666부터 시작하게 코드 설정

 

🧕🏼 위의 풀이는 ①cnt 변수를 따로 만들어 1부터 추가하며 체크하는 구조이나, 아래의 풀이는 ②N 자체에서 1씩 감소하며 체크하는 구조
※ while N 풀이가 신박해서 가져왔음 ※

N = int(input())
cnt = 0
start = 665

while N:
    start += 1
    if '666' in str(start):
        N -= 1
print(start)

 

(🧕🏼 *참고) 각각의 모든 경우의 수를 만들어 brute-force의 범위를 최소한으로 아래의 풀이와 같이 만들 수도 있다.)

import sys

N = int( sys.stdin.readline() )

num_list = [0] * 10000
cnt, num_cnt = 0, 0

# 5666, 6660~6669, 7666
# 65666, 66600~66699, 67666
# 665666, 666000~666999, 667666
# 6665666, 6660000~6669999, 6667666
while(1) :
    num = int( str(num_cnt) + "666" )

    if num_cnt % 10000 == 6666 :
        for i in range(10000) :
            num_list[cnt] = (num-6666) + i
            cnt += 1
            if cnt == N :
                break
    elif num_cnt % 1000 == 666 :
        for i in range(1000) :
            num_list[cnt] = (num-666) + i
            cnt += 1
            if cnt == N :
                break
    elif num_cnt % 100 == 66 :
        for i in range(100) :
            num_list[cnt] = (num-66) + i
            cnt += 1
            if cnt == N :
                break
    elif num_cnt % 10 == 6 :
        for i in range(10) :
            num_list[cnt] = (num-6) + i
            cnt += 1
            if cnt == N :
                break
    else :
        num_list[cnt] = num
        cnt += 1
    
    if cnt == N :
        print(num_list[cnt-1])
        break

    num_cnt += 1

---

★ 4673 셀프 넘버 ★

 

🧕🏼 brute-force 문제로 모든 숫자를 d(n)을 돌려 d(n)에 해당되지 않는 셀프 넘버를 일일이 모두 출력하는 문제

 

🧕🏼 list vs. set

→ d(n)의 결과를 어떤 자료형에 저장하는가에 따라 실행시간이 천차만별이 된다.

→ 최종적으로 in 연산자로 설정한 자료형에 원하는 데이터가 있는 지 확인해야 하기 때문에 중요

① list의 in 연산자 - 시간복잡도 $O(n)$

② set의 in 연산자 - 시간복잡도 $O(1)$

→ list과 tuple은 하나하나 데이터를 확인해야 하므로 in 연산자에 $O(N)$이라는 시간복잡도가 걸리지만, set과 dictionary는 hash 구조로 평균 $O(1)$ time complexity

def d(n):
    r=n
    for i in list(str(n)):r+=int(i) 
    return r
s=set()
for n in range(1,10001):s.add(d(n))
for n in range(1,10001):
    if n not in s:print(n)

 

 

→ 소요된 시간이 천차만별! set이 훨씬 더 빠르다

---

★ 7568 덩치 ★

 

N = int(input())
lst = []

for _ in range(N): #2 ≤ N ≤ 50
    x, y = map(int, input().split())
    lst.append((x,y)) #O(1)

for human in lst: #10 ≤ x, y ≤ 200 #O(n)
    me = human
    grade = 1

    for others in lst: #O(n)
        if others[0] > me[0] and others[1] > me[1]:
            grade += 1
    
    print(grade)

 

🧕🏼 각각 모든 사람들을 돌면서 나보다 키와 몸무게가 모두 크다면 1씩 추가해 최종 합한 결과인 등수를 각 인원별로 쭉 출력해주면 끝!

---

★ 8892 팰린드롬 ★

 

① itertools의 combinations를 활용해 가능한 두 word pair를 모두 구하고, 앞으로나 뒤로나 합쳐서 palindrome인지 확인하는 code

from itertools import combinations
import sys
input=sys.stdin.readline
def palindrome(word1, word2):
    n1=word1+word2
    n2=word2+word1
    if n1 == n1[::-1]:return n1    
    elif n2 == n2[::-1]:return n2
    else:return '0'

for _ in range(int(input())):
    cnt = 0
    words = [input().rstrip() for _ in range(int(input()))]
    pairs = list(combinations(words, 2))
    for pair in pairs:
        res = palindrome(pair[0], pair[1])
        if res.isdigit():cnt += 1
        else:
            print(res)
            break
    if cnt == len(pairs):
        print(0)

 

② 두 for문을 돌면서 각각의 index를 확인하며 indexing으로 각 word를 합친 결과가 palindrome인지 확인하는 code

import sys

def isPalindrome(word_a, word_b):
  word = word_a + word_b
  if word == word[::-1]:
    print(word)
    sys.exit(0)

if __name__ == "__main__":
  t = int(input())

  for _ in range(t):
    k = int(input())
    words = [sys.stdin.readline().rstrip() for _ in range(k)]

    for i in range(k-1):
      for j in range(i+1, k):
        isPalindrome(words[i], words[j])
        isPalindrome(words[j], words[i])
        
    print("0")

 

 

---

★ 1065 한수 ★

 

N=int(input())
if N<100:print(N)
else:
    cnt=99
    for i in range(100,N+1):
        l=list(map(int,str(i)))
        if (l[0]-l[1])==(l[1]-l[2]):cnt+=1
    print(cnt)

 

🧕🏼 100미만의 수는 모두 한수에 해당하고, 100이상일 경우 직접 등차수열인지 확인해 일일이 개수 1씩 더해주는 brute-force 전형적인 유형

---

★ 1018 체스판 다시 칠하기 ★

 

import sys
input = sys.stdin.readline

M,N=map(int,input().split())

chess = []

row1 = ['W','B','W','B','W','B','W','B']
row2 = ['B','W','B','W','B','W','B','W']
cmp1 = [row1,row2,row1,row2,row1,row2,row1,row2]
cmp2 = [row2,row1,row2,row1,row2,row1,row2,row1]

min_l = []

for _ in range(M):
    chess.append(list(input()))

for a in range(M-7):
    for b in range(N-7):
        cnt1,cnt2=0,0
        your_chess = []
        for i in range(8):
            row = []
            for j in range(8):
                row.append(chess[a+i][b+j])
            your_chess.append(row)

        for i in range(8):
            for j in range(8):
                if your_chess[i][j] != cmp1[i][j]:
                    cnt1 += 1
                if your_chess[i][j] != cmp2[i][j]:
                    cnt2 += 1
        min_l.append(min(cnt1,cnt2))
print(min(min_l))

 

🧕🏼 2차원 배열 + 브루트 포스 유형

 

🧕🏼

① 먼저 비교해야될 cmp1과 cmp2 배열을 2차원 배열로 만들기

② 내 2차원 배열을 chess에 입력하기

③ M행 N열의 chess에서 여러 8x8 정사각형 크기의 chess별로 각각 나누어 비교를 해야 한다

→ 두 for문을 돌려 0~(M-8) / 0~(N-8)까지 정사각형 시작점을 각각 다르게 두어 각 정사각형 별로 cmp1과 cmp2끼리 비교

④ cmp1과 cmp2 비교한 것 중 최솟값 찾아 list에 넣어 최종적으로 list 최솟값 출력

---

★ 1051 숫자 정사각형 ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())

arr=[]

for _ in range(N):
    arr.append(list(map(int,input().rstrip())))

size=min(N,M) #initial square size
ans=0
flag=False

while 1:
    for i in range(N-size+1):
        for j in range(M-size+1):
            if arr[i][j] == arr[i+size-1][j] == arr[i][j+size-1] == arr[i+size-1][j+size-1]:
                ans = size*size
                flag=True
                break
        if flag: break
    size-=1
    if size==0:break
    if flag: break
print(ans)

 

🧕🏼 위 체스판 칠하기 문제와 똑같은 2차원 배열 + BF 문제 유형이다. i와 j 가로와 세로 index 범위를 주어진 size 정사각형에 맞게 range()문을 잘 세우고, 정사각형의 조건이 맞다면 flag 변수로 break문을 적절히 만든다.

 

🧕🏼 size가 0일 경우 index 오류가 생기므로 indexerror를 피하기 위해 break문 추가

 

🧕🏼 여러 break문을 설정해야 하는 유형!

---

★ 1120 문자열 ★

 

A,B=input().split()
ans=51
a,b=len(A),len(B)
cnt=b-a+1
for i in range(cnt):
    x=0
    y=0
    for j in range(i,i+a):
        if A[y]!=B[j]:
            x+=1
        y+=1
    ans=min(ans,x)
print(ans)

 

🧕🏼 문자열 B는 고정한 채로 문자열 A를 첫 위치부터 가능 끝 위치까지 반복문

: 차이가 최소가 되어야 하므로 A와 B간의 남은 자리는 모두 같게 설정

: 반복문 돌며 A와 B 사이의 차이 갯수 최솟값 update

 

🧕🏼 + 이 때 문자열 A의 index는 항상 0부터 시작함 주의

---

★ 1543 문서 검색 ★

 

paper=input()
word=input()

ans=0
j=0
while j<=(len(paper)-len(word)):
    if paper[j:j+len(word)] == word:
        ans+=1
        j+=len(word)
    else:
        j+=1
print(ans)

 

🧕🏼 일일이 word와 동일한 문자열 while문 돌면서 찾아주기

---

★ 1057 토너먼트 ★

 

* 풀이 1) 전체 라운드의 수를 log2로 구하고 각 라운드의 번호를 모은 2차원 list 구현. 라운드 진행하면서 list append. 번호가 같은 list에 있을 때까지 점검

import math,sys
n=int(math.log(100_000,2))
rounds=[[] for _ in range(n+1)]
N,a,b=map(int,input().split())
l=[i for i in range(1,N+1)]
rounds[0]=l
rnd=0
while 1:
    for i in range(0,len(rounds[rnd]),2):
        if i == len(rounds[rnd])-1: #홀수일 경우 마지막 번호는 자동 다음라운드 진출
            rounds[rnd+1].append(rounds[rnd][i])
        else:
            if rounds[rnd][i] not in [a,b] and rounds[rnd][i+1] not in [a,b]: #둘 다 없다면
                rounds[rnd+1].append(rounds[rnd][i])
            elif rounds[rnd][i] in [a,b] and rounds[rnd][i+1] in [a,b]: #둘 다 있다면 답 발견!
                print(rnd+1)
                sys.exit()
            elif rounds[rnd][i] in [a,b]: #앞 번호에 누군가 있다면 앞번호 올라가기
                rounds[rnd+1].append(rounds[rnd][i])
            else:#뒷 번호에 있다면 뒷번호 올라가기
                rounds[rnd+1].append(rounds[rnd][i+1])
    rnd+=1

 

* 풀이 2) 라운드가 진행되면서 지민과 한수의 번호가 (n+1)//2씩 변함. 서로 같아질 때 라운드 수 출력

N,a,b=map(int,input().split())
ans=0
while (a!=b):
    a,b=(a+1)//2,(b+1)//2
    ans+=1
print(ans)

두 수의 (n+1)//2 결과가 같다는 건 만난다는 뜻, 같지 않으면 만나지 않음

---

★ 1969 DNA ★

 

import sys
input = sys.stdin.readline

N,M=map(int,input().split())
freq=[[0,0,0,0] for _ in range(M)] #ACGT

for _ in range(N):
    DNA=input().rstrip()
    i=0
    for nct in list(DNA):
        idx='ACGT'.index(nct)
        freq[i][idx]+=1
        i+=1

HD=0
ans=[]
for freq_pair in freq:
    ans.append('ACGT'[freq_pair.index(max(freq_pair))])
    HD+=(N-max(freq_pair))
print(*ans,sep='')
print(HD)

 

🧕🏼 각 자리별 Hamming Distance의 합이 가장 작은 뉴클레오타이드는 최대빈도 뉴클레오타이드(사전순)

🧕🏼 Hamming Distance는 각 자리별 전체 뉴클레오타이드의 개수 - 최대빈도 뉴클레오타이드의 빈도수의 누적합

 

🧕🏼 문자열 ACGT(알파벳순)의 indexing

---

★ 23428 Painting Roofs ★

import sys
input=sys.stdin.readline

m,n=map(int,input().split())
a,b=0,0
arr=[]
for _ in range(m):
    arr.append(list(input().rstrip()))

for i in range(m):
    if i%2==0:
        flag=True
        for x in arr[i]:
            if flag: #'2'
                if x == '1': a+=1
                flag=False
            else:
                flag = True
                if x == '2': a+=1
    else:
        flag=True
        for x in arr[i]:
            if flag: 
                if x == '2': a+=1
                flag=False
            else:
                flag = True
                if x == '1': a+=1

for i in range(m):
    if i%2==0:
        flag=True
        for x in arr[i]:
            if flag: #'2'
                if x == '2': b+=1
                flag=False
            else:
                flag = True
                if x == '1': b+=1
    else:
        flag=True
        for x in arr[i]:
            if flag: 
                if x == '1': b+=1
                flag=False
            else:
                flag = True
                if x == '2': b+=1

print(min(a,b))

 

🧕🏼 1과 2가 번갈아 나오는 2가지 케이스의 무늬 각각에서 brute-force로 바꿔야 하는 개수 구하고, 두 케이스 중 최솟값 출력

---

★ 2993 세 부분 ★

import sys
input=sys.stdin.readline

word=input().rstrip()
ans=[]

for x in range(1,len(word)):
    for y in range(x+1,len(word)):
        str1,str2,str3=word[:x],word[x:y],word[y:]
        ans.append(str1[::-1]+str2[::-1]+str3[::-1])
print(sorted(ans)[0])

🧕🏼 세 부분으로 나올 수 있는 케이스를 직접 2중 for문으로 돌리면서 찾는다. 길이는 50보다 작거나 같으므로 충분히 제한 시간 내에 해결 가능. 알파벳 순서는 sorted() 함수로 한 번에 해결

---

★ 1251 단어 나누기 ★

🧕🏼 위 <2993 세 부분> 과 동일 문제

---