그냥 코딩하는 사람의 블로그

문제 설명

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이 과정

일반적인 BFS 문제하고는 좀 다르다. 왜냐하면 걸을때는 1초 걸리고, 순간이동을 하는 경우에는 0초 걸리기 때문에 최단 시간을 구하기 애매하다. 따라서, 현재 위치에서 가능할때까지 2배만 사용해서 쭉 가보고, 왼쪽, 오른쪽으로 이동하는 방식으로 구현해야 한다.

1. BFS를 진행한다.
   • 덱에는 [현재 위치, 현재 위치까지의 비용] 형식으로 저장한다.
   • 현재 위치가 동생이 있는 위치인지 검사한다.
   • 현재위치 * 2, 현재위치 + 1, 현재위치 - 1 순서로 덱에 넣는다.
     • 이 때, 현재 위치 * 2를 덱의 왼쪽에 삽입한다. => 가장 먼저 현재 위치 * 2를 방문하도록 함.
     • 나머지의 경우는 덱의 오른쪽에 삽입한다.
     • 이런 식으로 구현하면, 예시로 비용이 2라고 할 때, N-1, N-2, N, N+1, N+2 위치에서 순간이동을 하여 갈수 있는 모든 지점을 갈 수 있다.
2. BFS 진행 중에, 동생이 있는 위치에 오게 되면 비용을 출력하고 종료한다.

소스 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

queue = deque([[N, 0]])
visited = [False] * 100001
visited[N] = True
answer = int(10e9)
while queue:
    next_x, cost = queue.popleft()
    if next_x == K:
        answer = cost
        break

    for step in [next_x * 2, next_x+1, next_x-1]:
        if 0 <= step <= 100000 and not visited[step]:
            if step == next_x * 2:
                queue.appendleft([step, cost])
            else:
                queue.append([step, cost+1])
            visited[step] = True

print(answer)

문제 설명

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

풀이 과정

1. 점들을 오름차순으로 정렬해 준다. => 이진탐색을 하기 위함.
2. 입력받은 선분의 두개의 점을 이진탐색을 진행한다.
   • 파이썬의 bisect_left, bisect_right 함수를 사용한다. 간단하게 설명하자면 bisect_left(x, a)는 a를 x에 삽입할 때, 삽입해야 할 위치를 리턴한다. left와 right의 차이는 왼쪽에 삽입할지, 오른쪽에 삽입할지의 차이이다.
   • 선분의 작은 점은 bisect_left => 작은 점을 포함하게 하기 위해
   • 선분의 큰 점은 bisect_right => 큰 점을 포함하게 하기 위해
   • 위의 두 인덱스 사이에 있는 모든 점들이 선분 안에 포함된다.
3. 점의 개수를 리턴해주면 된다.

소스 코드

from bisect import bisect_left, bisect_right
import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
points = list(map(int, sys.stdin.readline().rstrip().split()))
points.sort()

for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    lidx = bisect_left(points, a)
    ridx = bisect_right(points, b)
    print(ridx - lidx)

문제 설명

문제

홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.

 100000 이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 정수 N (1≤N≤200000)과 K(1≤K≤100)가 주어진다.

둘째 줄에는a1,a2,...an{a_1, a_2, ... a_n}$이 주어진다 (1≤ai≤100000)

출력

조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.

풀이 과정

• 원래는 투 포인터 문제 분류여서 투포인터 방식으로 구현하려 했으나.. 큐로 구현하는게 훨씬 편할 것 같아서 큐로 구현, 구현해보니 투포인터랑 크게 다를건 없는거 같다.

1. 원소의 개수를 매번 큐에서 세는 경우, 시간 초과가 발생할 수도 있으니 딕셔너리로 원수의 개수를 추가하면서 세줌.
2. 원소를 순차적으로 접근하면서 추가하였을 때, 원소의 개수가 K개를 넘는 경우
   • 추가한 원소를 빼줄때까지 큐의 왼쪽에서부터 빼준다.
3. 매 순간 queue가 언제 최대 길이가 되는지 저장해둔 다음, 마지막에 출력해주면 된다. (최장 연속 부분 수열의 길이)

소스 코드

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
numbers = list(map(int, input().rstrip().split()))
sequence = set()
dup_count = {i:0 for i in range(1, 100001)}
answer = 0

queue = deque()
for number in numbers:
    queue.append(number)
    dup_count[number] += 1
    # number에서 중복 문제 걸림
    if dup_count[number] > K:
        # number가 나올때까지 queue에서 싹 빼주어야 함.
        while queue:
            temp = queue.popleft()
            dup_count[temp] -= 1
            if temp == number:
                break
    answer = max(answer, len(queue))

print(answer)

풀이 과정

1. 재귀함수를 사용하여 구현하면 쉽게 구현할 수 있다.
   • 재귀함수를 통해 전체 사전을 구성
   • 구성한 사전들 중 입력받은 단어가 몇번째에 있는지 검사
2. 재귀함수의 하나의 함수 내에서 하는 역할은 다음과 같다.
   • 현재의 단어를 사전에 저장
   • A, E, I, O, U 각각을 붙여서 다음 재귀함수 호출
   • 단어의 길이가 6을 넘어가면 종료

소스 코드

dictionary = []

def recursion(p, step):
    if step == 6:
        return
    if p != '':
        dictionary.append(p)
    for c in ['A', 'E', 'I', 'O', 'U']:
        recursion(p+c, step+1)

def solution(word):
    answer = 0
    recursion('', 0)
    for i in range(len(dictionary)):
        if dictionary[i] == word:
            answer = i+1
            break

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

문제

최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.

최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
• 이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.

각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

풀이 과정

1. 그래프 구성
   • 의존성을 나타내는 정수 a, b, s를 b에서 a로 이동하기 위해 비용이 s가 든다고 가정하고 그래프 구성
2. 다익스트라 알고리즘 사용
   • 최소 히프를 사용하여 시간 절약
   • 현재 노드에서 이동 가능한 모든 정점을 이동하면서 비용 갱신
3. 총 감염된 컴퓨터 수, 마지막 감염 시간 출력
   • 총 감염된 수는 비용이 갱신된 컴퓨터의 수를 계산해주면 된다.
   • 마지막 감염 시간은 비용이 갱신된 컴퓨터들 중에, 비용의 최댓값을 구하면 된다.

소스 코드

import sys
import heapq

input = sys.stdin.readline

T = int(input().rstrip())
INT_MAX = int(10e9)

for _ in range(T):
    n, d, c = map(int,input().rstrip().split())
    graph = [[] for _ in range(n+1)]
    for __ in range(d):
        a, b, s = map(int, input().rstrip().split())
        graph[b].append([a, s])
    distance = [INT_MAX] * (n+1)
    distance[c] = 0
    heap = [[0, c]]
    while heap:
        cost, node = heapq.heappop(heap)
        if distance[node] != cost:
            continue

        for next_node, next_cost in graph[node]:
            if distance[next_node] > distance[node] + next_cost:
                distance[next_node] = distance[node] + next_cost
                heapq.heappush(heap, [distance[next_node], next_node])

    computer_count = 0
    time = 0
    for dist in distance:
        if dist != INT_MAX:
            computer_count += 1
            time = max(time, dist)

    print(computer_count, time)

문제 설명

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이 과정

1. 전체적으로 두가지 과정으로 진행된다.
   • 불이 퍼지는 과정
   • 상근이가 이동하는 과정
2. 상근이가 이동하는 경우(1초가 지난 경우), 이동하기 전에 불을 확산시킨다.
   • 이 부분은, bfs에서 queue에 step을 따로 저장하여, 이전 step과 현재 step이 다른 경우 이동한 것으로 간주
   • 따라서, 이전 step과 현재 step이 다른 경우 불을 한번 확산시키면 된다.
3. 불을 확산하는 경우는 한번 이루어지면 되므로, 함수로 구현.
   • 불의 위치를 입력받으면, 불의 위치에서 상하좌우로 불을 확산시키도록 구현
4. 배열의 인덱스를 벗어나는 경우, 탈출한 것이므로 step 출력
5. step을 출력하지 못하고 queue가 비게 되면, 탈출이 실패한 것이므로 IMPOSSIBLE 출력

• queue에서 다음 위치를 뺏을 때, 해당 위치에 불이 번져있다면 못가는 것임.. 이부분 처리를 안해줘서 1시간정도 걸린듯.

소스 코드

import sys
from collections import deque
import copy

input = sys.stdin.readline

T = int(input().rstrip())

def expand(matrix, fire):
    temp = []
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    w, h = len(matrix[0]), len(matrix)
    for x, y in fire:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if matrix[nx][ny] == '.':
                    matrix[nx][ny] = '*'
                    temp.append([nx, ny])

    return temp

for _ in range(T):
    # 입력부
    w, h = map(int, input().rstrip().split())
    matrix = [list(input().rstrip()) for _ in range(h)]
    # 초기
    visited = [[False] * w for _ in range(h)] 
    person_x, person_y = 0, 0
    fire = []
    # 불, 사람의 위치 저장
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '@':
                person_x, person_y = i, j
            if matrix[i][j] == '*':
                fire.append([i, j])

    queue = deque([[person_x, person_y, 0]])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[person_x][person_y] = True
    before = 0
    end = False
    while queue:
        x, y, step = queue.popleft()
        # 이동 => 불 확산
        if before != step:
            # 불 확산 + 확산된 불의 위치 저장
            fire = expand(matrix, fire)
            before = step

        if matrix[x][y] == '*':
            # 이번에 갈 곳에 불이 이미 번졌으면 못감
            continue

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    visited[nx][ny] = True
                    queue.append([nx, ny, step+1])
            else:
                # 범위 벗어나면 탈출한것이므로 출력
                print(step+1)
                end = True
                break
        if end:
            break
    if not end:
        print("IMPOSSIBLE")

문제 설명

문제

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

풀이 과정

• 처음엔 그냥 2차원 반복문으로 하면 안되나 했지만 .. 합을 구해야하는 횟수가 100000번이라서 안됨. DP를 사용해야 함.

1. DP[i][j]를 시작점에서부터 i행 j열까지의 표의 합계라고 두자.
   • 따라서, DP[i][j] = DP[i-1][j] + DP[i][j-1] + 표[i][j] - DP[i-1][j-1]
   • DP[i-1][j-1]을 빼주는 이유는, DP[i-1][j] + DP[i][j-1]을 할 때 겹치기 때문이다.
2. 이후, x1, y1, x2, y2를 입력받은 다음 해당 구간의 합계를 구한다.
   • 구간의 합계는 DP[x2][y2] - DP[x1-1][y2] - DP[x2][y1-1] + DP[x1-1][y1-1]
   • 마찬가지로, DP[x1-1][y1-1]을 더해주는 이유는 겹치기 때문에 두번 빼지게 되기 때문이다.
3. 구간의 합계를 출력해주면 된다.

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

matrix = ([[0] * (N+1)]) + (
    [[0] + list(map(int, input().rstrip().split())) for _ in range(N)]
) 
dp = [[0] * (N+1) for _ in range(N+1)]

for i in range(1, N+1):
    dp[i][1] = dp[i-1][1] + matrix[i][1]
    dp[1][i] = dp[1][i-1] + matrix[1][i]

for i in range(2, N+1):
    for j in range(2, N+1):
        dp[i][j] = matrix[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

for _ in range(M):
    x1, y1, x2, y2 = map(int, input().rstrip().split())
    area = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
    print(area)

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이 과정

1. DP 테이블을 구성한다
   • DP[i][j] : i를 합으로 나타낼 때, 맨 마지막에 사용할 수가 j
2. DP 테이블의 값을 미리 모두 채워둔다.
   • 최대 N이 100000이므로 100000개 모두 미리 채워둔다.
   • DP[i][1]의 값은 DP[i-2][2] + DP[i-3][3] 이러한 식으로 채워줌.
     • 이유는, 1을 사용하기 위해서는 이전에 2 또는 3이 나타나야 하기 때문.

• 어려웠던 점
  1. DP 테이블을 2차원으로 구성해야 되는 점 생각이 어려웠음..
  2. DP 테이블을 반복문에서 매번 초기화해줘서 시간 초과가 나타났는데, 이 점을 맨 위에서 모두 채워주고 아래에서 테스트 케이스를 입력받을 때, 대응되는 값을 바로바로 출력하도록 바꾸어 줌.

소스 코드

import sys

input = sys.stdin.readline
T = int(input().rstrip())

# dp[i][j] : i번째에 마지막으로 숫자가 j인 경우
dp = [[0, 1, 1, 1], [0, 1, 0, 0], [0, 0, 1, 0], [0, 1, 1, 1]] + (
    [[0] * 4 for _ in range(100001)]
)

for i in range(4, 100001):
    for j in [1, 2, 3]:
        for k in range(1, 4):
            # 이전에 나온 숫자를 바로 다시 나오게 하면 안됨.
            if j != k:
                dp[i][j] = (dp[i][j] + dp[i-j][k]) % 1000000009

for _ in range(T):
    n = int(input().rstrip())
    print(sum(dp[n]) % 1000000009)

문제 설명

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

풀이 과정

• 2차원 배열 DP 문제이다.

1. 점화식을 세워 보면, N번째 자리 숫자가 k라고 할 때, 가능한 경우의 수는 N-1번째 자리가 k 이상일때의 합계와 같다.
   • 첫번째 자리가 1이라면, 두번째 자리는 1부터 9까지가 나올 수 있고, 2라면 2부터 9까지, ...
   • 이 과정을 일의 자리에서부터 진행하면 된다.
   • 일의 자리인 경우에는 DP[1][i] = 1이다.
2. DP 테이블을 모두 채운 뒤, DP[N]의 합계를 구하면 된다. (길이가 N인 오르막 수의 개수)

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
dp = [[0] * 10 for _ in range(N+1)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, N+1):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007

answer = sum(dp[N]) % 10007

print(answer)

문제 설명

문제

N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력

첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

제한

• 1 ≤ N ≤ 100,000
• 0 ≤ M ≤ 2,000,000,000
• 0 ≤ |A[i]| ≤ 1,000,000,000

풀이 과정

1. 수열을 오름차순으로 정렬한다.
2. left, right를 0, 0으로 두고 시작.
   • array[right] - array[left]의 값에 따라 진행
   • M 이상이라면 left를 한칸 올린다.
   • M 이하라면 right를 한칸 올린다.
   • 이 때, left가 right보다 커질수도 있으니, 그러한 경우는 right도 한칸 올려서 맞추어 줌.
   • 진행하면서 array[right] - array[left] >= M인 경우 차이값의 최솟값 저장
3. 최솟값을 출력해주면 된다.

소스 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
array = [int(input().rstrip()) for _ in range(N)]

array.sort()
a, b = 0, 0
answer = int(10e9)
while b < len(array):
    subtraction = array[b] - array[a]

    if subtraction >= M:
        answer = min(answer, subtraction)

    if subtraction <= M:
        b = b + 1
    else:
        a = a + 1

    if a > b:
        b = b + 1

print(answer)