-
알고리즘 문제 해설 | 프로그래머스 (programmers.co.kr)
길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.제한사항
- 배열의 길이는 10만 이하입니다.
- 배열의 원소는 0 이상 10만 이하인 정수입니다.
입출력 예
입출력 예 설명
입출력 예 #1
입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다.입출력 예 #2
[4, 1, 3]이 주어진 경우, 배열의 길이가 3이므로 배열에는 1부터 3까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3]에는 2가 없고 4가 있으므로 false를 반환하면 됩니다.
문제 풀이 (1)
int chk[100001] = {0};
제한 사항인 1~10만이므로 위와 같이 설정해놓는다
int n = arr.size();
배열의 크기는 임의로 제공되므로, 변수 n에 arr.size를 통해 배열의 크기를 저장한다.
for(int i=0; i<n; ++i) { ... }
포문을 통해 배열을 모두 검사해야하므로 반복은 배열의 크기만큼 진행.
if(arr[i] < 1 || arr[i] > n) return false; chk[arr[i]]++;
제한 사항에서는 정수이므로 0도 포함되지만, 문제에서 1부터 시작한다고 가정하였으므로,
다음과 같이 배멸에 1보다 작은 경우는 false를,
또한 3의 크기의 배열에는 4가 들어가면 안되므로, n보다 크면 false를 출력합니다.
이 조건이 충족되었을 때, 체크용 배열에 값을 1씩 넣습니다.
for(int i=1; i<=n; ++i) if(chk[i] != 1) return false;
이 값에서 1이외에 값이 있다면, 중복된 값이 있다는 것이므로, false를 출력하게 하면 됩니다.
int i 가 왜 0부터 시작하지 않을까?
→ (내 생각) chk 배열은 arr에서 각각의 칸의 있는 수를 chk 배열의 해당 arr[i]의 값을 넣었음...
arr
4 3 2 1 이었다면,
chk[arr[i]]++; 을 통해서 chk[arr[1]] -> chk[4]++; 이므로
chk
1 이 된다. 앞서 chk는 배열의 크기가 '10만1' 으로 지정해놨기 때문에, 앞서 0은 예외로 처리했으므로, 0의 값이 의미가 없다... 따라서 이와 같이 모든 반복을 다 했을 때, chk 배열의 값이 1부터 n의 칸까지 모두 1이라면 문제에 해당하는 true가 출력되면 된다.
문제 풀이 (2)
sort(arr.begin(), arr.end());
주어진 배열을 시작과 끝을 오름차순으로 정렬한다.
if(arr[i] != i+1) return false;
배열은 1부터 n까지의 자연수이므로 arr[0]에는 1이 들어가있으므로,
for (int i = 0; i < arr.size(); ++i) 을 사용하여, 모든 배열을 검사한다.
이때 i+1의 값이 아닌 결과는 중복 값을 의미하므로, false를 출력한다.
'개발 > 알고리즘' 카테고리의 다른 글
알고리즘_ 1이 될 때까지, 반복하기. (0) 2021.12.14 알고리즘_ 자릿 수 더하기 (0) 2021.10.08 알고리즘_ 평행한 사각형에서 3개의 점과 나머지 한 점 (0) 2021.10.08 [백준/BOJ] JAVA_1330번 숫자 비교 하기 (자바) (0) 2021.07.29 [백준/BOJ] JAVA_2588번 곱셉 과정 출력하기 (자바) (0) 2021.07.27 댓글 (비로그인 댓글 허용하지 않습니다.)