Skip to main content

29. [Java] 가까운 1 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/181898

  • 정수 배열 arr가 주어진다.
  • 이때 arr의 원소는 1 또는 0이다.
  • 정수 idx가 주어졌을 때, idx보다 크면서
  • 배열의 값이 1인 가장 작은 인덱스를 찾아서 return
  • 단, 만약 그러한 인덱스가 없다면 -1을 return
  • 3 ≤ arr의 길이 ≤ 100'000
  • arr의 원소는 전부 1 또는 0이다.

정답코드

아래 코드가 답인 이유는 인덱스는 오름차순이기 때문이다. idx보다 큰 인덱스 중 제일 먼저 값이 1인 인덱스, 즉 처음 1을 만났을 때의 인덱스를 즉시 return 하면 된다. 1이 없다면 -1을 반환해야 하므로, 전체를 다 돌아도 1을 못 찾으면 -1 을 반환한다.

class Solution {
    public int solution(int[] arr, int idx) {
        for(int i = idx; i < arr.length; i++) {
            if (arr[i] == 1) {
                return i; // 가장 먼저 나오는 1의 인덱스 반환
            }
        }
        return -1; // 끝까지 1이 없으면 -1 반환
    }
}
  • 배열 arr에서 idx 이상의 인덱스 중 가장 먼저 등장하는 값이 1인 인덱스를 찾는 코드
  • 즉, 오름차순 방향(왼쪽 → 오른쪽) 으로 탐색 중 처음 만나는 1의 인덱스를 즉시 return 한다.
  • 1이 없다면 -1을 반환해야 하므로, 전체를 다 돌아도 못 찾으면 -1 반환

오답

for문 안에 로직을 잘못 설계했고, 인덱스를 비교해서 return해야 하는데 값을 비교하는 코드를 짜서 오답처리됨

class Solution {
    public int solution(int[] arr, int idx) {
        int result = 0;
        int min = 0;
        for(int i = idx; i < arr.length; i++) {
            min = arr[idx];
            if (arr[i] == 1) {
                min = Math.min(min, arr[i]);
            }
        }
        return (min>0) ? min : -1;
    }
}

image.png

for(int i = idx; i < arr.length; i++) {
    min = arr[idx]; // 매번 같은 값으로 덮어씀
    if (arr[i] == 1) {
        min = Math.min(min, arr[i]); // 항상 1과 arr[idx] 비교 (불필요)
    }
}
  • min = arr[idx];이 줄이 반복문 내부에 있어서 min은 매번 같은 값으로 덮어쓰기 된다.
    → 즉, arr[i]가 어떤 값이든 상관없이 min은 항상 arr[idx]로 초기화 된다.
  • Math.min(min, arr[i]) → 항상 Math.min(1, 1) 또는 Math.min(0, 1)이라 의미 없음
  • 그리고 최종 리턴값 min은 "값"이지 "인덱스"가 아니다.

수정한 부분

class Solution {
    public int solution(int[] arr, int idx) {
        for (int i = idx; i < arr.length; i++) {
            if (arr[i] == 1) {
                return i; // 처음 등장하는 인덱스를 즉시 반환
            }
        }
        return -1; // 못 찾은 경우
    }
}
  • idx부터 배열 끝까지 순회
  • arr[i] == 1을 처음 만났을 때 그 i를 반환
  • 없다면 -1 반환




Back to top