문제
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
- I can be placed before V (5) and X (10) to make 4 and 9.
- X can be placed before L (50) and C (100) to make 40 and 90.
- C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.
Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
- 1 <= s.length <= 15
- s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- It is guaranteed that s is a valid roman numeral in the range [1, 3999].
분석
- 큰 수부터 작은 수로 문자를 나열하여 구성된 로마숫자를 아라비아 숫자로 표현하기.
- 유의할 건 빼기 개념을 통해 완성되는 문자열이 있다는 것.
- 4 또는 9의 10배수가 오는 경우 그를 표현하기 위해 '상위 개념 - 하위개념' 식으로 구현함.
- 빼기인 것은 어떻게 분별하나?
경우의 수가 정해져 있기 때문에 그렇게 판별해도 되지만, 로마숫자는 큰수개념->작은수개념으로 이어지는 문자열이기 때문에, 만약 문자열 중 작은수 문자 뒤에 오는 큰 수 문자가 있다면 그건 빼기의 개념이다.
즉, M 은 1000의 개념이고 C는 100의 개념인데 CM 은 작은수 문자(100) 뒤에 큰수 문자(1000)이 왔으므로 빼기의 개념이 되고, 즉 큰수-작은수 가 되어 1000-100 = 900이 된다. - (1) 문자열의 0번 char 부터 체크하며, 체크 대상인 문자와 그에 대응하는 숫자를 미리 저장해둔다.
(2) 다음 문자를 확인하여, 미리 저장해둔 이전 문자보다 큰수의 개념이라면 빼기 계산을 하고 더한다. 그게 아니라면 이전 문자에 대응하는 숫자를 구하는 값에 더한다.
(3) for를 모두 수행하고 나면 남은 마지막 숫자도 구하는 값에 더한다. - 흠... 다른 식을 생각해보자.
- 일단 0번 문자부터 2개씩 가져와서 비교한다(a, b라고 칭하자). 비교하여 두 문자가 큰-작은 순서로 이루어져있다면 두개 문자에 대응하는 각 숫자를 리턴값에 더한다. 그리고 b와 그 뒤 문자를 가져와서 다시 비교한다.
만약 비교했는데 두 문자가 작은-큰 순서로 이루어져있다면 (큰-작은)의 값을 리턴값에 더하고, 대상문자 2개의 뒷순번부터 다시 비교한다.
피드백
- 나름대로 효율적으로 푼다고 풀었는데, 결과를 보니 평균적으로 중간 정도의 효율성이었다. 정진...
- 다른 사람의 풀이를 엿보고 오니, 신기한 아이디어도 있지만 내 코드에서 더 간단하게도 할 수 있었는데 역시 다소 부족했다. 정진...2...
답안
class Solution {
public int romanToInt(String s) {
int answer = 0;
s += "0"; // 2개씩 비교를 용이하게 하기 위한 전처리
int len = s.length();
boolean flg = true; // 앞의 숫자쌍이 큰-작은 순서로 이루어진 쌍이었는지 플래그
int[] pairNums = new int[2]; // 숫자쌍의 변수
for(int i = 0; i < len-1; i++) {
// 해당 문자에 대응하는 아라비아숫자를 구함
pairNums[0] = getArabNum(s.charAt(i));
pairNums[1] = getArabNum(s.charAt(i+1));
// 큰-작은 숫자쌍이고 && 앞의 숫자쌍이 큰-작은 숫자쌍인 경우
if(pairNums[0] >= pairNums[1] && flg) {
answer += pairNums[0];
flg = true; // 숫자쌍 플래그를 T로 재할당
// 작은-큰 숫자쌍이고 && 앞의 숫자쌍이 큰-작은 숫자쌍인 경우
}else if(flg){
answer += pairNums[1] - pairNums[0];
flg = false; // 숫자쌍 플래그를 F로 재할당
// 그 외의 경우 : 앞의 숫자쌍이 작은-큰 숫자쌍인 경우 이미 0번의 값이 계산되었으므로 플래그만 변경
}else {
flg = true; // 숫자쌍 플래그를 T로 재할당
}
}
return answer;
}
// 로마 숫자에 해당하는 문자가 들어오면 그 값에 따라 대응하는 아라비아 숫자를 return
public static int getArabNum(char c) {
int arabNum = 0;
switch(c){
case 'I' :
arabNum = 1;
break;
case 'V' :
arabNum = 5;
break;
case 'X' :
arabNum = 10;
break;
case 'L' :
arabNum = 50;
break;
case 'C' :
arabNum = 100;
break;
case 'D' :
arabNum = 500;
break;
case 'M' :
arabNum = 1000;
break;
}
return arabNum;
}
}
다른 사람의 답안
/*
로마자와 그에 대응하는 아라비아 숫자를 배열을 이용함.
로마자를 아스키코드를 이용해 인덱스화 하였음.
주어진 로마자를 맨 끝 순번부터 검증함으로써 로직 단순화
*/
class Solution {
public int romanToInt(String s) {
// 각 로마 숫자에 해당하는 문자를 아스키코드를 이용해 배열의 인덱스화 하고,
// 그 인덱스에 해당하는 배열의 인덱스 값은 로마자에 해당하는 아라비아 숫자로 할당함.
// 크기를 24로 할당한 것은 알파벳의 개수.
int[] hash= new int[24];
hash['I' -'A']=1;
hash['V'-'A']=5;
hash['X'-'A']=10;
hash['L'-'A']=50;
hash['C'-'A']=100;
hash['D'-'A']=500;
hash['M'-'A']=1000;
int ans=0;
// 역순으로 오른쪽부터 검사한다.
for(int i=s.length()-1;i>=0; i--){
char ch=s.charAt(i);
// 해당 문자가 의미하는 아라비아숫자를 구하여 리턴값에 더한다.
int a= hash[ch-'A'];
ans += a;
// 만약 현재 문자가 0번 문자가 아니고,
// 앞(왼쪽) 순번의 문자보다 크다면 앞 순번의 값을 빼고 한 순번을 건너뛴다.
if(i>0 && a>hash[s.charAt(i-1)-'A']){
ans-=hash[s.charAt(i-1)-'A'];
i--;
}
}
return ans;
}
}
/*
더 나아가면 이 정도로 단순하게도 도출할 수 있는 값이었군...
난 왜 더할 생각만 했을까.
*/
class Solution {
public int romanToInt(String s) {
// 문자열의 내용이 없는 경우에 대한 처리
if(s==null||s.length()==0)return 0;
// 문자열을 숫자배열화
int[] nums=new int[s.length()];
for(int i=0;i<s.length();i++){
switch(s.charAt(i)){
case 'M':
nums[i]=1000;
break;
case 'D':
nums[i]=500;
break;
case 'C':
nums[i]=100;
break;
case 'L':
nums[i]=50;
break;
case 'X':
nums[i]=10;
break;
case 'V':
nums[i]=5;
break;
case 'I':
nums[i]=1;
break;
}
}
// 숫자배열을 순회(마지막 요소 제외)
int sum=0;
for(int i=0;i<nums.length-1;i++){
// 뒷 순번의 배열값이 더 크다면 현재 값은 마이너스
if(nums[i]<nums[i+1]){
sum-=nums[i];
}
else{
sum+=nums[i];
}
}
// 따로 빼놨던 마지막 요소를 더한다.
sum+=nums[nums.length-1];
return sum;
}
}
🔗링크
'코딩테스트 > 리트코드LeetCode' 카테고리의 다른 글
| [리트코드LeetCode][Easy][JAVA]21. Merge Two Sorted Lists (5) | 2024.09.16 |
|---|---|
| [리트코드LeetCode][Easy][JAVA]20. Valid Parentheses (0) | 2024.09.15 |
| [리트코드LeetCode][Easy][JAVA][JavaScript]14. Longest Common Prefix (1) | 2024.09.14 |
| [리트코드LeetCode][Easy][JAVA]9. Palindrome Number (2) | 2024.09.10 |
| [리트코드LeetCode][Easy][JAVA][JavaScript]1. Two Sum (5) | 2024.09.07 |
