[자바] 백준 27159 - 노 땡스! (java)

 문제 : boj27159

---

 

필요 알고리즘 개념

• 구현
  
  • 제시된 조건에 따라 구현해주면 된다.

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

 

---

 

풀이

  N개의 입력 앞에 0을 추가하고 생각해보자.

int[] arr = [0, 6, 7, 10, 12, 13, 14, 15, 20, 21, 22] 와 같이 배열이 있다고 해보자.

그럼 arr[x]에서 'x=1부터 배열끝까지' 차례대로 보면서, arr[x-1] != arr[x]-1 이라면 연속된 그룹의 시작점에 해당하게 된다. (0을 추가한 것은, arr[x]는 최소 3, 최대 35 이므로 0이면 무조건 연속되지 않기 때문이다.)

 

  따라서 x를 1부터 배열끝까지 증가시키면서 arr[x-1] != arr[x]-1 인 횟수를 세주면 답이 된다. 이하 코드는 카운팅정렬 후 동일한 개념으로 푼 코드이다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[36];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[Integer.parseInt(st.nextToken())]++;
        int sum = 0;
        for (int i = 3; i <= 35; i++) {
            if (arr[i-1]==0&&arr[i]!=0)
                sum+=i;
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}