Code Signal -Arcade
코드시그널
아케이드 문제 관련 풀이들을 구글링하면서 찾아가는 일지를 하나씩하나씩 기록하고자 합니당.
주로 자바 위주로 풀이를 올릴예정이고, 추가로 공부하고 있는 파이썬이나 코틀린, GO, 자바스크립트 더 나아가 스위프트까지...
되는대로 가능한대로 구글링하고 정답맞추면 바로 패스!!
이런식으로 좋은 코드이든 말든 짜집기한 결과물들을 개인적 소장을 위해 기록합니다. ^^
참고 사이트들은 아래에 링크로 남겨둘터이니 자세하고 더욱 깊은 내용들은 링크로 들어가보세요!
Common Character Count
흔한? 비슷한 문자 수 세기?
진짜 해석하기 힘들다.. 내가 머리가 않좋은거겠지만, 진짜 이건 뭔가 싶었다.
아무튼 그냥 문자열 겹치는것을 구분해서 갯수로 알려달라는 것이었다. 하... 영어 수듄...
문제는 이렇다. 두개의 문자열을 준다. 그리고 각 문자열의 문자 하나하나를 중복되면 그것까지 갯수를 세어서 두 문자열을 비교해준다. (이 말도 어렵네,, 내가 써놓고..)
뭔말인가 처음에는 답지를 보고도 뭔말인가 싶었다. 한국말로 해줘 제발..
자 다시 해석해보면, 예를들어 한글로 바꿔보면, 'ㄱㄴㄷㄱㄱ' 과 'ㄱㄴㄷㄱㄴ' 이렇게 아무런 의미 없는 자음들이 있다.
이 두개의 문자열이 입력이 되는 것이다.
'ㄱㄴㄷㄱㄱ'
'ㄱㄴㄷㄱㄴ'
그렇다. 뭔말인가 싶다. 왜 하느거지 싶은데, 아무튼 최대한 쉽게 설명하면 이렇게 된 문자열을 하나씩 보면,
| 문자 입력값 | 첫번째 글자 | 두번째 글자 | 세번째 글자 | 네번째 글자 | 다섯번째 글자 |
| s1 | ㄱ | ㄴ | ㄷ | ㄱ | ㄱ |
| s2 | ㄱ | ㄴ | ㄷ | ㄱ | ㄴ |
이렇게 된다.
위아래로 둘을 비교하라는 거라면 쉽다. 오히려 그런데 단순히 위아래를 비교하라는 것이 아니라, 각 입력갑의 중복되는 문자열의 갯수를 확인해주고
그리고 두번째 입력값도 똑같이 해주고
마지막으로 두 개의 입력값들의 갯수들과 문자열이 같은 것이 무엇이며, 그것들의 쌍의 갯수를 나타내 주고
그거를!! 그 쌍의 갯수를 또 구해주라는 것이다.................
어쩌지...
이래도 뭔말인지 모를 것같다. ... 다시 다시...
일단 이 문자표를 보자 좀 힌트를 얻을 수 있을 것이다.
문자표를 보면 한글이나 알파벳이나 마찬가지로 순서대로 숫자들이 매겨져 있다. 한글의 자음은 14자니깐 총 1~14번까지 되어있고 알파벳은 1~26자 까지 되어있다.
이것을 보고도 모르겠음.. 맨 아래 답지를 같이 보세요. 진짜
다시 돌아오면, 코드에서는 문자열들에는 항상 숫자가 붙어있다. 물론 그 숫자들은 컴퓨터가 더 인식하기 쉽게 0 과 1 로 해석되어 2진법으로 풀이되지만 아무튼 우리가 쓰는 문자들은 그렇게 숫자로 구분되고 그 숫자는 또 기계어로 변형되어 컴퓨터에 들어가게 되는 것이다.
이렇게 보면 좀 이해가 된다.
| 문자 입력값 | 첫번째 글자 | 두번째 글자 | 세번째 글자 | 네번째 글자 | 다섯번째 글자 |
| s1 | ㄱ = 1 | ㄴ = 2 | ㄷ = 3 | ㄱ = 1 | ㄱ = 1 |
| s2 | ㄱ = 1 | ㄴ = 2 | ㄷ = 3 | ㄱ = 1 | ㄴ = 2 |
이렇게 보면 s1 에서는 'ㄱ'이라는 글자는 총 세번 나온다. 그리고 'ㄴ'은 한번 , 'ㄷ'도 한번 나온다.
s2에서는 'ㄱ'은 2번 나오고, 'ㄴ'은 2번 , 'ㄷ'은 1번 나온다.
그렇다면 s1 과 s2 입력값 둘을 비교했을 때 똑같은 문자열의 쌍이 어떻게 나올까?
s1 = 'ㄱ' * 3 / 'ㄴ' *1 / 'ㄷ' *1
s2 = 'ㄱ' * 2 / 'ㄴ' *2 / 'ㄷ' *1
'ㄱ' 쌍은 2쌍이 나온다.
'ㄴ' 쌍은 1쌍이 나온다.
'ㄷ' 쌍은 1쌍이 나온다.
그렇다면 총 몇쌍인가???!!!
바로 2 + 1 + 1= 4 ... 4쌍이 나온다. 답은 4쌍이다.
자아.. 서론이 길었습니다. 이게 간단한 개념 설명이에요.. 극혐...
이게 정녕 EASY 라는 것인가... (눙물)
아무튼 이러한 개념으로 이 문제를 풀어야 하는데 천재적인 분들은 이 개념을 이미 간파헀다면 새로운 문제가 있죠 항상..
어떻게 코드를 쓰느냐 이겁니다.
저야 허접이니깐 바로 답지를 체크하고 했기 때문에 코드의 이해가 더 잘 되었지만, 진짜 구글링 좀 하면서 풀었습니다.
알고리즘 문제의 특이점은 답지를 봐도 풀이가 이해가 안된다는 것이죠 ㅋㅋㅋ
아무튼 ! 답을 확인해봅시다.
//알파벳 갯수가 26개 이미로 배열의 범위는 26으로 설정한다.
int a [] = new int [26];
int b [] = new int [26];
for( char c : s1.toCharArray()){
a[c - 'a']++;
}
for ( char c : s2.toCharArray()){
b[c - 'a']++;
}
int s = 0 ;
for( int i =0 ; i< 26; ++i){
// 둘 중 더 작은 값을 s 에 더해주면서 리턴한다.
s+= Math.min(a[i], b[i]);
}
return s;
아무튼 답안 입니다.
극혐입니다. 이 짧은 코드의 극혐도 저에게는 상급.
아니, 문제를 이해했는데도 코드를 보면서 어떤원리로 돌아가는지 직접 써가면서 해보았습니다.
그제서야 이해가 되더군요.. 수듄...
코드를 하나씩 보면 일단
| int a [] = new int [26]; int b [] = new int [26]; |
이런 놈이 보입니다. 이게 처음에 왜 이렇게 선언을 하지 싶었음..
그런데 아래를 천천히 보면서 한번 훑으니깐 그제서야 문자표를 찾아보았고 그제서야!!! 이부분도 이해가 됨..
답지에 주석 없는거 너무함. ㅜㅜ 암튼 이 배열의 선언을 숫자형으로 하면서 그 배열의 크기는 26개로 한 이유는
간단합니다.
알파벳이니깐 입니다. !!! (쓰벌탱 미개한 영어. 한글쓰자 왜케 많은고얌)
아무튼 그렇게 보면 이해가 될겁니다.
두개의 입력값이 주어지고 그리고 그 입력값들은 알파벳 형태이니 그것을 담아주는 그릇입니다.
하지만 여기서 궁금증.. 그렇다면 application 같은 영단어가 들어가면 아니면,
미친척하고 문장을 붙여가지고 26자를 넘어가게 입력하면??
상관없습니다.
왜냐하면 이 알파벳 배열 그릇들은 그러한 무식한 입력을 정리해서 넣어주는 역할을 할겁니다.
아래를 볼까요.
for( char c : s1.toCharArray())
|
이 반복문이 무엇을 하느냐 이게 관건 이었습니다.
처음에는 for 반복문 마져 익숙하지않은 저에겐 다시 차근차근 이해하기 위해 구글링도 했습니다.
까딱하면 꼬이는 거 같걸랑요.
for (char c : s1. toCharArray()) 의 의미는
먼저 s1의 입력값이 들어왔을때, 그 문자열을 toCharArrray() 메서드로 각 문자열을 잘라서 배열의 형태로 넣어주는 것입니다.
그리고 나면 그 각 배열의 값들이 char c 에 하나씩 순서대로 들어가게 됩니다.
이렇게 이해하면 됩니다.
'ABBC' 가 s1이라면, 이거를 toCharArray() 로 변환해줍니다. 그러면
s1 은 [A] , [B] , [B] , [C] 이렇게 정리가 됩니다. 각 배열로 한개의 값씩 짤라져서 만들어 지는 겁니다.
그리고 나서 char c 라는 문자 객체에 순서대로 for()문이 들어가게 하는 겁니다.
그래서 char c 는 s1의 각 문자열들을 하나씩 들고 for 문 안으로 들어갔다 나오고 다시 s1의 두번째 값을 들고 다시 들어가고 ... 이것을 반복한다는 것이죠.
그렇게 해서 For 문 안으로 들어가보니
a [ c - 'a' ] ++; 가 있습니다.
이건 또 뭔가 싶었지만,,, 이부분은 Char c 가 하나씩들고 들어올때, 검사해주는 부분이다.
aabcc 가 s1 이라는 문제의 예시를 넣어보면, 먼저 toCharArray()로 쫘악 걸러진 s1이 이쪽으로 들어가게된다. 그러면,,,
a[ 'a' - 'a' ] ++ ;
a[ 'a' - 'a' ] ++ ;
a[ 'b' - 'a' ] ++ ;
a[ 'c' - 'a' ] ++ ;
a[ 'c' - 'a' ] ++ ;
이렇게 쭈루룩 반복문이 돌고, 위와 같이 값들이 툭툭 떨어진다. 그리고 이 값들을 자세히 보면,
| 코드 | 풀이 | 결과값 |
| a[ 'a' - 'a' ] ++ ; | a[ 1 - 1 ] ++ -> a [ 0 ] ++ | a[ 0 ] = 1 |
| a[ 'a' - 'a' ] ++ ; | a[ 1 - 1 ] ++ -> a [ 0 ] ++ | a[ 0 ] = 2 |
| a[ 'b' - 'a' ] ++ ; | a[ 2 - 1 ] ++ -> a [ 1 ] ++ | a[ 1 ] = 1 |
| a[ 'c' - 'a' ] ++ ; | a[ 3 - 1 ] ++ -> a [ 2 ] ++ | a[ 2 ] = 1 |
| a[ 'c' - 'a' ] ++ ; | a[ 3 - 1 ] ++ -> a [ 2 ] ++ | a[ 2 ] = 2 |
이런식으로 진행이 되어 값들이 쭈욱 나오게 된다. 즉, 이 값들이 a [ ] 안에 들어가게 되는데,,
결과적으로는 a [ ] 들의 값들은 이렇게 된다.
| a [ ] = { 2, 1, 2 } |
이런식의로 되는 것이다!
같은 방법으로 b [ ] 도 for 문을 돌리면!!
s2 = 'adcaa' 이니깐
| b [ ] = { 3, 0, 1, 1 } |
이렇게 된다.
그렇다면 맨 처음 말처럼 이 둘을 비교해서 쌍이 총 몇개인지 알아봐야하는 것이다.
이 부분이 잘 이해가 안될수 있다. 답안의 코드도 다른 형식으로 풀이를 하고 있으니 말이다.
쌍이라 하면 2개가 있어야 성립되므로 양쪽에 둘다 만족하는 짝이 있어야 한다.
이 말은 즉 같은 배열 위치의 값들 중 최소값이 되는 것이 그 쌍을 뜻한다는 것이다.
그래서 답안 코드에서는
int s = 0 ;
|
이렇게 표현하고 있다.
For 반복문에 26개의 알파벳을 쭈욱 있다치고, 돌리겠다는 것이다. 그리고
s라는 총 쌍의 갯수를 나타내는 객체를 하나 선언하여 넣어주고 += 로 계속 쌓이게 만든다.
math () 메서드를 활용하여 그 안에 min 최소값을 구해주는 메서드를 활용하여
min( a , b ) 를 이용하는데, 이 의미는 a 와 b 둘 중 더 작은 값을 반환한다는 의미이다.
즉, 코드를 보면, a 배열 과 b배열 의 i 자리 값들을 비교하여 더 작은 값을 반환해주고 그것들을 쌓아서 쭈욱 다
더해 준다는 뜻이다.
그렇게 해서 마지막으로는
return s ;
를 하게 되면 정답이 된다.
....
그렇게 고비를 넘어 넘어 최대한 설명을 붙여서 다시 코드를 보여드리겠습니다.
기존 답안 코드랑 같으나, 주석이 붙어 있습니다. 그 이유는,
제가 기억하려고요.. 이래야 기억날듯.
int commonCharacterCount(String s1, String s2) {
// 알파벳의 갯수는 26개이므로 숫자형 배열의 크기를 26개로 지정해준다.
int [] a = new int [26];
// 입력값이 두개 이므로 하나더 만들어준다.
int [] b = new int [26];
// 이제 각 입력된 문자열들을 하나씩 쪼개서 숫자형으로 변환해주자.
for(char c : s1.toCharArray())
// s1의 각 글자들을 배열로 쪼개서 그 하나의 값들을 한번씩 char c 에 넣어준다.
// 그리고 그것을 다시 a[]에 하나씩 추가해주어 배열의 번호 넣어준다.
a[ c - 'a']++;
/* 예를 들어 s1 = 'aabcc' 라 하면, 각 문자의 갯수를 보면은 a는 두개 b는 한개 c는 두개 이다.
* 이것을 숫자로 풀면 aabcc 는 212 이 된다.
* 만약 aabcc 처럼 a가 두개면 2로 a[0]=2 로 2개가 쌓이고, b가 1개니깐, a[1]=1 이된다.
* 그리고 c는 두개니깐, a[2]=2 로 적립된다. 이러한 과정을 풀어주는 것이 위의 for문이다.
* 즉, 알파벳 문자배열 그릇에, 입력값의 문자열을 분석해서 숫자로 적립해두는 것이다.
* 알파벳 문자열은 a ~ z 까지 1~26 로 숫자로 계산이 된다. 그래서 'a'은 1 이므로,
* 배열자리의 번호를 고려해서 'a'가 들어가서 하나를 빼주어 제대로 된 위치에 갯수를 쌓아주는 것이다.
* 그리고 ++는 같은 알파벳의 경우 a를 빼주어도 a[]의 위치가 같으므로 그것을 고려해서 똑같으면 하나를 더
* 쌓아주는 개념으로 들어가 있는 것이다.
*/
/* 똑같은 의미의 불편한 for문을 써서 만든 코드이다. 참고.
// Update the frequencies of
// the characters of string s1
for (i = 0; i < n1; i++)
freq1[s1.charAt(i) - 'a']++;
*/
// 위와 같은 개념으로 두번째 입력값도 같은 반복문으로 문자열의 알파벳을 분석해준다.
for(char c : s2.toCharArray())
b[c -'a']++;
//이제는 두 입력값을 분석해주기 위해서 숫자형의 객체를 생성해서 선언해준다.
int total = 0;
//이 부분이 두 입력값의 중복과 쌍이 얼마나 있는지 보여주는 반복문이다.
// 일단 i를 0 부터 26까지 1씩 상승하게 만들어준다.
for (int i =0; i<26; i++)
// 숫자메서드에서 최소값을 구해주는 메서드를 활용하여 계산하는데,
// 각 입력값들은 각 알파벳 숫자를 나타내는 위치에 각 가지고 있는 갯수만큼 들어있다.
// 이러한 것을 a[i], b[i] 의 형태로 비교해주어 둘중 최소값을 반환하고
// 그 값을 더해가며 차곡차곡 계산해주는 것이다.
// aabcc, adcaa 라 하면
// aabacc 는
// a[0] = 2 , a[1]=1, a[2]=2, a[3]=0 이다.
// adcaa 는
// b[0] = 3 , b[1]=0, b[2]=1, b[3]=1 이다.
// 이렇게 두고 보면 각 배열의 위치의 값들의 최소값은
// 2 , 0 , 1 , 0 이된다. 이 값들을 다 더하면 3 이된다.
total += Math.min(a[i],b[i]);
// 그래서 최종 리턴값은 3이 되는 것이다.
return total;
}휴 이렇게 저렇게 끝이 났고,
언제나 그랬듯이 아래에 정답이 있으니 직접 확인해보셔도 좋을 거 같아요.
greenhelix/CodeFights-Arcade
Efficient Solutions to 100+ problems in CodeFights Arcade written in c++, python, java , c#, JavaScript - greenhelix/CodeFights-Arcade
github.com
추가로 ,
이 답안을 제공해주는 사이틀 찾았습니다. 이쪽도 확인해보세요!! (영어임 쓰바.. 유명한데인가.. 몰겠음.)
https://www.geeksforgeeks.org/count-common-characters-in-two-strings/
Count common characters in two strings - GeeksforGeeks
Given two strings s1 and s2 consisting of lowercase English alphabets, the task is to count all the pairs of indices (i, j) from the… Read More »
www.geeksforgeeks.org
코드 시그널 사이트에 정답을 맞추면 정답자들의 답안을 언어별로 확인할 수 있는데, 정말 유용한 것 같습니다.
다양한 코드의 해석을 볼 수 있어 좋지만,
앞으로 알고리즘 인트로,,, 파트완료하면 다시 한번 복습하여 계속 꾸준히 쌓으려고 합니당. ㅎㅎ
'Algorithm > Java' 카테고리의 다른 글
| #11_Code Signal Arcade >> Is Lucky (0) | 2019.10.21 |
|---|---|
| #09_Code Signal Arcade >> All Longest Strings (0) | 2019.10.05 |
| #08_Code Signal Arcade >> Matrix Elements Sum (0) | 2019.10.03 |