[ABC301] B - Fill the Gaps (AtCoder Beginner Contest 301 in Java)

목차

• 문제 : ABC301 - B
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : ABC301 - B

 

필요 알고리즘

• 구현
  
  • 문제에서 제시된 방법대로 구현하면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  직전 숫자와의 차이가 1 이상이라면 사이값을 채워넣어주면 된다.

List<Integer> res = new ArrayList<>();
res.add(arr[0]);
for (int i = 1; i < n; i++) {
    if (Math.abs(arr[i-1] - arr[i]) <= 1) {	// 직전과 차이가 1 이하라면 무시
        res.add(arr[i]);
        continue;
    }

    if (arr[i-1] < arr[i]) {	// 증가하는 형태로 채우기
        for (int j = arr[i-1]+1; j < arr[i]; j++)
            res.add(j);
    } else {	// 감소하는 형태로 채우기
        for (int j = arr[i-1]-1; j > arr[i]; j--)
            res.add(j);
    }

    res.add(arr[i]);
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
 
    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        List<Integer> res = new ArrayList<>();
        res.add(arr[0]);
        for (int i = 1; i < n; i++) {
            if (Math.abs(arr[i-1] - arr[i]) <= 1) {
                res.add(arr[i]);
                continue;
            }
 
            if (arr[i-1] < arr[i]) {
                for (int j = arr[i-1]+1; j < arr[i]; j++)
                    res.add(j);
            } else {
                for (int j = arr[i-1]-1; j > arr[i]; j--)
                    res.add(j);
            }
 
            res.add(arr[i]);
        }
 
        StringBuilder sb = new StringBuilder();
        for (Integer cur : res)
            sb.append(cur).append(' ');
 
        System.out.println(sb);
    }
}