say repository

# 3085

import sys
n = int(sys.stdin.readline())
arr = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer = 0

# 완전 탐색
def check(array):
    max_len = 1 # 함수의 리턴 값 -> 가장 긴 최대 길이
    for i in range(n):
        # 열 비교
        cnt = 1 # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[i][j] == arr[i][j-1]:
                cnt += 1
            else: # 인접한 사탕 중 다른 색 나오면 cnt 초기화
                cnt = 1
            max_len = max(max_len, cnt) # max_len 갱신
        
        # 행 비교
        cnt = 1  # 같은 색인 최대 길이
        for j in range(1,n):
            if arr[j][i] == arr[j-1][i]:
                cnt += 1
            else:
                cnt = 1
            max_len = max(max_len, cnt)  # max_len 갱신
    return max_len

# 인접하고 색 다른 두 칸 고르고 완탐 호출
for i in range(n):
    for j in range(n):
        if j+1<n: # 인접한 열 끼리 비교 후 교체
            if arr[i][j] != arr[i][j+1]:
                arr[i][j],arr[i][j+1] = arr[i][j+1], arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer,tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i][j + 1] = arr[i][j + 1], arr[i][j]

        if i+1<n: # 인접한 행 끼리 비교 후 교체
            if arr[i][j] != arr[i+1][j]:
                arr[i][j], arr[i + 1][j] = arr[i + 1][j],arr[i][j]
                # 완전탐색 수행
                tmp = check(arr)
                # 정답과 완탐 CNT 비교
                answer = max(answer, tmp)
                # 교체 한 것 다시 원래대로 돌려놓기 ( 모든 경우의수 비교해야함)
                arr[i][j], arr[i + 1][j] = arr[i + 1][j], arr[i][j]
print(answer)

풀이

보드의 크기 N이 주어진다. (3 ≤ N ≤ 50) -> 완전 탐색 가능하다.

1. 색이 다른 인접한 두 사탕 선택 후 교체

2. 교체한 배열에서 같은 사탕 색이 있는 (행 또는 열) 최대 길이 구하기

3. 교체한 사탕 다시 제자리로 위치시키고 다음 인접한 사탕 교체 후 완전탐색 반복

계속 교체할 사탕 2개 선택해서 자리 바꾸고 완탐으로 최대 길이 구하고 리턴 시켜서

answer 값을 max 값으로 갱신시킨다.

이 문제 괜찮은 것 같다.

나중에 다시 풀어보자.

메타문자

원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자

. ^ $ * + ? { } [ ] \ | (

문자 클래스 [ ]

[abc] 라면 "a,b,c" 중 한 개의 문자와 매치

[a-c] 가 [abc]랑 같다. 

• [a-zA-Z] : 알파벳 모두
• [0-9] : 숫자
• [^0-9] : 숫자 아닌 문자만

자주 사용하는 문자 클래스

• \d - 숫자와 매치, [0-9] 와 같음
• \D -  숫자 아닌 것과 매치, [^0-9]
• \s - whitespace 문자와 매치, [ \t\n\r\f\v] 와 같음
• \S - whitespace 문자가 아닌 것과 매치
• \w - 문자 + 숫자와 매치 [a-zA-Z0-9] 와 같음

Dot(.)

줄바꿈 문자인 \n 을 제외한 모든 문자와 매치됨.

a.b
# "a+ 모든 문자 + b"

a와 b라는 문자 사이에 어떤 문자가 들어와도 매치된다.

반복

*,  +,  {m,n}, ?

# a가 0부터 무한번 반복 가능
ca*t

# a가 1부터 무한번 반복 가능
ca+t

# 반복 ({m,n},?)

# a 2번 반드시 반복
ca{2}t
# a 2~5번 반복
ca{2,5}t
# {0,1} 반복, ? : 있어도 되고 없어도 된다.
ca?t

re 모듈

import re
p = re.compile('ab*')

정규식 표현을 컴파일해 돌려주는 객체 p를 이용해 문자열 검색에 사용한다.

정규식을 이용한 문자열 검색

• match() : 문자열의 처음부터 정규식과 매치되는지 조사
• search() : 문자열 전체를 검색해 정규식과 매치되는지 조사
• findall() : 정규식과 매치되는 모든 문자열을 리스트로 돌려줌
• finditer() : 정규식과 매치되는 모든 문자열을 반복 가능한 객체로 돌려줌

# 11724
import sys
sys.setrecursionlimit(10000)
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
cnt = 0
for _ in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
# print(graph)

def dfs(node):
    visited[node] = 1
    for i in graph[node]:
        if not visited[i]:
            dfs(i)

for i in range(1,n+1):
    if not visited[i]:
        dfs(i)
        cnt += 1
print(cnt)

풀이 2 (BFS)

# 11724
import sys
# sys.setrecursionlimit(10000)
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
cnt = 0
for _ in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
# print(graph)

def bfs(graph, node, visited):
    visited[node] = 1
    q = deque([node])
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1

for i in range(1,n+1):
    if not visited[i]:
        bfs(graph, i, visited)
        cnt += 1
print(cnt)

https://programmers.co.kr/learn/courses/30/lessons/12912

출처 : 프로그래머스

풀이 1

def solution(a, b):
    answer = 0
    if a<=b:
        answer = sum(range(a,b+1))
    else:
        answer = sum(range(b,a+1))
    return answer

풀이 2

def solution(a, b):
    answer = (abs(a-b)+1)*(a+b)//2
    return answer

수열에서 합 공식을 사용하면 된다.

n(a+l)//2 -> n 은 항 개수, a는 첫 항, l은 마지막 항

https://programmers.co.kr/learn/courses/30/lessons/1845

출처 : 프로그래머스

def solution(nums):
    answer = 0
    n = len(nums)//2
    set_n = len(list(set(nums)))

    if n > set_n:
        answer = set_n
    else:
        answer = n
    return answer

풀이

nums//2 가 set(nums)의 길이보다 크면 set(nums)

작으면 nums//2가 되어야한다.

이는 주어진 테스트케이스를 손코딩해보면 알 수 있다.

https://programmers.co.kr/learn/courses/30/lessons/42889

def solution(N, stages):
    answer = {}
    cntplayer = len(stages)
    
    # 각 스테이지별 실패율 딕셔너리에 저장
    for i in range(1,N+1):
        if cntplayer != 0:
            answer[i] = stages.count(i) /cntplayer # 실패율
            cntplayer -= stages.count(i)
        else: # 스테이지 도달한 유저 없는 경우 실패율 0
            answer[i] = 0
        
    return sorted(answer,key = lambda x:-answer[x])

풀이

1부터 N까지의 스테이지 도달한 개수를 구하고 그 개수를 계속 제외해서 다음 실패율을 구한다.

구한 실패율을 answer 딕셔너리에 넣고, 

실패율이 큰 순서대로 정렬한다.

https://programmers.co.kr/learn/courses/30/lessons/42746#

출처 : 프로그래머스

def solution(numbers):
    numbers = list(map(str,numbers)) # string 리스트로 변경
    numbers.sort(key = lambda x:x*3,reverse = True) 
    # print(numbers)
    return str(int(''.join(numbers)))