MissingInteger 알고리즘 문제풀이

2018-11-26
블로그 UI가 개편중입니다. 참고해주세요.

1. 문제

말 그대로 빠진 숫자를 찾는 알고리즘이다. 아래와 같은 함수가 있는데 N 개의 정수 중 A 배열이 주어진다면, A에서 발생하지 않는 가장 작은 양의 정수 (0보다 큼)를 반환한다.

class Solution { public int solution(int[] A); }

아래의 경우 결과값은 5이다.

A = [1, 3, 6, 4, 1, 2]

또 다른 예로 아래의 같은 경우에는 연속된 숫자의 최대값에서 +1 인 4가 된다.

A = [1, 2, 3]

다른 예로 음수인 경우 양수의 최저값인 1이 결과값이 된다.

A = [-1, -3]

2. 풀이

먼저 A배열을 순회하며 A[idx] 값을 map에 담았다. 그중에서 제일 큰 값을 max 값으로 담았다. 두 번째 순회에서는 max 사이즈만큼 순회하면되고, 순회중에 빠진 숫자가 나온다면 해당 숫자를 리턴하고, 만약 순회의 idx 값이 max 값과 같다면 +1하여 값을 반환하면 해결된다.

3. 링크

Prev

MaxCounters 알고리즘 문제풀이

1. 문제 인자 N과, int 배열 A가 주어진다. N은 새로운 int 배열의 사이즈이고 가칭 tmp 배열이라 칭한다. 배열 A의 요소들이 tmp 배열의 index가 되어 값을 1씩 증가시킨다. 만약 A의 특정 요소가 N 사이즈보다 크다면 max counter가 발생하여 tmp 배열의 모든...

FrogRiverOne 알고리즘 문제풀이

1. 문제 개구리가 X 크기의 강을 건너려고 한다. 1초마다 X의 특정 위치에 나뭇잎이 떨어지는데, 몇 초를 기다리면 개구리는 강을 건널 수 있을까? 예 강의 크기가 5이고 아래처럼 나뭇잎이 떨어진다고 가정하면 개구리는 6초만에 강을 건널 수 있다. A[0] = 1 A[1]...

PermCheck 알고리즘 문제풀이

알고리즘 스터디에서 진행 중인 내용입니다. 1. 문제 랜덤 숫자로 이루어진 배열 A가 있다. 이 배열 A가 순열인지 확인하여 순열인 경우에 1을 반환하고 아닌 경우에 0을 반환하는 알고리즘을 작성하라. A[0] = 4 A[1] = 1 A[2] = 3 A[3] = 2...

TageEquilibrium 알고리즘 문제풀이

알고리즘 스터디에서 진행 중인 내용입니다. 1. 문제 숫자의 배열로 이루어진 A가 있고, 배열 A는 랜덤한 P 값에 의해 분리된다. P 값을 기점으로 |좌측의 합 - 우측의 합| 중 가장 작은 수를 구하라. P의 조건 0 < P < N 2....