알고리즘- (숫자의표현)

aquarius1997·2020년 5월 27일
0

Algorithm

목록 보기
7/9
  • 문제 출처 : 프로그래머스
  • 문제명 : 숫자의표현
  • 분류 : '연습문제'에 분류되어있음
  • 언어 : Java
  • 체감 난이도 : ⭐⭐
  • 풀이 시간 : 40min
  • Fail Cnt : 0


알고리즘 설계

1. 자료

1) sumArr
: 숫자 0부터 인덱스까지의 합을 저장한다.

예시

Index01234567...
value013610152128...

2. 문제 접근 방법

연속되는 숫자들을 합해서 숫자 n을 만드는 경우의 수는 다음과 같은 형태를 띄게된다.

ex) n = 15일 경우

1 + 2 + 3 + 4 + 5 : sum[5] - sum[0]
4 + 5 + 6 : sum[6] - sum[3]
7 + 8 : sum[8] - sum[6]
15 : sum[15] - sum[14]


코드

    public int solution(int n) {
        int answer = 0;
        int tempSum = 0;
        int diff = 0;
        ArrayList<Integer> sumArr = new ArrayList<Integer>();

	//인덱스 0에 대한 값(0)을 넣어주고 시작한다.
        sumArr.add(0);

	//tempSum 값 초기화
        //i가 3일 경우 숫자 1~3의 sum을 저장함
        for(int i=1; i<=n; i++) {
            tempSum = sumArr.get(i-1) + i;
            sumArr.add(tempSum);
        }

	//startIdx : 탐색을 시작할 인덱스, endIdx : 마지막 숫자 (ex. 1+2+3 으로 숫자 n을 만들 수 있는지 확인하려 할 때, endIdx는 3이다)
        int startIdx, endIdx;
        startIdx = endIdx = 0;

        //endIdx가 가르키는 값이 n보다 크거나 같을때까지로 이동한다
        while(true) {
            if(sumArr.get(endIdx) >= n) { break; }
            endIdx++;
        }

	//숫자 n을 만들 수 있는 경우의 수 카운팅
        while(endIdx < sumArr.size()) {
            diff = sumArr.get(endIdx) - n;  //n을 구하기 위해서 빼야할 값
            while(startIdx < endIdx) {
                if(diff == sumArr.get(startIdx)) {  //n값을 구할 수 있는 경우
                    answer++;   break;
                } else if(diff < sumArr.get(startIdx)) {    //endIdx이 마지막 숫자일 경우 n값을 구할수 없음.
                    break;
                } else {
                    startIdx++;
                }
            }
            endIdx++;
        }

        return answer;
    }
profile
안녕하세요😀😀

0개의 댓글