[Programmers] #181881 - 조건에 맞게 수열 변환하기 2 [Java][C++][Python]

문제 링크

---

1. 아이디어

주어진 연산을 배열 전체에 한 번 적용하는 것을 한 단계로 보고, 배열이 더 이상 변하지 않을 때까지 시뮬레이션하며 단계 수를 세면 된다. 유한 횟수 내에 종료됨을 문제에서 보장하므로 무한 루프를 활용해 반복하다가 변하지 않는 순간 탈출했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times K)$	$O(N)$

($N$ = arr의 길이, $K$ = 변환이 멈출 때까지의 단계 수)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int[] arr) {
        int[] prv = arr;
        int cnt = 0;

        while (true) {
            int[] cur = step(prv);

            if (Arrays.equals(prv, cur)) return cnt;
            prv = cur;
            cnt++;
        }
    }

    static int[] step(int[] arr) {
        int[] res = arr.clone();

        for (int i = 0; i < res.length; i++) {
            if (res[i] >= 50 && res[i] % 2 == 0) {
                res[i] /= 2;
            } else if (res[i] < 50 && res[i] % 2 != 0) {
                res[i] = res[i] * 2 + 1;
            }
        }

        return res;
    }
}

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

vector<int> step(vector<int> v) {
    for (int& x : v) {
        if (x >= 50 && x % 2 == 0) {
            x /= 2;
        } else if (x < 50 && x % 2) {
            x = x * 2 + 1;
        }
    }

    return v;
}

int solution(vector<int> arr) {
    vector<int> prv = arr;
    int cnt = 0;

    while (true) {
        vector<int> cur = step(prv);

        if (prv == cur) return cnt;
        prv = cur;
        cnt++;
    }
}

def transform(x):
    if x >= 50 and x % 2 == 0:
        return x // 2
    if x < 50 and x % 2:
        return x * 2 + 1
    return x


def solution(arr):
    prv = arr
    cnt = 0

    while True:
        cur = [transform(x) for x in prv]
        if prv == cur:
            return cnt
        prv = cur
        cnt += 1

---