[BaekJoon] 2331번 - 반복수열 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 수열에 해당 규칙을 적용할 시 언젠가는 반복되는 구간이 나온다고 전제하고 있어서 무한 루프를 활용하다가 해당 조건을 만나면 출력 후 종료를 해줬다. 특정 수가 등장했는지 여부를 알아야하며 반복되지 않는 구간의 길이를 위해 각 수의 등장 위치가 필요해서 해시맵 자료구조로 키에 해당 수, 값에 등장 순서를 저장해서 반복되는 수가 등장한 순간 기존에 존재했던 위치에서 한 칸 앞을 반환하면 반복되지 않는 구간의 길이와 같다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());

        Map<Integer, Integer> map = new HashMap<>();
        int idx = 1;
        int cur = a;

        while (true) {
            map.put(cur, idx);

            int next = 0;
            while (cur > 0) {
                int r = cur % 10;
                int tmp = 1;
                for (int i = 0; i < p; i++) {
                    tmp *= r;
                }

                next += tmp;
                cur /= 10;
            }

            if (map.containsKey(next)) {
                System.out.println(map.get(next) - 1);
                return;
            }

            idx++;
            cur = next;
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, p;
    cin >> a >> p;

    unordered_map<int, int> mp;
    int idx = 1;
    int cur = a;

    while (true) {
        mp[cur] = idx;

        int next = 0;
        while (cur > 0) {
            int r = cur % 10;
            int tmp = 1;
            for (int i = 0; i < p; i++) {
                tmp *= r;
            }

            next += tmp;
            cur /= 10;
        }

        auto it = mp.find(next);
        if (it != mp.end()) {
            cout << it->second - 1;
            return 0;
        }

        idx++;
        cur = next;
    }
}

---