개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
첫번째 예제를 보면 입력값이 3,2,2,3 과 3인 경우 3을 제외하면 2,2 가 남으니 정답은 2 가 됩니다.
두번째 예제는 입력값이 0,1,2,2,3,0,4,2 와 2 이니 2를 제외하면 0,1,3,0,4 가 남으니 정답은 5가 됩니다.
이번 문제는 비교적 쉬운것 같습니다.
class Solution { public int removeElement(int[] nums, int val) { int i = 0; // 결과 값을 저장할 변수 for(int j=0; j < nums.length; j++) { // 입력된 배열의 아이템 숫자 만큼 for 문을 돌린다. if(nums[j] != val) { // 배열 내 해당 숫자가 입력된 val과 같지 않으면 아래 문을 실행한다. nums[i] = nums[j]; // nums의 i 번째에 nums의 j번째를 넣는다. i++; // i를 1씩 증가한다. } } return i; } }
어떻게 돌아가나 알아보기 위해 for 문과 if 문 사이에 프린트 문을 넣어 봤습니다.
입력값은 3,2,2,3 과 3 입니다.
첫번째 루프에서는 배열의 첫번째 값인 3과 입력값인 3이 같기 때문에 if 문이 실행 되지 않습니다.
그렇기 때문에 j와 i는 모두 초기값인 0이 됩니다.
두번째 루프에서는 j 가 1이 되고 두번쨰 값인 2와 입력값인 3이 같지 않기 때문에 if 문이 실행이 되어서 i에 1이 더해 집니다.
세번째도 값이 2이니까 if 문에 실행 되어서 i에 1이 더해 집니다. 그래서 i 값은 2가 됩니다.
네번쨰는 값이 3이라서 if 문이 실행 되지 않습니다. If 문이 실행 되지 않아서 i는 여전히 2 입니다.
For 루프문이 다 돌았기 때문에 i 값인 2가 반환 됩니다.
조금 다르게 접근 할 수도 있습니다.
class Solution { public int removeElement(int[] nums, int val) { int i = 0; int n = nums.length;
while(i < n){ // 배열의 아이템 개수만큼 루프를 돌립니다. if(nums[i] == val) { // 해당 값이 Val 과 같으면 nums[i] = nums[n-1]; // 해당 값은 그 이전 값 배열의 n 번째 숫자 (첫번쨰 루프 라면 맨 마지막 숫자인 3이 됨) n--; // n에서 1을 제외 한다. } else { i++; // 같지 않으면 i를 1 증가 시킨다. } System.out.println("i is " + i + " n is " + n); } return n; } }
오늘의 문제는 정렬된 int 배열에서 겹친 숫자를 제외한 숫자는 몇개 인지 알아내는 문제 입니다.
문제에서 조건은 새로운 배열을 만들어서 풀지 말고 입력된 배열을 그냥 수정해서 답을 구하라는 겁니다.
예제를 보면 첫번째 배열 1,1,2 의 경우 2를 리턴 해야 합니다. 왜냐하면 중복된 숫자를 제외한 값은 1과 2 두 개 이기 때문입니다.
두번째 예제는 중복 된 값을 제외하면 남는 숫자들은 0,1,2,3,4 입니다. 정답은 5가 됩니다.
그럼 이제 패턴을 생각해 보겠습니다. (두번째 예제의 입력값을 보겠습니다.)
입력값은 일단 오름차순으로 정렬 돼 있습니다.
그러니까 첫번째 숫자는 제일 작은 숫자입니다. (0)
두번째 숫자를 첫번째 숫자와 비교해서 같은 숫자 이면 0은 중복된 숫자 입니다.
그러면 세번째 숫자를 비교 합니다. 세번째 숫자 1 과 두번째 숫자 0은 같지 않기 때문에 1을 두번째 자리에 놓습니다.
그러면 이제 0,1,1,1,1,2,2,3,3,4 가 됩니다. 처음 입력값은 0,0,1,1,1,2,2,3,3,4 이었습니다.
네번째 숫자 1은 세번째 숫자와 같습니다. 넘어 갑니다. 다섯번째 숫자도 1입니다. 넘어갑니다.
여섯번째 숫자는 2 입니다. 그 전 숫자와 다릅니다. 그러면 이 2를 세번째 자리에 넣습니다.
이제 배열은 0,1,2,1,1,2,2,3,3,4 가 됐습니다.
일곱번째 숫자는 2 입니다. 이전 숫자와 같으니 넘어가고 여덟번째 숫자는 3입니다.
그럼 이 3을 네번째 자리에 넣습니다.
0,1,2,3,1,2,2,3,3,4 이제 배열은 이렇게 됐습니다.
다음은 아홉번째 숫자 차례 3이니까 넘어가고 마지막 열번째 숫자는 4. 그 이전 3과는 다르죠.
이 4를 다섯번째 자리에 넣습니다.
이제 배열의 모든 값을 살펴 봤습니다.
배열은 이렇게 됐습니다.
0,1,2,3,4, 2,2,3,3,4
중복된 숫자를 제외하면 0,1,2,3,4 가 남으니 정답은 5개 입니다.
이걸 코딩 하려면 두가지 값을 다루어야 합니다.
우선 입력된 배열 속의 숫자들을 모두 살펴봐야 하니까 그 배열의 아이템 개수를 다루어야 합니다. Array.length
다음은 새로 나온 숫자를 제자리에 넣을 때 사용할 숫자를 다루어야 합니다. InsertIndex 로 변수 이름을 정하겠습니다.
코딩과 결과 값은 아래와 같습니다.
입력값이 1,1,2 인 경우 1,2 가 중복된 숫자를 제외한 결과 이기 때문에 2를 리턴합니다.
입력값이 0,0,1,1,1,2,2,3,3,4 인 경우 중복된 숫자를 제외한 결과가 0,1,2,3,4 이기 때문에 5가 리턴 됩니다.
소스는 아래와 같습니다.
class Solution { public int removeDuplicates(int[] nums) { int n = nums.length; // 배열의 아이템 개수. For 문에서 사용 됨. if(n == 0) { return 0; // 입력된 배열이 empty이면 0을 반환한다. }
int insertIndex = 1; // 새로운 숫자를 찾았을 때 삽입할 위치. 배열의 첫번째 숫자 다음에 입력하면서 시작하기 위해 값은 1이 된다.
for (int i=1; i < n; i++) { // 입력된 배열의 모든 아이템 숫자를 비교하기 위해 length만큼 for문을 돌린다. if(nums[i] != nums[i-1]) { // 해당 숫자가 그 이전 숫자와 같지 않으면 if 문 내의 코드를 실행한다. nums[insertIndex] = nums[i]; // insertIndex 위치에 해당 숫자를 insert 한다. insertIndex++; // insertIndex의 값을 1 증가 시킨다. } } return insertIndex; // insertIndex 값을 리턴한다. } }
이번 문제의 핵심은 새로운 배열을 생성하지 말라는 것과 중복된 숫자를 제외한 숫자들의 개수를 알아내라는 겁니다.
그리고 stdout 을 보면 아래와 같다.0 c is ( 1 c is ( 2 c is ) 2 open is ( *** 2 open is (, c is ) 3 c is ) 3 open is ( *** 3 open is (, c is ) 4 c is { 5 c is } 5 open is { *** 5 open is {, c is } 6 c is [ 7 c is { 8 c is ( 9 c is ) 9 open is ( *** 9 open is (, c is ) 10 c is ) 10 open is { *** 10 open is {, c is )
처음 두 열린 괄호는 stack에 넣는다. 처음으로 닫힌 괄호 )가 나왔다.바로 직전 열린 괄호를 보니 ( 여서 짝이 맞는다. 그러면 통과하고 해당 (는 stack에서 제외한다.그 다음도 닫힌 괄호 ) 있고 직전 열린 괄호는 ( 이니 통과하고 해당 (는 stack에서 제외 한다.(()) 부분은 검증이 다 끝났고 현재 Stack에는 아무 것도 없다. 그 다음 { 는 스택에 넣고 그 다음을 보니 } 이므로 짝이 맞으니까 통과하고 {는 스택에서 제외.{}도 검증 됐고 Stack에는 아무것도 없는 상태
입력값 중에서 [{())] 를 검증해야 한다.[ 는 열린 괄호이니 스택으로, 그리고 { 도 스택으로 그리고 ( 도...이제 스택에는 [{( 가 있다.다음은 닫힌 괄호 ) 이다. 보니까 가장 가까운 열린 괄호는 ( 이니까 짝이 맞다. 그러면 통과 하고 (는 스택에서 제외.이제 스택에는 [{ 가 있다.다음을 보니까 닫힌 괄호 ) 이다. 스택에는 { 이 있다.짝이 맞지 않으니까 여기서 이 입력값은 invalid 판정이 나게 된다.그래서 결과는 false.
전체 코드를 보면 아래와 같다.
class Solution {
private static final Map<Character, Character> map
= Map.of('(', ')',
'{','}',
'[',']');
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
if(map.containsKey(c)) {
stack.push(c);
} else {
if(stack.isEmpty()) {
return false;
}
char open = stack.pop();
if(map.get(open) != c) {
return false;
}
}
}
return stack.isEmpty();
}
}
우선 (),[],{} 쌍을 Map에 넣는다.
그리고 isValid 안에서 Stack을 만든다.
입력된 스트링의 아이템 갯수 만큼 for 문을 돌린다.
해당 아이템이 Map의 key 이면, 즉 열린 괄호이던 stack 에 push 한다.
Key 가 아니면 stack에 있는 key와 짝이 맞는지 비교한다. Stack이 비어 있거나 짝이 맞지 않으면 false를 반환한다.
For 문을 다 돌고 나서 stack에 아무 값도 없으면 모든 짝이 다 맞는 것이니까 입력값은 Valid하고 true를 리턴한다.
class Solution: def romanToInt(self, s: str) -> int: total = 0 i = 0 while i < len(s): # If this is the subtractive case. if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]: total += values[s[i + 1]] - values[s[i]] i += 2 # Else this is NOT the subtractive case. else: total += values[s[i]] i += 1 return total
조금 다르게 접근할 수도 있다.
아예 로마숫자와 아라비아 숫자 매칭을 아래와 같이 할 수 있다.
class Solution {
static Map<String, Integer> values = new HashMap<>();
int sum = 0; int i = 0; while (i < s.length()) { if (i < s.length() - 1) { String doubleSymbol = s.substring(i, i + 2); // 아예 처음부터 입력값의 글자 두 개를 불러 온다. // Check if this is the length-2 symbol case. if (values.containsKey(doubleSymbol)) { // 그 키 값이 위 매핑에 있다면 sum += values.get(doubleSymbol); // 해당 값을 가져오고 i += 2; // 문자 두 개를 처리 했으니 i에 2를 더한다. continue; } } // Otherwise, it must be the length-1 symbol case. 두 글자가 매핑에 없다면 String singleSymbol = s.substring(i, i + 1); // 한 글자만 불러와서 sum += values.get(singleSymbol); // sum 에 더해 준다. i += 1; // 한 글자만 처리했으니 i 에 1을 더해 준다. } return sum; // 결과 값을 리턴한다. } }
class Solution: def romanToInt(self, s: str) -> int: total = 0 i = 0 while i < len(s): # This is the subtractive case. if i < len(s) - 1 and s[i:i+2] in values: total += values[s[i:i+2]] i += 2 else: total += values[s[i]] i += 1 return total
위 두 개는 입력값 을 왼쪽에서 오른쪽으로 보면서 계산한 것이다.
입력값을 오른쪽에서 부터 계산하는 방법도 생각해 볼 수 있다.
class Solution {
static Map<String, Integer> values = new HashMap<>();
String lastSymbol = s.substring(s.length() - 1); // 맨 마지막 - 오른쪽 - 글자를 가져온다. int lastValue = values.get(lastSymbol); // 오른쪽 로마자에 해당하는 아라비아 숫자를 가져온다. int total = lastValue; // 리턴할 int 변수를 생성했다. 값은 lastValue를 넣었다.
for (int i = s.length() - 2; i >= 0; i--) { // 입력값 -1 만큼 for 문을 돌린다. i 는 맨 마지막 글자 이전 부터 시작할 수 있도록 한다. String currentSymbol = s.substring(i, i + 1); // 현재값을 구한다. (첫번째 루프실행의 경우 맨 오른쪽에서 두번째 글자) int currentValue = values.get(currentSymbol); // 현재 값에 해당하는 아라비아 숫자를 구한다. if (currentValue < lastValue) { // 현재 값이 lastValue보다 작다면 total -= currentValue; // total = total - currentValue를 한다. 첫번쨰 루프에서 total은 lastValue가 된다. } else { // 현재 값이 lastValue보다 크거나 같다면 total += currentValue; // total = total + currentValue를 한다. } lastValue = currentValue; // lastValue에 currentValue를 입력한다. } return total; // for 문을 다 돌린 후 total 값을 리턴한다. } }
class Solution: def romanToInt(self, s: str) -> int: total = values.get(s[-1]) for i in reversed(range(len(s) - 1)): if values[s[i]] < values[s[i + 1]]: total -= values[s[i]] else: total += values[s[i]] return total
오늘의 문제는 9. Palindrome Number 입니다. 앞으로 해도 뒤로 해도 똑같은 우병우 가 아니라 앞으로 해도 뒤로 해도 똑같은 숫자를 구별하라는 문제 입니다.
제가 만든 스크립트는 아래와 같습니다.
class Solution { public boolean isPalindrome(int x) { boolean returnValue = true; // 일단 리턴 값을 담을 변수를 만들고 초기값은 true로 설정한다. String temp = Integer.toString(x); // 나중에 charAt을 사용할 예정이므로 int 입력값 을 스프링으로 변환한다.
int left = 0; // left는 0 int right = temp.length()-1; // right는 입력값 길이 -1
while(left < right) { // left 가 right 보다 작을 때까지 while 문 실행 if(temp.charAt(left++) != temp.charAt(right--)){ // 입력값의 왼쪽 값과 오른쪽 값이 다를 경우 if 문 실행 returnValue = false; // 다를 경우 리턴값은 false 가 된다. } }
return returnValue; // 리턴값을 리턴한다. } }
다른 사람이 만든 스크립트를 보자.
class Solution {
public boolean isPalindrome(int x) {
String s1 = Integer.toString(x);
//passing x in the below statement won't work(idk why)
StringBuilder s2 = new StringBuilder(s1).reverse();
return s2.toString().equals(s1);
//s2.toString() == s1 -> compares string references --> hence use .equals()
}
}
내꺼 보다 훨씬 간단하다. 이 사람은 StringBuilder의 reverse 함수를 사용했다. 원래 입력값과 reverse한 값이 같으면 true 다르면 false를 리턴한다.
Python 으로는 아래와 같이 할 수 있다.
class Solution:
def isPalindrome(self, x: int) -> bool:
s = str(x)
return s == s[::-1]
마지막 줄이 좀 이해가 안기는데......
list[<start>:<stop>:<step>]
start(optional)- Starting index value where the slicing of the object starts. Default to 0 if not provided.
stop– Index value until which the slicing takes place.
step (optional)– Index value steps between each index for slicing. Defaults to 1 if not provided.
String input을 reverse 하는데 letter 별로 하는게 아니라 단어별로 하라는 거다.
그래서 결과는 output과 같아야 한다는 것이다.
그 자리에서 나름대로 스크립팅를 해서 만들게 아래 코드다.
다행히도 원하는 결과물의 만들었다.
그래서 테크니컬 인터뷰는 통과 했다.
로직은 이전에 했던 String 의 letter들을 reverse 하는 것과 같다. 다면 단어를 reverse 해야 하는데 이건 letter 별이 아니라 단어별로 끊어서 배열에 넣으면 된다고 생각했다.
class HelloWorld { // 클래스 이름. 그냥 신경 안 쓰고 HelloWorld로 했다. public static void main(String[] args) { // 메인 함수 String input = "Reverse words in a sentence."; // 입력값 String output = "sentence. a in words Reverse"; // 원하는 출력 값
System.out.println(reverseWords(input)); // reverseWords라는 메소드에 입력값을 보내고 그 결과를 프린트 한다. }
public static String reverseWords(String input) { // reverseWords 메소드 입력값은 input 스트링 return은 스트링 타입이다. String returnValue; // return 할 스트링 변수를 만든다.
String[] tempInput = input.split(" "); // input 을 단어별로 나눠서 스트링 배열에 담는다. int left = 0; int right = tempInput.length -1;
while(left < right) { // left가 right 보다 작을 때까지 while문을 돌린다. String temp = tempInput[left]; // 스프링에 배열 맨 왼쪽 값을 넣는다. tempInput[left++] = tempInput[right]; // 맨 왼쪽에 맨 오른쪽 단어를 넣는다. tempInput[right--] = temp; // 오른쪽에 맨 왼쪽 값을 넣는다. }
returnValue = tempInput[0]; // returnValue에 배열의 맨 첫번째 값을 담는다.
for(int i=1; i < tempInput.length; i++) { // 배열의 갯수보다 1 작은 만큼 for 문을 돌린다. returnValue = returnValue + " " + tempInput[i]; // 각 배열의 값들을 하나의 스트링 으로 만든다. }
