[240508] 코딩테스트 문제풀이

1. 트리의 부모찾기

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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


N = int(input())
visited = [False] * (N+1)
tree = [[]for _ in range(N+1)]
answer = [0] * (N+1)  #트리의 부모노드를 저장할 리스트

for _ in range(1,N) :
    a,b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(number) :
    visited[number] = True
    for i in tree[number] :
        if not visited[i] :
            answer[i] = number
            dfs(i)


dfs(1)

for i in range(2,N+1) :
    print(answer[i])

 

---

2.  미로탐색

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

from collections import deque
n,m = map(int, input().split(" "))
A = []
for i in range(n) :
    A.append(list(map(int,input())))


direction = [(1,0),(-1,0),(0,1),(0,-1)]

def bfs(n,m,A) :
    visited = [[0 for _ in range(m)] for j in range(n)]
    queue = deque()
    for row in range(n) :
        for col in range(m) :
            if A[row][col] == 1 :
                queue.append((row,col))
                while queue :
                    curr_x, curr_y = queue.popleft()
                    A[curr_x][curr_y] = 0
                    for dx,dy in direction :
                        next_x, next_y = curr_x + dx, curr_y + dy
                        if 0<=next_x<n and 0<=next_y<m and A[next_x][next_y] == 1 :
                            queue.append((next_x,next_y))
                            A[next_x][next_y] = 0
                            visited[next_x][next_y] = visited[curr_x][curr_y] + 1

    answer = visited[-1][-1]

    return answer + 1


print(bfs(n,m,A))

 

---

3. 양

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

# 양
from collections import deque
n,m = map(int, input().split(" "))
directions = [(0,1),(0,-1),(1,0),(-1,0)]
A = list()
for i in range(n) :
    A.append(list(input()))

def dfs(n,m,A) :
    queue = deque()
    count = 0
    count_wo_sh = [0,0] #늑대->양 순서
    for row in range(n) :
        for col in range(m) :
            answer = [0,0]
            if A[row][col] != "#" :
                queue.append((row,col))
                if A[row][col] == 'v':
                    answer[0] += 1
                if A[row][col] == 'o':
                    answer[1] += 1
                A[row][col] = '#'
                while queue :
                    curr_x, curr_y = queue.popleft()
                    for dx,dy in directions :
                        next_x, next_y = curr_x+dx, curr_y+dy
                        if 0<=next_x<n and 0<=next_y<m and A[next_x][next_y] != '#' :
                            queue.append((next_x,next_y))
                            if A[next_x][next_y] == 'v':
                                answer[0] += 1
                            if A[next_x][next_y] == 'o':
                                answer[1] += 1
                            A[next_x][next_y] = '#'

                count +=1
                if answer[0] >= answer[1] :
                    count_wo_sh[0] += answer[0]

                else :
                    count_wo_sh[1] += answer[1]



    return count_wo_sh


a,b = dfs(n,m,A)

print(b,a)

 

---

4. 헌내기는 친구가 필요해

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

• 조건을 잘 봐야함
  • 상하좌우로 밖에 움직이지 못함 !!! 

from collections import deque
n,m = map(int,(input().split(" ")))
A = list()
for i in range(n) :
    A.append(list(input()))

directions = [(-1,0),(1,0),(0,1),(0,-1)]

def dfs(n,m,A) :
    queue = deque()
    count = 0
    found_I = False
    for row in range(n) :
        for col in range(m) :
            if A[row][col] == 'I' :
                queue.append((row,col))
                found_I = True
                break

        if found_I :
            break

    while queue :
        curr_x,curr_y=queue.popleft()
        for dx, dy in directions :
            next_x,next_y = curr_x+dx, curr_y+dy
            if 0<=next_x<n and 0<=next_y<m :
                if A[next_x][next_y] == 'P':
                    count += 1
                elif A[next_x][next_y] == 'X':
                    continue
                queue.append((next_x,next_y))
                A[next_x][next_y] = 'X'

    return count

count = dfs(n,m,A)
if count == 0 :
    print("TT")
else :
    print(count)

 

---

5. 정수제곱근

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

n = int(input())

start_index = 0
end_index = n

while start_index <= end_index :
    mid = (start_index + end_index) // 2
    if (mid**2) < n :
        start_index = mid + 1

    else :
        end_index = mid -1

print(start_index)

 

---

6.  트리 / 리프 노드 개수 구하기 (복습하기)

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

# 트리 / 리프노드 개수 구하기
import sys
sys.setrecursionlimit(10 ** 6)   # 재귀함수

input = sys.stdin.readline
N = int(input())
visited = [False] * (N+1)
tree = [[] for _ in range(N)]
answer = 0 #리프노드 저장 // 카운트
p = list(map(int, input().split()))

# 트리 -> 인접리스트로 구현
for i in range(N) :
    if p[i] != -1 :
        tree[i].append(p[i])
        tree[p[i]].append(i)
    else :
        root = i

def DFS(number) :
    global answer
    visited[number] = True
    cNode = 0
    for i in tree[number] :
        if not visited[i] and i != deleteNode :
            cNode += 1
            DFS(i)

    # 자식 노드 수가 0개일 떄 리프 노드로 간주하고 정답 값 증가
    if cNode == 0 :
        answer += 1

deleteNode = int(input())

if deleteNode == root :
    print(0)
else :
    DFS(root)
    print(answer)

 

---

7.  트리 순회

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

import sys
input = sys.stdin.readline
N = int(input())
tree = {}   #딕셔너리 형태로 선언

# input 값 받기
for _ in range(N) :
    root, left, right = input().split()
    tree[root] = [left,right]

def preOrder(now) :
    if now == '.' :
        return
    print(now, end = '') #현재노드
    preOrder(tree[now][0]) #왼쪽탐색
    preOrder(tree[now][1]) #오른쪽탐색


def inOrder(now) :
    if now == '.' :
        return
    inOrder(tree[now][0]) #왼쪽탐색
    print(now, end = '') #현재노드
    inOrder(tree[now][1]) #오른쪽탐색


def postOrder(now) :
    if now == '.' :
        return
    postOrder(tree[now][0]) #왼쪽탐색
    postOrder(tree[now][1]) #오른쪽탐색
    print(now, end = '') #현재노드

preOrder('A')
print()
inOrder('A')
print()
postOrder('A')

 

---

8.  롤케이크 자르기

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

프로그래머스

 

시간초과 

from collections import Counter

def solution(topping):
    answer = 0
    start_index = 1

    for i in range(1,len(topping)-1):
        a = len(Counter(topping[0:i]).keys())
        b = len(Counter(topping[i:]).keys())
        if a == b:
            answer += 1
    return answer

 

시간초과

def solution(topping):
    answer = 0
    start_index = 1

    for i in range(1,len(topping)-1):
        a = len(set(topping[0:i]))
        b = len(set(topping[i:]))
        if a == b:
            answer += 1
    return answer

 

• Counter - dict 이용하기
• topping 리스트를 하나씩 보면서, 해당 dict 값을 감소시키고, 만약 value 값이 0 이면 -> dict 에서 pop 해줌

from collections import Counter
def solution(topping):
    a = Counter(topping)
    b = set()
    answer = 0
    for i in topping :
        a[i] -= 1
        b.add(i)
        if a[i] == 0:
            a.pop(i)
        if len(a) == len(b) :
            answer += 1
    return answer

 

---

9. 방문길이

• (startx, starty,nextx,nexty)을 저장하는 방식으로 구현하기

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

프로그래머스

def solution(dirs):
    answer = 0
    a = list(dirs)
    xydict = {'U' : (0,1), 'D' : (0,-1), 'L' : (-1,0), 'R' : (1,0)}
    sets = set()
    cur_x, cur_y = 0,0

    for i in a :
        dx,dy = xydict[i]
        ny = dy + cur_y
        nx = dx + cur_x
        if -5<=ny<=5 and -5<=nx<=5 :
            sets.add((cur_x,cur_y,nx,ny))
            sets.add((nx, ny,cur_x,cur_y))
            cur_x = nx
            cur_y = ny

    return len(sets) // 2

 

---

10. 주식가격

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

프로그래머스

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)
    while prices :
        price = prices.popleft()
        time = 0
        for p in prices :
            time += 1
            if price > p :
                break
        answer.append(time)
    return answer

 

---

11. 뒤에 있는 큰 수 찾기

• 시간초과

def solution(numbers):
    answer = [-1] * len(numbers)
    for i in range(len(numbers)) :
        for j in range(i,len(numbers)) :
            if numbers[i] < numbers[j] :
                answer[i] = numbers[j]
                break


    return answer

 

 

---

12. 땅따먹기

• 점화식 짱 쉬움

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

프로그래머스

def solution(land):
    dp = [[0 for i in range(4)] for _ in range(len(land))]
    # 점화식 초기화
    for i in range(4) :
        dp[0][i] = land[0][i]

    for i in range(1,len(land)) :
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2]
        dp[i][3] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3]


    return max(dp[-1])

 

---

13.  스킬트리

• a : skill_trees 안에 skill 문자가 몇 개 있는지 카운트 
• b : skill 문자 순서로 들어오는게 있으면, stack에 append
• 최종 a,b 값 비교 같으면 -> True

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

프로그래머스

def solution(skill, skill_trees):
    answer = 0
    for i in skill_trees :
        a = list(i)
        b = list(skill)
        stack = []
        count = 0
        for k in a :
            if len(b)==0 :
                break
            if k in b :
                count += 1
            if k == b[0] :
                stack.append(k)
                del b[0]

        if len(stack) == count :
            answer += 1

    return answer

 

---

 

14.  두 큐 합 같게 만들기

• 문제는 쉽지만, 시간복잡도를 생각해야 하는 문제
  • 처음에는 sum 함수를 이용해 구현했지만,  sum 함수는 O(n) 의 시간복잡도를 가짐
  • 그래도 시간초과 발생함 -> queue2의 길이가 30000 이상이라는 문제 조건이 있음 -> 따라서 'count > 30000' 일 때도 break 해주도록 함

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

프로그래머스

from collections import deque

def solution(queue1, queue2):
    queue1 = deque(queue1)
    queue2 = deque(queue2)
    count = 0
    sum_queue1 = sum(queue1)
    sum_queue2 = sum(queue2)

    while True  :
        if len(queue1) == 0 or len(queue2) == 0 or count > 300000 :
            count = -1
            break

        if sum_queue1 > sum_queue2  :
            number = queue1.popleft()
            queue2.append(number)
            sum_queue1 -= number
            sum_queue2 += number
            count += 1

        elif sum_queue2 > sum_queue1 :
            number = queue2.popleft()
            queue1.append(number)
            sum_queue1 += number
            sum_queue2 -= number
            count += 1

        else : break
    return count

 

---

15. 연속된 부분 수열의 합

• 막힌 부분 : out of range 가 발생할 수 있기 때문에 end_index < len(sequence) 인지 확인해줘야 함

            if end_index < len(sequence) :
                sum += sequence[end_index]

 

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

프로그래머스

 

def solution(sequence, k):
    start_index = 0
    end_index = 0
    sum = sequence[0]
    answer = []

    while end_index < len(sequence) :
        if sum == k :
            lenw = end_index - start_index
            answer.append((lenw, start_index, end_index))
            sum -= sequence[start_index]
            start_index += 1

        elif sum < k :
            end_index += 1
            if end_index < len(sequence) :
                sum += sequence[end_index]

        else :
            sum -= sequence[start_index]
            start_index += 1

    answer.sort()
    answer = [answer[0][1], answer[0][2]]

    return answer

 

---

16.  게임 맵 최단거리(⭐️복습하기)

• 최단거리 너비우선탐색 구할 땐, 최단거리 저장하는 리스트 (short_count) 리스트를 만들어줘야 함

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

from collections import deque

def solution(maps):
    n = len(maps)
    m = len(maps[0])
    direction = [(0,1),(0,-1),(1,0),(-1,0)]
    queue = deque()
    short_count = [[-1 for i in range(m)] for _ in range(n)]
    queue.append((0,0))
    short_count[0][0] = 1

    while queue :
        x,y = queue.popleft()
        for dx,dy in direction :
            next_x, next_y = dx+x, dy+y
            if 0<=next_x<n and 0<=next_y<m and short_count[next_x][next_y] == -1 and maps[next_x][next_y] == 1 :
                short_count[next_x][next_y] = short_count[x][y] + 1
                queue.append((next_x, next_y))

    if short_count[n-1][m-1] == -1 :
        return -1
    else :
        return short_count[n-1][m-1]