[구름톤 챌린지] 2주차 학습 일기 모음(1)

이번 주에는 기숙사 입사 때문에 너무 바빠서... 목/금 문제는 제대로 풀지 못하고 제출만 했다. 시간 내서 풀어봐야겠다...

 

1. 문자열 나누기

from itertools import combinations

# 입력 받기
N = int(input())
S = input()

# 조합으로 모든 부분문자열 구하기
cnt = [i for i in range(N)]
cnt_comb = list(combinations(cnt, 3))
str_comb = []
for i in cnt_comb:
  comb = [S[i[0]:i[1]], S[i[1]:i[2]], S[i[2]:]]
  if "".join(comb) == S:
    str_comb.append(comb)

# 모든 부분문자열 기반으로 P 구하기
P = sorted(set(sum(str_comb, []))) # 이중 리스트을 flatten하는 방법 중 하나: sum

# 점수 계산하기
score = []
for i in str_comb:
  score.append(P.index(i[0]) + P.index(i[1]) + P.index(i[2]) + 3) # X번째 보정을 위해 3 더해줌

# 결과 출력
print(max(score))

처음 문제를 읽었을 때는 어떻게 풀어야 하지...하는 생각이 들었다. 조합으로 구할 수 있는 경우의 '개수'가 아니라 그 모든 경우의 '값'을 구해야 했기 때문이다. 그래도 조금 시간을 들여 생각해보니, 인덱스를 통해 조합으로 수열을 구하면, 그 수열을 인덱스로 여기고 모든 부분문자열을 만들어낼 수 있었다.

그리고 이중 리스트를 1차원 리스트로 만드는 방법을 처음 배웠는데, 다름 아닌 sum이었다. 다른 방법은 for문을 돌아야 한다든지 하는 번거로움이 있었는데, 이렇게 간단하게 flatten할 수 있다는 걸 알게 되어 새롭고 파이썬에 다시 한 번 놀랐다.

 

2. 구름 찾기 신발

# DFS
dy = (-1, -1, -1, 1, 1, 1, 0, 0)
dx = (-1, 0, 1, -1, 0, 1, -1, 1)

def dfs(y, x):
  for i in range(8):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= ny < N and 0 <= nx < N:
      if not visited[ny][nx] and board[ny][nx] == 1:
        visited[y][x] += 1
        
# 입력 받기
board = []
N, K = map(int, input().split(" "))
for _ in range(N):
  *row, = map(int, input().split(" "))
  board.append(row)

# 실행
visited = [[0] * N for _ in range(N)]
for i in range(N):
  for j in range(N):
    if not visited[i][j] and board[i][j] == 0:
      dfs(i, j)
    
print(sum(visited, []).count(K))

DFS, BFS... 이론으로만 알고 있지 실제 코드로 구현한 경험은 많지 않아서 여러 블로그 글을 많이 참고했다. 주위 8칸을 탐색해야 한다는 게 선뜻 코드로 생각나지 않았는데, 이런 dx, dy 증가량 방식으로 구현할 수 있다는 점이 신기했다. 이 코드는 머릿속에 확실히 담아둬야겠다...!

 

나머지 3문제는... 사실 수요일 문제만 풀고 목금 문제는 답안만 확인했다ㅠㅠ 수요일 문제라도 올려놔야겠다.