2023. 4. 13. 14:36ㆍ알고리즘/문제
연속 부분 수열
출처: 프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/131701
문제는 위의 링크에서 확인 부탁드립니다.
간단하게 설명드리면,
수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 나올 수 있는 경우는
길이가 1인 연속 부분 수열로부터 [1, 4, 7, 9] 네 가지의 합이 나올 수 있습니다.
길이가 2인 연속 부분 수열로부터 [2, 5, 10, 11, 16] 다섯 가지의 합이 나올 수 있습니다.
길이가 3인 연속 부분 수열로부터 [6, 11, 12, 17, 20] 다섯 가지의 합이 나올 수 있습니다.
길이가 4인 연속 부분 수열로부터 [13, 15, 18, 21] 네 가지의 합이 나올 수 있습니다.
길이가 5인 연속 부분 수열로부터 [22] 한 가지의 합이 나올 수 있습니다.
이들 중 중복되는 값을 제외하면 다음과 같은 18가지의 수들을 얻습니다.
[1, 2, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15, 16, 17, 18, 20, 21, 22]
원형수열의 모든 원소가 담긴 intArray 를 주고 나올 수 있는 모든 경우의 개수를 구하면 됩니다.
저는 간단하게 3중 for문으로 풀었습니다.
더 빠르게 풀 수 있는 방법이 분명히 존재하겠지만 처음 보았을 때 풀었던 방법은 아래와 같습니다.
풀이
class Solution {
fun solution(elements: IntArray): Int {
var answer: Int = 0
val arr = elements+elements
val numSet = HashSet<Int>()
for(i in 1..elements.size) {
for(j in elements.indices) {
var sum = 0
for(k in j until j+i) {
sum += arr[k]
}
numSet.add(sum)
}
}
return numSet.size
}
}
3중 for문을 이용해
첫번째 반복으로 먼저 개수를 반복합니다.
개수가 1개
개수가 2개
개수가 3개
...
끝날 때까지 갑니다.
그리고 elements.indices 즉, elements의 원소 index를 0부터 끝까지 선형 탐색합니다.
그 안에 k가 0부터 몇 개를 더하면서 가는지 확인합니다.
개수가 i=1일 때, j는 0,1,2,3,4를 반복하는데
j=0일 때, k는 j=0부터 0+1(i=1)전까지 반복합니다. j는 0을 확인하여 sum에 더합니다.
그리고 k반복이 끝나고 set에 sum을 추가합니다.
j=1일 때, k는 j=1부터 1+1전까지 반복하고 j는 1을 확인하여 sum에 더합니다.
k반복이 끝나고 set에 sum을 추가하여 나올 수 있는 경우를 set에 추가합니다.
이렇게 3중 for문을 이용하여 개수를 먼저 정하고 그 뒤에 0 시작, 1 시작일 때 개수만큼 반복하면서 더하고 더해서 나오는 숫자가 겹치지 않게 set으로 처리하는 방법입니다.
이상. 읽어주셔서 감사합니다.
'알고리즘 > 문제' 카테고리의 다른 글
프로그래머스 Level2 프린터 (0) | 2023.04.14 |
---|---|
프로그래머스 Level2 기능 개발 (0) | 2023.04.13 |
프로그래머스 Level2 예상 대진표 (0) | 2023.04.11 |
프로그래머스 Level 2 광물 캐기 (0) | 2023.04.03 |
프로그래머스 Level 3 순위 (2) | 2023.03.21 |