모서리 IT 블로그

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

내 문제풀이

1. 각 선수마다 이긴 경우(win), 진 경우(lose) 상대 선수를 저장한다.

2. a번 선수가 b번 선수를 이겼다면, a번 선수가 진(a번 선수를 이긴) 선수들은 b번 선수가 무조건 질(b번 선수를 무조건 이길) 수 밖에 없다. 또한 a번 선수가 c번 선수한테 졌다면, a번 선수가 이긴(a번 선수한테 진) 선수들은 c번 선수가 무조건 이길(c번 선수한테 무조건 질) 수 밖에 없다.

-> 이 부분에서 시간을 많이 썼다.
a번 선수가 b번 선수를 이겼다면, "b번 선수가 이긴 선수들을 모두 a번 선수가 무조건 이긴다"라는 순서로 아래와 같이 코드 로직을 짰다. = 런타임 에러가 발생했고, 반복문을 수행하고 있는 대상을 계속 수정했기 때문이었을거다.

for idx in range(1, n+1):
    for x in win[idx]:
        win[idx].update(win[x])
    for x in lose[idx]:
        lose[idx].update(lose[x])

3. 각 선수마다 win, lose 길이가 n-1이면 정확한 순위를 알 수 있기 때문에 이 경우 answer + 1을 해준다.

내 코드 - 파이썬

def solution(n, results):
    answer = 0 
    win = [set() for i in range (n+1)] # i가 이긴 경우, 상대 선수
    lose = [set() for i in range (n+1)] # i가 진 경우, 상대 선수
    
    for a, b in results:
        win[a].add(b)
        lose[b].add(a)
            
    for idx in range(1, n+1):
        for x in win[idx]:
            lose[x].update(lose[idx])
        for x in lose[idx]:
            win[x].update(win[idx])
            
    for player in range(1, n+1):
        count = len(win[player]) + len(lose[player])
        if count == n-1: 
            answer += 1
            
    return answer

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

내 문제풀이

[위상 정렬 원리 활용]

1. 먼저 노드 1부터 노드 간 연결 정보를 확인하기 위해 edge를 오름차순 정렬한다.

2. edge를 차례대로 보며 리스트 graph에 각 노드마다 연결된 다른 노드 정보를 모두 저장한다. 이 때 양방향 그래프인 것을 유의한다.

3. queue(deque())에 현재 노드와 직접 연결되어 있는 노드들을 삽입하는 작업을 반복한다. 
   - 1번 노드가 기준이므로 먼저 queue에 1을 가장 먼저 삽입한다.

4. queue의 가장 앞 원소를 빼고 해당 원소와 연결되어 있는 모든 노드를 접근한다.
   - 만약 접근한 노드가 아직 연결된 이력이 없다면(route[ ? ] == 0) 현재 원소와 연결되어 있기 때문에 queue에 삽입하고 route값을 현재 원소의 route + 1 해준다.

5. queue가 빌 때까지 위 4번 로직을 반복하는데, route란 1번 노드로부터 몇 개의 간선을 통해 연결된 것인지를 표현하는 것이다. 하지만 route의 초기화는 모두 0으로 되어있고 route[1]==0이다.
만약 [5,1]이 edge에 있었다면, if route[g] == 0: 구문에서 route[1] 값이 증가하는 일이 발생한다. 따라서 while queue: 반복문을 시작하기 전에 route[1]을 1로 설정하고 이후 노드들의 route 값은 2부터 시작하게 되도록 하였다.
노드 1부터 "얼마나 멀리 떨어져 있는가"가 핵심이기 때문에 route의 시작(route[1])을 1로 설정해도 문제가 되지 않는다.

6. 정답을 반환하기 위해 route에서 가장 큰 값(노드 1부터 가장 멀리 떨어진 값)을 가지는 노드 갯수를 계산한다.

내 코드 - 파이썬

from collections import deque


def solution(n, edge):
    answer = 0
    route = [0]*(n+1) #노드 1부터 각 노드까지의 거리
    edge.sort() #노드 1부터 연결 정보 확인하기 위해 정렬
    queue = deque() 
    graph = [[] for i in range(n+1)] #각 노드에 연결된 노드 정보 저장
    
    for e in edge: # 양방향이므로 
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        
    queue.append(1)
    route[1] = 1
    
    while queue:
        now = queue.popleft()
        for g in graph[now]:
            if route[g]==0:
                queue.append(g)
                route[g] = route[now]+1
        
    # 1번 노드로부터 가장 멀리 떨어진 노드 개수 계산
    max_edge= max(route)
    for r in route:
        if r == max_edge:
            answer+=1     
            
    return answer

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치각 바위 사이의 거리거리의 최솟값

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

입출력 예

내 문제풀이

1. 바위 사이 거리를 기준으로 이진탐색을 수행한다. 가능한 바위 사이 거리는 대략 0~1000000000으로 두고 최솟값을 left, 최댓값을 right로 설정한다.

2. mid는 현재 turn에서의 최소 바위 사이 거리이다. 이 보다 작을 수는 없으며, 크거나 같을 수는 있다.

3. rocks를 하나 씩 보며 각 바위 사이의 거리와 mid를 비교한다.
mid보다 작은 경우, 뒷 바위(현재 위치)를 제거하는 것으로 판단하여 count(제거한 바위 갯수) +1 한다.
이 외의 경우, 현재 turn에서 바위 사이 거리의 최솟값(변수 dist)을 계산하고 앞 바위를 현재 위치로 이동시킨다.

4. 모든 바위를 모두 탐색 후,
count가 n보다 크다면 더 적은 바위를 제거해야 하므로, mid를 줄이기위해 right = mid-1로 설정한다.
count가 n보다 작거나 같다면 더 많은 바위를 제거해야 하므로, mid를 늘리기위해 left = mid+1로 설정한다. 추가적으로 우리는 각 turn에서의 최소 바위 거리 중 "최댓값"을 구해야 하기 때문에 mid를 늘릴 때 answer을 현재 turn의 최소 바위 거리(변수 dist)를 재설정한다.

5. 이진탐색이 종료되면 answer를 반환한다.

내 코드 - 파이썬

def solution(distance, rocks, n):
    answer = 0
    left, right = 0, distance
    rocks.sort()
    rocks.append(distance)
    
    while left <= right:
        dist = 1000000000
        mid = (left+right)//2 #현재 지정한 최소 바위 사이 거리
        count = 0 # 제거한 바위 갯수
        now = 0 #앞 바위
        
        for rock in rocks: #뒷 바위
            #현재 mid를 최소라고 가정했으므로, 더 작으면 뒷 바위 삭제
            if rock-now < mid:         
                count +=1 
            else:
                dist = min(dist, rock-now)
                now = rock
                
        if count > n:
            right = mid-1
        else:
            left = mid+1
            answer = dist #최솟값 중 최댓값이므로 바위 거리를 더 키워야하는 경우 저장
            
    return answer

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

내 문제풀이

1. 심사에 소요될 수 있는 가능한 시간(1~n*max(times)을 기준으로 이진탐색을 수행한다. 최솟값(1)은 변수 left, 최댓값(n*max(times))는 변수 right, left와 right의 중간값은 변수 mid로 설정한다.

2. mid는 현재 turn에서 가정하는, 심사에 소요되는 시간이다. 이 시간동안 각 심사관들이 총 몇 명을 심사할 수 있는지 계산한다. (변수 people에 저장)

3. 만약 people이 n보다 크다면, 심사에 소요되는 시간(mid)를 줄여야하므로, right = mid-1로 설정한다. 그리고 소요 시간의 "최솟값"을 찾아야하므로, mid를 answer에 저장해둔다. 만약 people이 n과 같다면, 현재 mid보다 더 최솟값을 찾을 수 있는 확률이 있기때문에 n보다 큰 경우와 동일한 작업을 수행한다. 

4. people이 n보다 작다면, 심사에 소요되는 시간(mid)를 늘려야하므로, left = mid+1로 설정한다.

5. 이진탐색을 수행하다 left가 right보다 크게 되면 탐색을 종료하고 answer를 반환한다.

내 코드 - 파이썬

def solution(n, times):
    answer = 0
    left, right = 1, n*max(times)
    
    while left<=right:
        mid = (left+right)//2
        people=0
        for time in times:
            people += mid//time #총 시간동안 각 심사관이 처리할 수 있는 사람 수 
            #일단 총 사람 수(n)보다 넘으면 반복문 종료
            if people > n: break
        
        if people >= n: 
            right = mid-1
            answer = mid # 최솟값을 찾아야 하므로 일단 저장
        else:
            left = mid+1
    
    return answer

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

내 문제풀이

1. 변환할 수 없는 경우의 예외처리를 먼저 수행한다.

2. 기준이 될 현재 단어들을 word_list에 저장하며 words에서 word_list들과 비교했을 때 한 글자만 다른 글자들을 차례대로 찾는다. word_list는 begin 단어로 초기화하고 시작한다.

3. word_list와 한 글자만 다른 글자들을 찾아 diff_word에 삽입하고 words에서 삭제한다. 
모든 word_list와 수행한 후,
- diff_word에 target이 있다면 바로 answer(begin부터 한 글자씩 달라질 때마다 +1)를 반환한다. 
- diff_word에 target이 없다면 다음 턴에 비교할 현재 단어 리스트(word_list)를 diff_word로 치환하고 2번을 반복한다.

내 코드-파이썬

def solution(begin, target, words):
    if target not in words:
        return 0
    
    answer = 0
    word_len = len(begin)
    word_list = [begin]
    diff_word = list()
    
    while(1):
        for wl in word_list:
            diff_word.clear()
            for word in words:
                diff = 0
                for idx in range (0, word_len):
                    if wl[idx] != word[idx]: diff += 1
                    if diff > 1: break
                if diff==1: # 1글자 차이
                    diff_word.append(word)
                    words.remove(word)
        
        answer += 1            
        if target in diff_word: return answer
        else: word_list = diff_word
            

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

내 문제풀이

1. 현재 컴퓨터와 연결된 컴퓨터가 있는 경우, 해당 컴퓨터와 연결된 다른 컴퓨터를 계속해서 탐색하기 위해서 DFS를 사용했다. DFS는 stack, 재귀함수를 활용한다.

2. 네트워크 갯수를 계산하는 answer, 연결된 컴퓨터를 표시하기 위한 stack을 초기화한다.

3. 0번 컴퓨터부터 각 컴퓨터별 네트워크를 확인하기 위해 반복문을 수행한다. 반복문 내에서는 dfs() 함수를 호출한다. 
예외처리로는 2가지 경우를 구현했다.
- 현재 컴퓨터 번호가 stack에 표시되어 있다면, 이미 네트워크에 포함되어 있다는 것이기 때문에 dfs() 를 호출하지 않고 continue를 수행한다. 
- stack의 값이 모두 1이라면, 바로 answer를 반환한다.

4. dfs() 함수는 다음의 총 4개의 인자를 받는다.
n(총 컴퓨터 갯수), idx(현재 컴퓨터 번호), computers(컴퓨터 연결 정보 배열), stack(연결된 컴퓨터 표시)
해당 함수는 현재 컴퓨터와 연결되어 있으며, stack에 표시되지 않은 컴퓨터가 있는 경우를 탐색한다. 이 경우, 새로운 컴퓨터를 stack에 표시하고 해당 컴퓨터 번호로 dfs()를 다시 호출한다. 마지막에는 stack을 반환한다.

5. solution()에서 dfs()를 반복 호출하고, dfs() 내에서 재귀적으로 수행하다보면, 최종 결과 값이 반환된다.

내 코드-파이썬

def dfs(n, idx, computers, stack):
    for i in range(0, n):
        if computers[idx][i]==1 and stack[i]==0: #연결되어 있고, stack에 표시 x
            stack[i] = 1
            dfs(n, i, computers, stack)
    return stack

def solution(n, computers):
    answer = 0 #네트워크 갯수
    stack = [0]*n #연결된 컴퓨터 표시
    for c in range(0, n): #각 컴퓨터별 네트워크 확인
        if stack[c] == 1: continue
        if sum(stack)==n: return answer
        answer += 1        
        stack = dfs(n, c, computers, stack)
        
    return answer

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

내 문제풀이

1. numbers 배열의 각 숫자마다 +와 -를 사용한 모든 계산을 수행하기 위해 재귀함수를 활용한 DFS를 구현한다.

2. dfs함수의 인자로는 (numbers 배열의 숫자를 선택할 index, 차례대로 계산 중인 결과 값, numbers, target) 이다.

3. 재귀함수를 호출할 때마다 index는 1씩 증가시키고, 계산은 각 숫자를 + 또는 -하여 수행한다.

4. index가 numbers의 길이와 같아지면 numbers의 모든 숫자를 사용한 것이므로 현재까지의 계산 결과가 target과 같은지 확인하고 해당 함수 주기를 return 0으로 종료한다.

5. 만약 현재까지의 계산 결과가 target과 같다면 answer(타겟 넘버 생성할 수 있는 방법의 수)를 +1 한다.

내 코드-파이썬

answer=0

def dfs(idx, cur, numbers, target):
    global answer
      
    if idx==len(numbers):
        if cur == target:
            answer += 1
        return 0
    
    dfs(idx+1, cur+numbers[idx], numbers, target)
    dfs(idx+1, cur-numbers[idx], numbers, target)

def solution(numbers, target):
            
    dfs(0, 0, numbers, target)
    return answer

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

내 문제풀이

1. 위 처럼 패턴을 갖고 5를 4번 사용하는 경우 -> 1번 사용&3번 사용, 2번 사용& 2번 사용, 3번 사용&1번 사용 값을 활용한다.

2. n번 사용할 경우 n//2번을 넘어가면 이전 계산과 중복되므로 1~n//2+1 번까지 반복문을 수행한다. 반복문 내에서는 위의 패턴대로 각 숫자의 사용 횟수별 사칙연산을 수행한다.

3. 계산한 사칙연산 리스트에 number가 있다면 몇 번 사용했는지의 값(i)를 반환한다.

4. 계산한 사칙연산 리스트에 number가 없다면 다음 횟수 계산을 위해 total에 계산한 값 리스트(num_list)을 추가해준다.

5. 최솟값이 8보다 클 수 없다고 제한 조건을 주었기 때문에 반복문 내에서 정답이 반환되지 않으면 -1을 반환한다.

내 코드 - 파이썬

def solution(N, number):
    total = [0, [N]] # 사용횟수 별 계산 값 저장 리스트
    if N==number: return 1

    for i in range(2, 9):
        num_list = [int(str(N)*i)] # 단순 반복 값 초기화
        for j in range(1, i//2+1):
            for a in total[j]:
                for b in total[i-j]:
                    num_list.append(a+b)
                    num_list.append(a*b)
                    num_list.append(a-b)
                    num_list.append(b-a)
                    if a!=0 : num_list.append(b//a)
                    if b!=0 : num_list.append(a//b)
        if number in num_list : return i
        total.append(num_list)
    
    return -1