8618번 - Taśma
조니는 집에서 매우 긴 테이프를 발견했습니다. 조니는 한 치의 망설임도 없이 그 테이프에 수들을 써내려가기 시작했습니다. 수들을 다 쓴 조니는 테이프에서 가장 멀리 떨어져 있는 서로 다른 두 개의 수를 찾으려고 합니다.
이때 인접한 두 수 사이의 거리를 1, 공통된 이웃이 있는 수 사이의 거리를 2라고 생각합니다.
1
2
첫 번째 줄에는 테스트 케이스의 개수 m이 입력됩니다. (1 <= m <= 10)
m
(1 <= m <= 10)
각 테스트 케이스에는 조니가 테이프에 쓴 수의 개수 n이 입력됩니다. (1 <= n <= 100 000) 그 다음 줄에는 조니가 테이프에 쓴 n개의 수 a_i가 공백으로 구분되어 입력됩니다. (1 <= a_i <= 1 000 000 000)
n
(1 <= n <= 100 000)
a_i
(1 <= a_i <= 1 000 000 000)
출력은 각 테스트 케이스에 대한 답을 포함하는 m개의 줄로 구성되어야 합니다.
각 테스트 케이스에 대해서 가장 멀리 떨어져 있는 서로 다른 두 수 사이의 거리를 출력합니다. 만약 그러한 수가 없으면 "BARK"를 출력합니다.
첫 번째 예제에서 가장 멀리 떨어져 있는 서로 다른 두 수는 첫 번째 수 2와 일곱 번째 수 5입니다.
5
개인적인 바람으로는 '공통된 이웃' 에 대한 설명이 추가되었으면 합니다..
공통된 이웃이 있는 수는 1 2 3에서 1과 3을 의미합니다. 이때 공통된 이웃은 2입니다.
원문에는 관련 내용이 없는 것 같아 댓글로 남깁니다.
감사합니다.
숫자와 수를 구분해서 작성해 주세요
제가 아직 뉴비라 한가지만 더 질문드립니다.
공통된 이웃 이라는 표현이 알고리즘문제를 풀때 일반적으로 통용되고 있는 표현인가요?
보통 격자 등을 이용하는 문제에서 종종 보이는데 이 문제는 조금 특이한 케이스인 것 같습니다.
아니면 번역기 돌린 걸 다듬은 정도라 그 과정에서 오역되었을 수도 있고요.
떨어진 거리가 2인 두 수의 관계를 설명할 때 공통된 이웃이란 표현을 굳이 쓴 이유는 여기에 다시 거리 개념을 가지고 오면 거리를 설명하기 위해 거리를 사용해 어폐가 되어 그런 거 같습니다.
@unta 친절한 답변 감사합니다!!@_@
댓글을 작성하려면 로그인해야 합니다.
unta 2년 전 3
문제
조니는 집에서 매우 긴 테이프를 발견했습니다. 조니는 한 치의 망설임도 없이 그 테이프에 수들을 써내려가기 시작했습니다.
수들을 다 쓴 조니는 테이프에서 가장 멀리 떨어져 있는 서로 다른 두 개의 수를 찾으려고 합니다.
이때 인접한 두 수 사이의 거리를
1, 공통된 이웃이 있는 수 사이의 거리를2라고 생각합니다.입력
첫 번째 줄에는 테스트 케이스의 개수
m이 입력됩니다.(1 <= m <= 10)각 테스트 케이스에는 조니가 테이프에 쓴 수의 개수
n이 입력됩니다.(1 <= n <= 100 000)그 다음 줄에는 조니가 테이프에 쓴
n개의 수a_i가 공백으로 구분되어 입력됩니다.(1 <= a_i <= 1 000 000 000)출력
출력은 각 테스트 케이스에 대한 답을 포함하는
m개의 줄로 구성되어야 합니다.각 테스트 케이스에 대해서 가장 멀리 떨어져 있는 서로 다른 두 수 사이의 거리를 출력합니다.
만약 그러한 수가 없으면 "BARK"를 출력합니다.
힌트
첫 번째 예제에서 가장 멀리 떨어져 있는 서로 다른 두 수는 첫 번째 수
2와 일곱 번째 수5입니다.