정수 대 로마 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple BlackRock 블룸버그 게시물에서 Evernote Facebook 구글 링크드 인 Microsoft 신탁 Twitter Yahoo
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학 조회수 51

이 문제에서는 정수가 주어지고 로마 숫자로 변환해야합니다. 따라서 문제는 일반적으로“Integer to Roman”이라고하며 이것은 Integer to Roman Leetcode Solution입니다. 누군가 로마 숫자에 대해 모르는 경우. 예전에는 사람들이 최근에 사용하던 정수를 사용하지 않았습니다.

로마 숫자는 일반적으로 왼쪽에서 오른쪽으로 내림차순으로 작성되지만 이에 대한 몇 가지 예외가 있습니다. 다음 숫자보다 작은 숫자가 있으면 양의 합에서 현재 숫자를 뺍니다. 일반적으로 같은 숫자를 3 번 ​​이상 반복하지 않는 것이 좋습니다. 정수에서 로마 숫자로 변환하려면 아래 이미지를 확인해야합니다.

정수 대 로마 Leetcode 솔루션

3
III

설명 : I는 1과 같으므로 합계 = 3을 얻기 위해 세 번 반복합니다.

4
IV

설명 : 우리는 I를 4 번 ​​이상 반복 할 수 없기 때문에 3 번 반복 할 수 없습니다. 그래서 우리는 V 앞에 I를 평면화합니다. I가 V보다 작기 때문에 1은 5와 같은 총합에서 뺍니다. 따라서 총합은 4가됩니다.

정수 대 로마 Leetcode 솔루션에 대한 접근 방식

"Integer to Roman"문제는 먼저 숫자를 가능한 가장 높은 숫자로 변환하려고 시도하는 탐욕스러운 방식으로 해결할 수 있습니다. 문제에 대한 무차별 대입 접근 방식은 실현 가능하지도 않고 일반적으로 적용 할 수 없기 때문에 불가능합니다. 이런 식으로 우리는 로마 숫자로 된 더 작은 교단으로 계속 이동합니다. 그러나이 방법은 4를 변환하려고하면 실패합니다.이 방법은 I를 4 번 인쇄합니다. 따라서이 문제를 해결할 방법을 찾아야합니다.

글쎄, 자세히 살펴보면이 예외에 부딪 힐 수있는 몇 가지 가능한 방법이 있습니다. 이 예외는 우리가 어떤 숫자를 3 번 ​​이상 반복하는 경우에만 해당됩니다. 따라서 예외가 될 수있는 정수를 작성하는 방법을 찾으십시오. 예외는 각각 IV, IX, XL, XC, CD, CM으로 변환 할 수있는 4, 9, 40, 90, 400, 900이라는 것을 알게됩니다.

예외 처리

그래서 지금까지 우리는 주어진 정수를 사용 가능한 원래의 단일 문자 로마 숫자로 변환하려고 생각했습니다. 그러나 예외를 피하기 위해 별도로 처리합니다. 따라서 우리는 배열 각 로마 숫자에 해당하는 정수 값을 저장하는 것. 다른 배열은 로마 숫자를 저장합니다. 이 두 배열은 동일한 해당 인덱스에 정수와 로마 숫자를 저장합니다.

이제 남은 것은 단순히 탐욕스러운 방식으로 수행되는 변환을 사용하는 것입니다. 가장 큰 로마 숫자로 시작하고 숫자가 현재 로마 숫자에 해당하는 숫자보다 큰 경우. 답변에 로마 숫자 추가 주어진 정수에서 정수 값을 뺍니다. 주어진 정수가 현재 숫자보다 클 때까지 현재 숫자를 뺍니다. 현재 숫자가 현재 정수 값보다 작은 지점에 도달하면. 다음으로 작은 로마 숫자를 확인하기 만하면됩니다. 모든 로마 숫자가 끝나면 답을 반환합니다.

정수에서 로마식 Leetcode 솔루션에 대한 코드

Integer to Roman Leetcode 솔루션을위한 C ++ 코드

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

string intToRoman(int num) {
    vector<string> romans({"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    vector<int> value({1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000});
    int seqSize = romans.size();
    int idx = seqSize - 1;
    string ans = "";
    while(num>0){
        while(value[idx]<=num){
            ans += romans[idx];
            num -= value[idx];
        }
        idx--;
    }
    return ans;
}

int main(){
    cout<<intToRoman(4);
}
IV

Integer to Roman Leetcode 솔루션을위한 Java 코드

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

class Main {
    public static String intToRoman(int num) {
        String romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int seqSize = romans.length;
        int idx = seqSize - 1;
        String ans = "";
        while(num>0){
            while(value[idx]<=num){
                ans += romans[idx];
                num -= value[idx];
            }
            idx--;
        }
        return ans;
    }
    public static void main(String[] args){
    	System.out.println(intToRoman(4));
    }
}

 

IV

복잡성 분석

시간 복잡성

O (1), 결과를 찾기 위해 일정한 수의 단계를 사용하기 때문입니다.

공간 복잡성

O (1), 상수 개수의 변수 만 저장했기 때문에 우리가 사용한 배열도 일정한 크기를 갖습니다.

코멘트를 남겨

Translate »