• places의 원소는 P,O,X로 이루어진 문자열입니다.
• places 원소의 길이(대기실 가로 길이) = 5
• P는 응시자가 앉아있는 자리를 의미합니다.
• O는 빈 테이블을 의미합니다.
• X는 파티션을 의미합니다.

<코드>

from collections import deque

def bfs(p):
    start=[]

    for i in range(5):
        for j in range(5):
            if p[i][j]=='P':
                start.append([i,j])
    for s in start:
        queue=deque([s])
        visited=[[0]*5 for i in range(5)]
        distance=[[0]*5 for i in range(5)]
        visited[s[0]][s[1]]=1

        while queue:
            y,x=queue.popleft()
            dx=[-1,1,0,0]
            dy=[0,0,-1,1]

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

                if 0<=nx<5 and 0<=ny<5 and visited[ny][nx]==0:
                    if p[ny][nx]=='O':
                        queue.append([ny,nx])
                        visited[ny][nx]=1
                        distance[ny][nx]=distance[y][x]+1

                    if p[ny][nx]=='P' and distance[y][x]<=1:
                        return 0
    return 1

def solution(places):
    answer = []
    for i in places:
        answer.append(bfs(i))

    return answer

• "U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
• "D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
• "C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
• "Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

<코드>

def solution(n, k, cmd):
    answer = ''

    linkedList={i: [i-1,i+1] for i in range(1, n+1)}
    OX=["O" for i in range(1,n+1)]
    stack=[]
    k+=1
    print(linkedList)
    for c in cmd:
        if c[0]=='D':
            for _ in range(int(c[2:])):
                k=linkedList[k][1]
        elif c[0]=='U':
            for _ in range(int(c[2:])):
                k=linkedList[k][0]
        elif c[0]=='C':
            prev,next=linkedList[k]
            stack.append([prev,next,k])
            OX[k-1]="X"

            if next==n+1:
                k=linkedList[k][0]
            else:
                k=linkedList[k][1]

            if prev==0:
                linkedList[next][0]=prev
            elif next==n+1:
                linkedList[prev][1]=next
            else:
                linkedList[prev][1]=next
                linkedList[next][0]=prev
        elif c[0]=='Z':
            prev,next,now=stack.pop()
            OX[now-1]="O"

            if prev==0:
                linkedList[next][0]=now
            elif next==n+1:
                linkedList[prev][1]=now
            else:
                linkedList[prev][1]=now
                linkedList[next][0]=now
    return "".join(OX)

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

<코드>

def solution(word):
    answer = 0
    word_list=[]
    words="AEIOU"

    def all_word(cnt, w):
        if cnt==5:
            return
        for i in range(len(words)):
            word_list.append(w+words[i])
            all_word(cnt+1,w+words[i])

    all_word(0,"")
    return word_list.index(word)+1

• 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다.
• 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다.
• 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다.
• 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.

당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의 길이가 얼마인지 알고 싶습니다. 경로 사이클이란, 빛이 이동하는 순환 경로를 의미합니다.

격자의 정보를 나타내는 1차원 문자열 배열 grid가 매개변수로 주어집니다. 주어진 격자를 통해 만들어지는 빛의 경로 사이클의 모든 길이들을 배열에 담아 오름차순으로 정렬하여 return 하도록 solution 함수를 완성해주세요.

<코드>

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

def solution(grid):
    global visited,n,m
    n=len(grid)
    m=len(grid[0])
    answer=[]
    visited=[[[False]*4 for _ in range(m)] for _ in range(n)]
    for sx in range(n):
        for sy in range(m):
            for d in range(4):
                if not visited[sx][sy][d]:
                    rst=simul(sx, sy, d, grid)
                    if rst!=0:
                        answer.append(rst)
    answer.sort()
    return answer

def simul(sx, sy, sd, grid):
    global visited
    x,y,d=sx,sy,sd
    cnt=0
    visited[sx][sy][sd]=True
    while True:
        x=(x+dx[d])%n
        y=(y+dy[d])%m
        cnt+=1

        if grid[x][y]=='R':
            d=(d+1)%4
        elif grid[x][y]=='L':
            d=(d-1)%4
        if visited[x][y][d]:
            if (x,y,d)==(sx,sy,sd):
                return cnt
            else:
                return 0
        visited[x][y][d]=True

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

<코드>

from collections import deque

def bfs(graph, start, visited):
    queue=deque([start])
    visited[start]=True
    cnt=0
    while queue:
        v=queue.popleft()
        cnt+=1
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
    return cnt

def solution(n, wires):
    answer = n-2
    for i in range(len(wires)):
        tmps=wires.copy()
        graph=[[]for i in range(n+1)]
        visited=[False]*(n+1)
        tmps.pop(i)
        for wire in tmps:
            x,y=wire
            graph[x].append(y)
            graph[y].append(x)
        for idx,g in enumerate(graph):
            if g!=[]:
                start=idx
                break
        cnts=bfs(graph,start,visited)
        other_cnts=n-cnts
        if abs(cnts-other_cnts)<answer:
            answer=abs(cnts-other_cnts)

    return answer

따라서 정답은

"........"
"........."
"........."
".......*"
"........."
"........."
"........."
"........."
"......." 입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

<코드>

from itertools import combinations

def intersection_point(line1, line2):
    a,b,e=line1
    c,d,f=line2
    if a*d==b*c:
        return None
    x=(b*f-e*d)/(a*d-b*c)
    y=(e*c-a*f)/(a*d-b*c)
    if x==int(x) and y==int(y):
        return (int(x),int(y))

def solution(line):
    N=len(line)
    combs=list(combinations(line,2))
    points=set()
    for comb in combs:
        point=intersection_point(comb[0],comb[1])
        if point:
            points.add(point)
    xs=[p[0] for p in points]
    x_min=min(xs)
    x_max=max(xs)

    ys=[p[1] for p in points]
    y_min=min(ys)
    y_max=max(ys)

    answer = ['.'*(x_max-x_min+1)]*(y_max-y_min+1)

    for point in points:
        x,y=point
        answer[y_max-y]=answer[y_max-y][:x-x_min]+'*'+answer[y_max-y][x-x_min+1:]
    return [''.join(ans) for ans in answer]

1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.

정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

<코드>

def solution(n, left, right):
    answer = []
    for i in range(left, right+1):
        a=i//n
        b=i%n
        if a<b: a,b=b,a
        answer.append(a+1)
    return answer

<코드>

def solution(board, skill):
    answer=0
    tmp=[[0 for j in range(len(board[0])+1)]for i in range(len(board)+1)]

    for  t, r1, c1, r2, c2, d in skill:
        if t==2:
            d= -d
        tmp[r1][c1]-=d
        tmp[r1][c2+1]+=d
        tmp[r2+1][c1]+=d
        tmp[r2+1][c2+1]-=d

    for i in range(len(tmp)-1):
        for j in range(len(tmp[0])-1):
            tmp[i][j+1]+=tmp[i][j]
    for i in range(len(tmp)-1):
        for j in range(len(tmp[0])-1):
            tmp[i+1][j]+=tmp[i][j]
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j]+tmp[i][j]>0:
                answer+=1

    return answer

<설명> 단순하게 구현했다가 효율성에서 실패하게 된다. 그래서 누적합을 사용해서 이중포문을 사용하지 않도록 노력했다. 링크텍스트 해당 블로그를 보고 풀이를 이해했다.

<코드>

from collections import deque

def solution(queue1, queue2):
    deque1=deque(queue1)
    deque2=deque(queue2)
    sum1=sum(deque1)
    sum2=sum(deque2)

    for i in range(len(deque1)*3):
        if sum1==sum2:
            return i
        if sum1>sum2:
            num=deque1.popleft()
            deque2.append(num)
            sum1-=num
            sum2+=num
        else:
            num=deque2.popleft()
            deque1.append(num)
            sum2-=num
            sum1+=num

    return -1

elements result [7,9,1,1,4] 18

<코드>

def solution(elements):
    answer = 0
    numberSet=set()

    n=len(elements)
    elements=elements*2
    for i in range(n):
        for j in range(n):
            numberSet.add(sum(elements[j:j+i+1]))

    answer=len(numberSet)
    return answer

<풀이> set을 사용해서 중복되는 값을 자동으로 제거해준다. list에서도 sum함수를 사용할 수 있다는 점!!

<코드>

from collections import Counter

def solution(topping):
    dic=Counter(topping)
    set_dic=set()
    answer=0
    for i in topping:
        dic[i]-=1
        set_dic.add(i)
        if dic[i]==0:
            dic.pop(i)
        if len(dic)==len(set_dic):
            answer+=1

    return answer

<풀이> counter와 dictionary의 개념을 확실히 아는 것이 중요했다. collections의 Counter를 사용하게 되면 dictionary의 형태로 담기게 된다. ex) {'1':2, '2':3, '3':4}

<코드>

from collections import deque

def solution(n, roads, sources, destination):
    visit=[-1]*(n+1)
    graph=[[] for _ in range(n+1)]
    for s,e in roads:
        graph[s].append(e)
        graph[e].append(s)

    queue=deque([destination])
    visit[destination]=0
    while queue:
        now=queue.popleft()

        for node in graph[now]:
            if visit[node]==-1:
                visit[node]=visit[now]+1
                queue.append(node)

    return [visit[i] for i in sources]

<코드>

import math

def solution(a, b, n):
    answer = 0
    while(n>=a):
        remain = n % a
        n =math.floor(n / a) * b
        answer += n
        n += remain
    return answer

<코드>

n,k=map(int, input().split())
list=list(map(int, input().split()))
plug=[0]*n

cnt=0
list_idx=0
tmp=0
tmp_i=0

for i in list:
    if i in plug: #멀티탭에 이미 있는 경우
        pass
    elif 0 in plug: #멀티탭에 빈곳이 있는 경우
        plug[plug.index(0)]=i
    else:
        for j in plug:
            if j not in list[list_idx:]: #이후에 없으면
                tmp=j
                break
            elif list[list_idx:].index(j)>tmp_i: #이후에 있을 때, 어느 것이 나중에 나오고 먼저 나오는지 판단 
                tmp=j
                tmp_i=list[list_idx:].index(j)
        plug[plug.index(tmp)]=i
        tmp=tmp_i=0
        cnt+=1
    list_idx+=1

print(cnt)

• 그리디 알고리즘 각 단계에서 가장 최선의 선택을 하는 방법 탐욕 알고리즘을 적용시키려면 두가지 조건을 만족해야 한다. 1-앞의 선택이 이후의 선택에 영향을 주지 않아야 한다. 2-문제의 최적해가 부분 문제에 대해서도 최적해여야 한다.

<문제 설명> 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

<코드>

n=int(input())
list=list(map(int, input().split()))
ans=[0]*n
for j in range(1, n+1):
    t=list[j-1]
    cnt=0
    for i in range(n):
        if cnt==t and ans[i]==0:
            ans[i]=j
            break
        elif ans[i]==0:
            cnt+=1
print(*ans)

문제링크:저울

이 문제는 코드는 간단하지만 논리를 이해하는데 시간이 오래걸렸습니다. 핵심논리는 현재 가지고 있는 추로 만들 수 있는 무게가 1, 3, 5, 7, 8 이라면 x무게의 추가 추가됐을 때 1+x, 3+x, 5+x, 7+x, 8+x의 무게를 더 만들 수 있다는 것입니다.

n=int(input())
list=list(map(int, input().split()))
list.sort()
result=1

for i in list:
    if result<i:
        break
    result+=i

print(result)

이 문제에서 핵심은 1부터 무게를 만들어 나갈 때 만들 수 없는 최소숫자를 구하는 것입니다. 그래서 result는 1로 시작했습니다. result는 현재 가지고 있는 추로 만들 수 있는 최대무게+1로 생각하는게 직관적으로 이해할 수 있는 것 같습니다.(+1을 해주는 이유는 마지막에 만들 수 없는 최소무게를 출력하기 위해서)

[1 1 2 3 6 7 30]을 예시로,

for문을 시작하기 전에는 추가 없기 때문에 만들 수 있는 최대무게는 0이 되고 result는 1이 됩니다.

1. 첫번째 추(1)를 가지게되면 0+1을 만들 수 있기 때문에 result는 2(result+1)가 됩니다.
2. 두번째 추(1)를 가지게되면 0+1, 1+1을 만들 수 있기 때문에 result는 3(result+1)이 됩니다.
3. 세번째 추(2)를 가지게되면 0+1, 1+2, 2+2를 만들 수 있기 때문에 result는 5(result+2)이 됩니다.
4. 네번째 추(3)을 가지게되면 0+3,..., 4+3을 만들 수 있기 때문에 result는 8(result+3)이 됩니다.
5. 다섯번째 추(6)을 가지게되면 0+6,...,7+6을 만들 수 있기 때문에 result는 14(result+6)이 됩니다.
6. 여섯번째 추(7)을 가지게되면 0+7,...13+7을 만들 수 있기 때문에 result는 21(result+7)이 됩니다.
7. 마지막 추(30)을 가지게되면 0+30,...,20+30을 만들 수 있습니다. 이 때, result가 21이었기 때문에 21부터 만들 수 있어야 하는데 마지막추는 30부터 만들 수 있습니다. 그렇기 때문에 21은 만들 수 없는 최소 무게가 됩니다.

문제링크 : 보석도둑

최대한 비싼 보석을 훔치는 방법을 찾는 문제이다. heapq는 자동으로 정렬이 되는 효과가 있기 때문에 정렬이 시간초과가 날 경우 유용하게 사용할 수 있다.

import sys
import heapq

input=sys.stdin.readline
n,k=map(int, input().split())
jew=[list(map(int, input().split()))for _ in range(n)]
bag=[int(input())for _ in range(k)]
jew.sort()
bag.sort()

total=0
temp=[]
for b in bag: #bag의 최솟값부터
    while jew and b>=jew[0][0]:
        heapq.heappush(temp, -jew[0][1])
        heapq.heappop(jew)
    if temp:
        total+=heapq.heappop(temp)
    elif not jew:
        break
print(-total)

heap은 작은 값이 부모노드로 큰 값이 자식노드로 들어간다. heappop을 사용할 경우 root값이 빠져나온다(가장 작은 값)

정말 좋은 기술인데 왜 항상 떠오르지 않을까!!!

문제링크 : 카드 정렬하기

문제

import heapq

n=int(input())
card=[]
for i in range(n):
    heapq.heappush(card, int(input()))
sum=0
if len(card)==1:
    print(0)
else:
    while len(card)>1:
        result=heapq.heappop(card)+heapq.heappop(card)
        sum+=result
        heapq.heappush(card,result)
    print(sum)

문제링크 : 크게만들기

문제

n,m=map(int, input().split())
num=list(map(int, input().strip()))
result=[]
count=0

for i in range(n):
    while count<m and result:
        if result[len(result)-1]<num[i]:
            result.pop()
            count += 1
        else:
            break
    result.append(num[i])

for i in range(n-m):
    print(result[i],end="")

문제링크 : 배

문제

n=int(input())
crane=list(map(int, input().split()))
m=int(input())
box=list(map(int, input().split()))

crane.sort(reverse=True)
box.sort(reverse=True)

time=0
count=0
visited=[0 for _ in range(m)]
crane_visited=[0]*n

if max(crane) < max(box):
    print(-1)
else:
    while count<len(box):
        for i in range(n):
            while crane_visited[i]<len(box):
                if not visited[crane_visited[i]] and crane[i]>=box[crane_visited[i]]:
                    visited[crane_visited[i]]=True
                    count+=1
                    crane_visited[i]+=1
                    break
                crane_visited[i]+=1
        time+=1
    print(time)