[구름톤 챌린지]블로그학습일기 2주차(1)

ego2·2023년 8월 24일

구름톤 챌린지

목록 보기

3/6

블록을 모아 성장한 나의 캐릭터,,, 1주차에는 공대생의 체크 셔츠와 노트북이였다면 조금 힙해져서 에어팟 맥스에 스타벅스 텀블러를 들고있다.~~(MZ 신입개발자인듯)~~

6일차 : 문자열 나누기

import sys
input = sys.stdin.readline

n = int(input())
s = input().strip()

p = set()
temp = []
for i in range(1, n-1):
    for j in range(i+1, n):
        s1, s2, s3 = s[:i], s[i:j], s[j:]
        p.add(s1)
        p.add(s2)
        p.add(s3)
        temp.append((s1, s2, s3))

p = sorted(list(p))

result = 0
for i in temp:
    sum1 = p.index(i[0]) + p.index(i[1]) + p.index(i[2]) + 3
    result = max(result, sum1)
print(result)

문자열을 입력받아 3개의 부분 분자열을 만든다(길이가 3인 부분집합)
예) abcd => {a,b,cd}, {a,bc, d}, {ab,c,d}

부분 문자열을 중복제거, 사전 순으로 정렬한다 (P)
예) a, ab, b, bc, c, cd, d

P와 1에서 구한 부분집합과 하나씩 비교하여 얻울 수 있는 최대 점수를 출력하라
예) {a,b,cd}이면 P에서 2번째 + 5번째 + 7번째 = 14이다.

정해 코드

from itertools import combinations

N = int(input())
S = input()

# 부분 문자열을 담을 P를 set()으로 선언합니다.
P = set()

# 공백의 번호를 담은 배열을 선언할게요.
blank = [i for i in range(1, N)]
# 공백 2개를 선택한 조합의 배열을 저장합니다.
comb = list(combinations(blank, 2))

# 현재 comb 배열의 각 원소는 위에서 언급한 (f, s) 꼴입니다. 변수의 개수를 맞추어 그대로 가져올게요.
for f, s in comb:
	# 부분 문자열로 쪼개어 P에 추가할게요.
	P.add(S[:f])
	P.add(S[f:s])
	P.add(S[s:])

# 구한 부분 문자열 집합을 list로 변환해줍니다.
P = list(P)

# 파이썬의 sort 함수는 문자열도 사전순으로 정렬이 가능합니다!
P.sort()

# 최대 점수를 저장할 변수를 선언할게요.
result = 0

# comb의 각 f, s에 대해 최대 점수를 완전탐색으로 찾아봅시다.
for f, s in comb:
	temp = 0

	# P에서 부분 문자열이 등장하는 위치를 찾습니다.
	# 이 때, 인덱스 + 1 을 해주어야 문제에서 말하는 점수가 됩니다.
	temp += P.index(S[:f]) + 1
	temp += P.index(S[f:s]) + 1
	temp += P.index(S[s:]) + 1

	result = max(result, temp)

# 답을 출력합니다!
print(result)

나는 문자열을 frist, second, 남은 문자열 3가지로 구분해 2중 for문으로 배열 슬라이싱 했다면, 정해 코드에서는 반복문 대신 조합을 사용해 범위를 지정했다.

문자열 S를 세 부분으로 나눈 결과를 각각 S[:f] , S[f:s] , S[s:]

{a, b, cd} 의 경우
f = 1, s = 2 입니다.

{a, bc, d} 의 경우
f = 1, s = 3 입니다.

{ab, c, d} 의 경우
f = 2, s = 3 입니다.

(f, s)쌍을 정리하면 (1, 2), (1,3), (2, 3) 즉, 3개의 숫자 1,2,3중 중복없이 2개씩 뽑는 경우의 수 조합이다.
=> 중복조합은 (1,1), (2,2), (3,3)을 허용함

7일차 : 구름 깃발 찾기

import sys

input = sys.stdin.readline


N, K = map(int, input().rstrip().split())

# 맵 입력 초기화
M = [list(map(int, input().split())) for _ in range(N)]

result = 0
for x in range(N):
    for y in range(N):
        # 구름이 없는 곳이면
        if M[x][y] == 0:
            count = 0
            # 상 하 좌 우 오른쪽아래, 오른쪽 위, 왼쪽 위, 왼쪽 아래
            for dx, dy in [(-1,0), (1,0), (0, -1), (0,1), (1,1),(-1,1),(-1,-1),(1, -1)]:
                nx = x + dx
                ny = y + dy
                # 인덱스 범위 체크, 구름이 있는지 체크
                if 0<= nx < N and 0<= ny < N and M[nx][ny] == 1:
                    count += 1

            if count == K:
                result += 1

print(result)

맵을 전체를 완전탐색으로 순회하면서 깃발을 놓을 수 있는곳을 찾아(값이 0이고 상,하,좌,우,대각선 구름이있는경우)
깃발의 값(상,하,좌,우,대각선의 구름의 갯수)를 세어 가장 깃발의 값이 큰값을 반환한다.

8방향으로 이동하고나서 배열의 인덱스 범위를 벗어나는지 체크, 그리고 이동한 곳이 구름을 가지고 있는지 체크한다.

정해코드


dy = [-1, -1, 0, 1, 1, 1, 0, -1]
dx = [0, -1, -1, -1, 0, 1, 1, 1]

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

matrix = []

for _ in range(N):
	row = list(input().split())
	matrix.append(row)

result = 0

for i in range(N):
	for j in range(N):
		if matrix[i][j] == "1":
			continue
		
		check = 0
		
		for k in range(8):
			y = i + dy[k]
			x = j + dx[k]

			if y < 0 or y >= N or x < 0 or x >= N:
				continue
			
			if matrix[y][x] == "1":
				check += 1

		if check == K:
			result += 1

print(result)

내정답과 비슷해 생략

8일차 : 통증

# ---------------------------------------------------------------
# 1차코드(시간초과)
#  n = 10억이라 제한 시간안안에 풀려면 더욱 간소한 코드를 사용해야한다.
# ---------------------------------------------------------------
# 통증 수치
N = int(input())

cnt = 0
while N:
    if N>= 14:
        cnt += 1
        N -= 14
    elif N>= 7:
        cnt += 1
        N -= 7
    else:
        cnt += N        
        N = 0

print(cnt)
# ---------------------------------------------------------------
# 구름톤 챌린지 테스트 케이스 오류 버그
# 아래의 코드의 시간복잡도 : O(1)
# ---------------------------------------------------------------
N = int(input())

result = 0
result += N//14
N %= 14
result += N//7
N %= 7
result += N//1

print(result)