코딩 테스트 스터디 기록 _ 2

코딩테스트 스터디 2주차 기록입니다.

 

https://leetcode.com/problems/roman-to-integer/

Roman to Integer - LeetCode

로마 숫자를 정수로 변환하는 문제였습니다.

 

처음에 문제에 나온 조건인 4,9 / 40,90 / 400,900을 어떻게 처리해야 할 지 고민이 많았습니다.

처음 한 생각이, 다른 케이스는 다 큰 값을 갖는 로마 숫자가 먼저오는데 위의 케이스들만 반대로 작은 값을 갖는 것이

먼저 오고 큰 값이 뒤

에 오기 때문에 그렇게 앞 뒤의 숫자 크기를 비교해서 처리해주면 되겠다 생각했습니다. 그런데

그게 과연 모든 케이스를 처리해줄 수 있을지 의문을 갖고 있다가, 다양한 케이스를 생각해보니 모든 케이스를 다 처리해 줄 수 있겠다고 생각해서 코드를 제출 했고 다행히 정답 처리를 받았습니다 !

 

예를들어, 149를 로마숫자로 변환한다고 치면 100을 뜻하는 C가 가장먼저오고 40을 표현하기 위해 10을 뜻하는 X 뒤에 50을 뜻하는 L이 오고 9를 표현하기 위해 1을 뜻하는 I가 나온뒤 10을 뜻하는 X가 오면 결국 앞뒤로 비교 했을때, 앞의 문자가 뒤에 문자보다 더 작은 값을 가질 때, 그 부분만 처리해서 답을 도출하면 되는 것 입니다.

 

나머진 다 temp라는 변수에 문자가 뜻하는 크기만큼 값을 더해주고 위에 해당하는 앞의 문자의 값이 더 작은 경우에만 

temp에서 값을 빼주고 추가 하지 못한 newArr의 마지막 인덱스의 값만 더해서 값을 반환했습니다.

 

 

var romanToInt = function(s) {
    let roman = [
        ['I',1] , ['V',5] , ['X',10] , ['L',50] , ['C',100] , ['D',500] , ['M',1000]
    ]
    let newArr =[];
    let temp = 0;
 
    for (let i=0; i<s.length; i++)
    {
        for (let j=0; j<roman.length; j++)
        {
            if (s[i] == roman[j][0])
            {
                newArr.push(roman[j][1]);
            }
        }
    }
 
    for (let i=0; i<newArr.length-1; i++)
    {
        if (newArr[i] <newArr[i+1])
        {
            temp -= newArr[i];
        }
        else
        {
            temp += newArr[i];
        }
    }
 
    temp += newArr[newArr.length-1];
 
    return temp;
    
};

 

https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

두번 째 문제는 가장 많이 겹친 접두사를 찾아내는 문제였습니다.

 

입력으로 들어오는 첫 번째 단어를 기준으로 뒤에 오는 단어들과의 철자 비교를 진행합니다.

flag를 만들어놔서 같은 위치에 같은 단어가 안나오게 되면 어차피 답이 되지 않는 철자 이기 때문에

flag를 false로 바꾸고, 그렇지 않으면 답에 포함시켜야 하는 문자이기 때문에 정답을 모으는

answerArr배열에 담습니다.

 

조건에 맞는 철자들을 다 담은 배열을 빈 문자로 만든 chk변수에 + 연산을 통해 문자열을 합쳐서

정답으로 제출하고 채점 받았습니다.

 

var longestCommonPrefix = function(strs) {
    let flag = true;
    let answerArr = [];
    let chk = '';
 
    for (let i=0; i<strs[0].length; i++)
    {
        let str1 = strs[0][i];
        for (let j=0; j<strs.length; j++)
        {
            if (str1 !== strs[j][i])
            {
                flag = false;
            }
        }
        if (flag == true)
        {
            answerArr.push(str1);
        }
        
    }
    for (let i=0;i < answerArr.length;i++)
    {
        chk += answerArr[i];
    }
 
    return chk;
};

 

https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

세번 째 문제는 연결리스트로 두 개가 주어지고, 가장 마지막 노드부터 역순으로 숫자를 만들어서 두 숫자를 더해서

나온 값을 위의 입력 값의 연결리스트 처럼 역순으로 만들어서 맨 앞의 숫자가 가장 마지막 노드의 value값으로 들어올 수

있게 만들어 반환하는 문제였습니다.

 

노드 클래스와 이어주는 동작을 하는 함수를 구현해야겠다고 생각했는데, 아직 자바스크립트의 실력이 많이 부족해서 어떻게 구현 해야할 지 모르겠어서 홈페이지에 있는 다른분들의 풀이를 참고했습니다. 다른 분들의 Javascript 솔루션을 봐도 이해하기가 어려워 C++ 풀이를 보고 이해했습니다.

 

ListNode 구조체에 val 변수와 ListNode *next변수 그리고 인자 별로 3개의 생성자함수를 만들고, dummy라는 ListNode포인터 변수를 생성해서 동적 할당으로 ListNode하나를 생성합니다. 그리고 temp라는 ListNode 포인터 변수를 임시로 만들어 dummy 주소를 저장하여 생성할 ListNode를 가리킵니다.

조건문을 통해서 인자로 넘어오는 입력 노드들의 val값을 따로 저장하고 다음 노드로 이동하면서 두개의 입력 노드들의 val값을 더합니다. 꼼꼼하게 10이 넘는 경우를 대비해서 carry라는 변수도 만들어 줬습니다. 그래서 sum을 10으로 나누는 나머지를 val값으로 하여 ListNode를 생성해서 temp의 next를 이렇게 생성한 노드를 가리키게 하고  temp에 temp->next값을 넣어서 이렇게 새로 생성한 노드가 다음 노드를 받을 준비를 하게합니다. 그렇게 while문을 반복하면 자연스럽게 문제에서 원하는 순서로 val값들이 배치가 되고 return dummy -> next를 통해서 while문을 통해 새로 만든 Linked-List를 반환하는 풀이입니다. 이 분의 풀이를 보고 이해하는 것 만으로 많은 도움이 되었다고 생각합니다 !

 

(풀이 출처  : https://leetcode.com/problems/add-two-numbers/solutions/2759116/c-easy-to-understand/)