웹드루아 - 웹 개발자 드루아

첫 번째 풀이(오답)

1. 트럭 deque와 0으로 이루어진 다리 deque를 만든다.

2. 트럭 deque가 0일 될때까지 while문을 반복한다. 트럭을 하나 popleft해주고
'다리도 하나 popleft 해준다.'(다리를 이동하는 것을 0 하나를 빼고 트럭을 올리는 거로 표현) 

2-1. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 다리에 올려준다.

2-2. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 트럭 deque에 appendleft 해주고 '0을 넣어준다.' (다리에 아무것도 올라가지 않았다는 표현)

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    
    while tque:
        time += 1
        pop = tque.popleft()
        bl.popleft()
        
        if sum(bl) + pop <= w:
            bl.append(pop)
            continue
        
        if sum(bl) + pop > w:
            bl.append(0)
            tque.appendleft(pop)
            continue

    time += b_l
    return time

로직은 맞았지만 케이스 하나에서 시간 초과가 발생했다. sum을 사용해서 그런 것 같다.

두 번째 풀이 (정답)

sum을 어떻게 바꿀지 고민해보자

그리고 무조건 처음에 pop을 하여 트럭을 빼는 방식은 비효율적이다.

다리가 버티는 무게(wei)를 따로 만들어 무게를 더하고 빼주자.

무조건 while 반복문을 시작할때, 다리 deque에서 popleft한 요소를 빼준다.

그리고 트럭 deque도 먼저 빼주지 말고 트럭 deque의 0 인덱스와 wei를 더한 무게를 다리가 버틸 수 있는 하중과 비교해주면 훨씬 간단하게 해결할 수 있다.

deque를 사용한 풀이

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    wei = 0
    
    while tque:
        time += 1
        wei -= bl.popleft()
        
        if wei + tque[0] <= w:
            wei += tque[0]
            bl.append(tque.popleft())
            continue
        
        if wei + tque[0] > w:
            bl.append(0)
            continue

    time += b_l
    
    return time

deque를 사용하지 않는 풀이

def solution(b, w, t):
    time = 0
    bridge = [0]*b
    wei = 0
    
    while len(t) != 0:
        time += 1
        wei -= bridge.pop(0)
        
        if wei + t[0] <= w:
            wei += t[0]
            bridge.append(t.pop(0))
        else:
            bridge.append(0)
        
    time += b
        
    
    return time

스택/큐 문제를 풀 때 팁

스택이나 큐에 쌓이는 것을 확인하고 싶을 때 위에서 했던 것처럼 +/-를 이용해 표현할 수 있다.

위에서는 다리에 올라간 트럭의 무게를 빠른 속도로 파악하기 위해 wei를 0으로 초기화하고, 들어오는 트럭과 나가는 트럭의 무게를 뺐는데 이는 스택을 사용하는 것과 같은 효과를 가지고 있다.

다리는 지나는 트럭 문제 외에 대표적인 문제로 올바른 괄호 찾기 문제가 있다.

이 문제는 중괄호로 주어진 문자열이 열림과 닫힘의 짝이 맞는 지 확인하는 문제이다.

기본적으로는 무조건 false인 경우를 처리한 후 스택에 문자열 순대로 넣으면서 스택에 들어간 괄호가 (이고 이어서 들어가는 괄호가 ) 라면 없애주고 그렇지 않은 경우는 그냥 계속 넣어준다. 결과적으로 스택에 아무것도 남아있지 않으면 올바른 괄호이고, 스택에 남아있다면 올바른 괄호가 아닌 것이다. 이를 정말 간편하게 변수를 0으로 초기화하고 +와 -로 구현할 수 있다.

def solution(s):
	answer = True
    judge = 0
    
    if s[-1] == '(' or s[0] == ')':
    	return False
    
    while s:
    	pop = s.pop(0)
        
        if pop == '(':
        	judge += 1
        
        if  judge > 0 and pop == ')': 
        # 아무것도 들어오지 않은 상태(0)에서 ')'를 넣으면(-1) 의미가 없기 때문에 아무 조치도 하지 않는다.
        	judge -= 1
        
    if judge != 0:
    	return False
        
    return answer

위와 같이 0에 +1 -1을 하는 방식으로 스택을 표현했다. 이를 다른 문제를 풀 때도 고려해보고 적용해보면 좋을 것이라 생각된다.

|| 문제 설명 ||

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

---

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

---

입출력 예mapsresult

["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

---

입출력 예 설명

입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

틀린풀이 1

계속 이상하게 문제를 풀어서 이 문제만 3시간은 잡고 있었던거 같다ㅠㅠ

일단 처음에 했던 방식은 아래와 같다

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    vis = []
    visForE = []
    dis = []

    s = []
    e = [] 

    # visit 만들기
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        vis.append(arr)
        visForE.append(arr)
        dis.append(arr)



    # 시작점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j)

    # 탈출점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "E":
                e.append(i)
                e.append(j)            


    # 레버까지의 최단거리 + 레버 -> 탈출구 까지의 최단거리
    time = 0
    queue = deque()
    queue.append(s)

    equeue = deque()

    while queue:
        h, w = queue.popleft()
        vis[h][w] = 1 # 방문 처리

        if maps[h][w] == "L":
            equeue.append((h, w, 0))
            break

        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]

            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue

            if maps[nh][nw] == "X":
                continue

            if vis[nh][nw] == 1:
                continue

            if vis[nh][nw] == 0:
                queue.append((nh, nw))
                time += 1

    print(time)
    print(queue)
    print(equeue)

이렇게 레버까지의 걸린 시간을 구한 후에 레버에서 탈출구까지 걸리는 시간을 구할려고 했다. 하지만 이 방식은 탐색을 진행할 때마다 전역 변수인 time에 +1을 해주기 때문에 탐색하는 모든 시간을 구하므로 옳지 않다.

그래서 큐에 비용까지 포함해서 다시 코드를 작성했다.

틀린 풀이 2

from collections import deque

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    lastcost = 0
    
    vis = []
    visForE = []
    
    s = []
    
    # visit 만들기
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        vis.append(arr)
        visForE.append(arr)
    
    # 시작점 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j) 
    
    # 레버까지의 최단시간 구하기
    h, w = s
    vis[h][w] = 1
    queue = deque()
    queue.append((h, w, 0))
    
    
    while queue:
        h, w, cost = queue.popleft()
        
        if maps[h][w] == "L":
            queue.append((h, w, cost))
            break
        
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if vis[nh][nw] == 1:
                continue
            
            if vis[nh][nw] == 0:
                queue.append((nh, nw, cost + 1))
                vis[nh][nw] = 1
    
    # 레버에서 탈출점까지의 최단 시간 구하기
    
    while queue:
        x, y, cost = queue.popleft()
        
        if maps[x][y] == "E":
            return cost
            break
        
        for i in range(4):
            nh = x + dh[i]
            nw = y + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if vis[nh][nw] == 1:
                continue
            
            if vis[nh][nw] == 0:
                queue.append((nh, nw, cost + 1))
                vis[nh][nw] = 1
    
    ## 비용으로 생각해서 풀자 전역적으로 time을 지정해서
    ## 풀려고 하니까 최단 거리가 아니라
    ## 모든 지점을 탐색하는데 걸린 시간이 출력되어서 계속 못 풀었다
    
    return -1

이 경우는 무조건 레버를 찾을 수 있다는 가정하에 다음 단계로 넘어가기 때문에 정답을 맞히지 못한건 같다 그래서 bfs 함수를 따로 만들어서 (시작점, 목표점, maps)를 입력해 cost 값을 받는 방식으로 바꿔보기로 했다.

옳은 풀이

from collections import deque

def bfs(start, end, maps):
    h, w = start
    eh, ew = end
    
    dh = [1, -1, 0, 0]
    dw = [0, 0, 1, -1]
    n = len(maps)
    m = len(maps[0])
    
    visit = []
    for i in range(n):
        arr = []
        for j in range(m):
            arr.append(0)
        visit.append(arr)
    
    que = deque()
    que.append((h, w, 0))
    visit[h][w] = 1
    
    while que:
        h, w, cost = que.popleft()
        
        if h == eh and w == ew:
            return cost
        
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            
            if nh < 0 or nh >= n or nw < 0 or nw >= m:
                continue
            
            if maps[nh][nw] == "X":
                continue
            
            if visit[nh][nw] == 1:
                continue
            
            if visit[nh][nw] == 0:
                que.append((nh, nw, cost + 1))
                visit[nh][nw] = 1
    
    return -1
    
def solution(maps):
    s = []
    e = []
    l = []
    
    n = len(maps)
    m = len(maps[0])
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "S":
                s.append(i)
                s.append(j)
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "L":
                l.append(i)
                l.append(j) 
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == "E":
                e.append(i)
                e.append(j)
    
    path1 = bfs(s, l, maps)
    path2 = bfs(l, e, maps)
    
    if path1 != -1 and path2 != -1:
        return path1 + path2
    
    return -1

함수를 따로 만들어서 시작점과 끝점을 정하고 각각 따로 bfs를 돌려서 각 비용을 계산하고 둘다 찾아진다면 두 비용을 합친 것을 리턴하고 아니라면 -1을 리턴해 마무리 해준다.

항상 차분하게 문제를 보고 신중하게 생각하자

다이나믹 프로그래밍이란 한 번 계산하여 해결한 문제를 메모리에 저장하여 다음에 같은 문제를 만났을때 계산하지 않고 메모리에 저장한 값을 가져와 답을 반환하여 효율성을 높이는 방식이다.

해당 다이나믹 프로그래밍에서의 다이나믹은 다른 상황에서 쓰이는 의미가 담기진 않았다.

다이나믹 프로그래밍(DP)의 두 가지 방법

- 탑다운

하향식, 구현 과정에서 재귀함수를 사용한다. 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출

- 바텀업

상향식, 구현 과정에서 반복문를 사용한다. 아래쪽부터 작은 문제를 하나씩 해결해나가며 다음의 문제까지 차례로 해결 

위 처럼 두 가지의 방법을 다이나믹 프로그래밍을 구현할 수 있다.

DP를 이용할 수 있는 조건

1. 최적 부분 조건

- 작은 문제들의 답을 모아 큰 문제를 해결할 수 있어야 한다.

2. 중복되는 부분 문제

- 동일만 문제를 반복적으로 해결하는 상황

DP로 효과적으로 계산할 수 있는 문제들 

[피보나치 수열]

앞 두 수의 합으로 이루어진 수열

이러한 인접한 항들 사이의 관계식으로 표현한 것을 점화식이라고 하는데 피보나치 수열을 점화식은 다음과 같다

피보나치 수열이 계산되는 과정을 표현해보면

이렇게 표현된다.

코드로 작성해보자

def fibo(x):
	if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)

하지만 단순 재귀함수로 피보나치 수열을 해결하면 아래 그림과 같이 되어 지수 시간 복잡도를 가지게 되기 때문에 더 효율적인 방법이 필요하다.

>>  중복되는 부분문제라고 볼 수 있다.

그리고 특정 값을 구할려고 하면 그 값이 작은 문제로 분해되는데 이는 최적 부분 구조이기 때문에 

DP를 이용해 해결할 수 있다.

먼저 탑다운 방식인 메모이제이션으로 구현해보자

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.

- 같은 문제를 다시 호출할 경우 메모했던 결과를 가지고 온다.

- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.

# f(99)를 구하고 싶다

dp = [0]*100

def fibo(x):
	# 종료조건
    if x == 1 or x == 2:
    	return 1
    # 계산한 적이 있는 문제라면 저장한 값 반환
    if dp[x] != 0:
    	return dp[x]
    # 계산한 적이 없는 문제라면 계산하여 dp 테이블에 저장
    dp[x] = fibo(x-1) + fibo(x-2)
    return dp[x]
    
print(f(99))

재귀함수를 사용하는 것을 확인할 수 있다.

바텀업 방식으로도 DP를 구현해보자

dp = [0]*100

dp[1] = 1
dp[2] = 1
n = 99

for i in rnage(3, n + 1):
	dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

반복문을 사용하는 것을 확인할 수 있다.

메모이제이션 동작 분석

 위와 같이 계산이 되기 때문에 효율적인 것을 알 수 있다 또한 호출된 것만 남긴다면 

이렇게 함수가 호출된다.

피보나치 수열로 다이나믹 프로그래밍의 기초 개념을 알아봤다. 다이나믹 프로그래밍은 거의 알려진 문제에서 나오는 경우가 많기 때문에 문제를 많이 접하고 해결하며 익숙해 지는 것이 중요한것 같다

푸는 과정은 일단 다 풀어보고 이해하게 된 점 정리와 사용된 자료구조를 정리하는 방식으로 진행할 것이다.

폰켓몬 문제

문제 풀이

풀이1

def solution(nums):
    setNums = list(set(nums))
    countMonster = len(setNums)
    
    if countMonster <= (len(nums)/2):
        return countMonster
    elif countMonster > (len(nums)/2):
        return (len(nums)/2)

처음에는 뽑는 경우의 수를 모두 가져오고 종류를 확인할려고 했는데, 코드를 작성하는 과정에서 너무 복잡하다는 생각에 다시 문제를 확인했다. 결론적으로 뽑을 수 있는 폰켓몬의 수는 정해져 있으므로 그 이상으로 여러 종류의 폰켓몬을 뽑을 순 없다.
따라서 뽑을 수 있는 수보다 종류가 적거나 같으면 가장 많이 뽑는 수는 뽑을 수 있는 수 그 자체가 될것이고,

뽑을 수 있는 수보다 종류가 적다면 무조건 파라미터로 받는 나열에 있는 종류의 수가 가장 많이 뽑은 종류의 수가 될것이다.

이 생각으로 위와 같이 풀었다.

풀이 2

근데 이는 더 간다한게 min 내장 함수를 통해 풀 수 있는데 그 풀이는 다음과 같다.

def solution(nums):
	return min( len(set(nums)), (len(nums)/2) )

위에서 작성한 코드와 똑같은 기능을 하지만 min을 이용에 훨씬 간결하게 짤 수 있다.

완주하지 못한 선수

문제 풀이

그 전 포스팅에서 적긴 했는데, 문제를 풀면서 느낀 것이 먼저 문제의 의도를 정확히 파악하고 머리로 알고리즘을 설계하는 것이 더 중요한 것 같다.

처음에는 set 함수를 이용해서 풀려고 했는데 set을 이용하면 동명이인을 잡아낼 수 없어 문제가 됐다. 그 다음에는 참여자 명단이랑 완주자 명단을 비교하며 참여자 명단에서 완주자 명단에 있는 사람을 없애려고 했는데, 이는 설정한 len(참여자명단)이 실시간으로 바뀌기 때문에 for문에서 에러가 나 실행하지 못했다.

그래서 hash를 이용해 풀었다.

주어지는 선수의 수는 100000이하기 때문에 O(NlogN) 이하의 시간으로 풀어야한다.

풀이 1

특정 문자열은 고유한 해시값으로 변환되기 때문에 이를 이용했다.

참여자 명단의 이름들을 해시로 변환해 더하고, 똑같이 완주자 명단의 이름들을 해시로 변환해 더했다.

그리고 빼면 특정 해시값이 나오고 그 해시값에 해당하는 이름을 가져오면 완주하지 못한 사람이다.

틀린 처음 풀이

def solution(participant, completion):
    mydict = dict()
    
    for i in participant:
        mydict[hash(i)] = i
    
    sumPartKey = sum(mydict.keys())
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

이 방식은 오류가 났었다. 그 이유는 반복문으로 딕셔너리를 만들때 동명이인은 같은 키로 들어가기 때문에 위에서 만들어진 mydict은 동명이인을 받아도 하나로 넣어버린다. 그렇기 때문에 sumPartKey에서 sumComp를 빼면 해시값이 아닌 숫자가 나와 동명이인을 입력 받았을 때는 오류가 발생한다.

맞는 풀이

def solution(participant, completion):
    mydict = dict()
    sumPartKey = 0
    for i in participant:
        mydict[hash(i)] = i
        sumPartKey += hash(i)
        
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

딕셔너리를 만들 때, 넣는 값들을 바로바로 더해줘서 위에서 있었던 문제를 해결할 수 있다.

풀이 2

collection 모듈의 Counter를 이용한 풀이 방식이다. Counter을 이용하면 배열에 각 원소들의 갯수가 몇개인지 뽑아주는데 참여자 명단과 완주자 명단에 적용을 하고 빼주면 완주하지 못한 참여자를 구할 수 있다. 

딕셔너리 끼리는 뺄 수 없지만 Counter를 통해 객체로 바뀌었기 때문에 빼는 것이 가능하다.

import collections

def solution(participant, completion):
	answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys()[0])

전화번호 목록 문제

이 문제를 풀기 위해선 문자열 비교하는 것을 알아야한다.

• 완전 일치 : == !=
• 부분 일치 : in not in
• 전방 일치 : startswith
• 후방 일치 : endswith

위와 같이 비교를 할 수 있고 전방과 후방 일치는 문자열2. startswith / endswith (문자열1) 방식으로 사용하고 문자열1일 문자열2에 있는지 찾는 것이다.

그리고 정렬하는 기준에 대해 알아야한다. 배열의 원소가 정수형이나 실수형이라면 정렬의 기준의 숫자의 크기이지만 문자열인 경우는 제일 앞에 있는 문자를 기준으로 정렬한다. 제일 먼저 오는 문자 순으로 정렬한 후의 그 뒤에 오는 문자를 기준으로 다시 정렬한다. 예를 들어 133이 1222보다 작지만 1 다음으로 오는 2가 3보다 작기 때문에 ['133', '1222']를 sort하면 ['1222', '133']으로 정렬된다.

예를 하나 더 들어서 설명하자면,

[12, 134, 34, 456]에 sort()를 해주면 [12, 34, 134, 456]으로 정렬되고,

['12', '134', '34', '456']에 sort()를 해주면 다음과 같이 정렬한다. ['12', '134', '34', '456']

이러한 특성을 이용해 문제를 풀 수 있다.

파라미터로 오는 배열을 정렬하면 문자열 a가 그 다음에 오는 문자열 b에 포함되는지만 확인하면 되니까 먼저 배열을 정렬해준 뒤, 바로 옆에 있는 문자열끼리만 비교해주면 된다.

def solution(phone_book):
	answer = True
    phone_book.sort()
    
    for i in range (len(phone_book)-1):
    	if phone_book[i+1].startswith(phone_book[i]):
        	answer = False
            break
	retrun answer

이렇게 작성할 수 있다