MINJU's code story

https://school.programmers.co.kr/learn/courses/30/lessons/12904

실패한 코드

def solution(s):
    answer = 0
    new_s = s[::-1]
    
    j = 0
    for i in range(len(s)):
        if s[j] == new_s[i]:
            answer += 1
            j += 1

    return answer

성공한 코드

• 주어진 문자열을 순차적으로 뒤집으면서 new_s를 만든다
• 기존 문자열과 일치하는지 확인하고 일치하면 문자열 길이를 answer에 업데이트한다

def solution(s):
    answer = 0
    new_s = s[::-1]
    
    for i in range(len(s)):
        for j in range(len(s), i, -1):
            new_s = s[i:j]
            if new_s == new_s[::-1]:
                answer = max(answer, len(new_s))

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42627

• 처음엔 작업 시간을 기준으로 jobs를 오름차순 정렬하려고 함
• jobs.sort(key = lambda x : x[1])
• 하지만 이 경우 만약 작업 시간은 1초만 걸려도 작업 요청이 100초 뒤에 들어온 것이라면 앞에 요청들어온 다른 작업을 처리할 수 없음
• 그래서 현 시점에서 처리할 수 있는지를 따져본 후 작업을 heap에 저장하는 순서가 있어야 함
• 그리고 현 시점에서 처리할 수 있는 작업이 없을 때는 now 시간을 올려주는 코드도 필요

import heapq

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        # 처리할 작업이 있는 경우
        if len(heap) > 0: 
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
            
        # 처리할 작업이 없는 경우 다음 시간을 넘어감
        else: 
            now += 1
                
    return answer // len(jobs)

https://www.acmicpc.net/problem/10026

• 일반적인 BFS를 구해주고
• 기존 graph에서 모든 R을 G로 바꾼 뒤 다시 BFS 돌림

from collections import deque

N = int(input())
graph = []
for _ in range(N):
    graph.append(input())
visited = [[False] * N for _ in range(N)]
answer = [0] * 2

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

queue = deque()
def bfs(i,j,color):
    if visited[i][j]:
        return
    queue.append((i,j))
    visited[i][j] = True

    while(queue):
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue

            if not visited[nx][ny] and graph[nx][ny] == color:
                visited[nx][ny] = True
                queue.append((nx, ny))

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            answer[0] += 1
        bfs(i,j,graph[i][j])

for i in range(N):
    graph[i] = graph[i].replace('R', 'G')

visited = [[False] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            answer[1] += 1
        	bfs(i,j,graph[i][j])

        
for i in answer:
    print(i, end=' ')

https://school.programmers.co.kr/learn/courses/30/lessons/92334

def solution(id_list, report, k):
    rp_list = [[] for _ in range(len(id_list))]
    answer, rp_cnt = [0] * len(id_list), [0] * len(id_list)
    final_list = []

    for i in report:
        each_list = i.split()
        s = id_list.index(each_list[0])
        e = id_list.index(each_list[1])
        if e not in rp_list[s]:
            rp_cnt[e] += 1
            rp_list[s].append(e)
            
    for i in range(len(rp_cnt)):
        if rp_cnt[i] >= k:
            final_list.append(i)

    for idx in range(len(rp_list)):
        for i in rp_list[idx]:
            if i in final_list:
                answer[idx] += 1

    
    return answer

• reports를 만드는 방식에서 dict() 선언하는 법 배움
• set으로 효율적으로 중복 제거 : 한 사람이 동일 인물 지목하는 string 전체가 중복제거됨 (매우 참신!!)

def solution(id_list, report, k):
    answer = [0] * len(id_list)    
    reports = {x : 0 for x in id_list}

    for r in set(report):
        reports[r.split()[1]] += 1

    for r in set(report):
        if reports[r.split()[1]] >= k:
            answer[id_list.index(r.split()[0])] += 1

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/84512

• A, AA, AAA, AAAA, AAAAA 까지 w값을 증가시키다가 cnt가 5가 되면 dfs를 빠져나온다.
• 그러면 w가 AAAA인 상태에서 for문을 돌리게 되고, AAAA뒤에 차례대로 E,I,O,U가 붙는다.
• AAAAU까지 for문을 다 돌리고 나면 재귀를 빠져나와 이제는 w가 AAA인 상태에서 dfs를 수행한다.
• 이렇게 차례로 A가 맨 앞일 때, E가 맨 앞일 때... U가 맨 앞일 때 dfs를 수행한다.

def solution(word):
    answer = 0
    word_list = []
    words = 'AEIOU'
    
    def dfs(cnt, w):
        if cnt == 5:
            return 
        for i in range(len(words)):
            word_list.append(w + words[i])
            dfs(cnt+1, w + words[i])
            
    dfs(0,"")
    
    return word_list.index(word)+1

넘 어려웡 ㅜㅜㅜㅜ

https://www.acmicpc.net/problem/2468

• 수위마다 방문배열을 만들고 bfs 실행해야 함
• bfs를 새로 실행할 때마다 (새로운 블럭이 나타날 때마다) cnt를 1개씩 증가해주고, visited 배열도 새로 전달해줘야 함

from collections import deque

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max = max(max(graph))
result = 0

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

queue = deque()
def bfs(x,y,level,visited):
    visited[x][y] = True
    queue.append((x,y))

    while(queue):
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] > level and not visited[nx][ny]:
                    visited[nx][ny] = True	# 안 쓰면 시간초과 뜸
                    queue.append((nx, ny))    


for i in range(max):    # min~max로 하면 안 되고 0~max로 하면 통과
    visited = [[False] * N for _ in range(N)]
    cnt = 0
    for j in range(N):
        for k in range(N):
            if graph[j][k] > i and not visited[j][k]: 
                bfs(j, k, i, visited)
                cnt += 1
    
    if result < cnt:
        result = cnt
    

print(result)

https://www.acmicpc.net/problem/1525

• 2차원 배열 형태의 퍼즐을 문자열로 만들어준다는 것이 포인트!
• 0의 위치를 바꿔나가면서 새로 생성된 그래프를 또다시 문자열로 만들어주고 "123456780"에 해당하는지 비교해줘야 함.
• 2차원 배열에서의 x, y 좌표값은 문자열에서 index 값을 3으로 나눈 몫과 나머지로 구할 수 있음.

from collections import deque

graph = ""
for i in range(3):
    graph += "".join(list(input().split())) # 그래프를 문자열로 만들어준다 

queue = deque([graph])
visited = dict()    # key: 그래프, value: 해당 그래프를 만들기 위해 퍼즐을 옮긴 횟수 
dx = [1,-1,0,0]
dy = [0,0,-1,1]

def bfs():
    visited[graph] = 0

    while(queue):
        target = queue.popleft()

        if target == "123456780":
            return visited[target]
        
        idx = target.find("0")  # 그래프에서 빈 공간인 0의 위치
        x = idx // 3            # 2차원 배열일 때 빈 공간의 x 좌표
        y = idx % 3             # y 좌표

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < 3 and 0 <= ny < 3:
                n = nx * 3 + ny     # 0 주변의 퍼즐값 
                list_target = list(target) # 문자열 그래프를 리스트로 변환
                # swap
                # 빈 공간의 인덱스에 현재 좌표를 넣고 현재 좌표에 빈 공간의 인덱스 값을 넣는다.
                list_target[idx], list_target[n] = list_target[n], list_target[idx]
                new_target = "".join(list_target) # 리스트 퍼즐을 문자열로 변환

                # 현재 그래프 모양을 갖는 key 값이 없다면
                if not visited.get(new_target):
                    visited[new_target] = visited[target] + 1   # 횟수 갱신
                    queue.append(new_target)    # 탐색 추가

    # 탐색이 끝나도 정리된 상태가 안된다면 -1 리턴
    return -1

print(bfs())

https://school.programmers.co.kr/learn/courses/30/lessons/87946

• 던전 방문 순서의 모든 조합을 구해야하므로 itertools의 permutations 메소드를 이용해서 완전 탐색해준다.

from itertools import permutations
def solution(k, dungeons):
    answer = -1
    result = []
    
    for n_dungeons in permutations(dungeons): 
        cnt = 0
        power = k
        for i in range(0, len(dungeons)):
            if n_dungeons[i][0] <= power and n_dungeons[i][1] <= power:
                power -= n_dungeons[i][1]
                cnt += 1
        result.append(cnt)
    
    answer = max(result)
    
    return answer

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    
    for n_dungeons in permutations(dungeons): 
        cnt = 0
        power = k
        for i in range(0, len(dungeons)):
            if n_dungeons[i][0] <= power and n_dungeons[i][1] <= power:
                power -= n_dungeons[i][1]
                cnt += 1
        if cnt > answer:
            answer = cnt
    
    return answer

• 백트랙이라고 하는 것 같은데 dfs로 이 문제를 풀 때 dfs를 재귀호출하고 다시 visited 값을 초기화해주는 방법이다
• 결과적으로 permutations 함수를 쓴 것과 같이 모든 조합에 대해서 방문하게 된다

answer = 0
N = 0
visited = []


def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer