29일 차입니다. 요즘은 카공하는 것에 재미가 들린 것 같아요. 카페에서 노트북 키보드를 치고 있으면 뭔가 기분이 좋아지는 것 같더라고요.
그래서 오늘은 누나랑 집 근처 카페에 왔어요. 곧 있을 대만여행 계획도 세울 겸 문제 풀고 블로그도 쓰려고요.
벌써 코테 스터디 마지막 주더라고요. 마지막까지 힘내서 열심히 해보겠습니다.
문제 설명
영어 문제라서 역시나 당황을 먼저 했죠. 영어에 제가 좀 약하거덩요. 그래도 침착하게 해석을 해보았습니다.
그런데 문제 설명은 굉장히 짧은데 단번에 이해가 안돼서 더욱 당황을 해버렸어요. 하하;;
아래 예시를 보니 드디어 이해가 되더라고요. 주어지는 숫자 num안에 있는 수를 짝수인지 홀수인지를 구별해 swap 해주어 가장 큰 수를 출력해 주는 문제였습니다.
근데 문제에선 수학적으로 큰 수가 아니라 swap을 해서 만들 수 있는 수중 가장 큰 수를 의미한다고 다시 말해주더라고요.
https://leetcode.com/problems/largest-number-after-digit-swaps-by-parity/description/
생각 흐름
우선, 문제를 보자마자 쉽지 않은 문제겠다는 생각을 하였습니다.
정수형으로 받아오는 num을 문자열로 바꾸어서 풀어야 하는 문제인 것은 같은데 짝수와 홀수까지 판별하고,, 이를 swap까지 해서 출력한다? 그리고 최댓값이다? 각종 생각이 다 들면서 멘붕이 오더라고요.
지금까지 풀어봤던 문제 중에서 가장 어렵게 느껴졌달까,,
그래도 우선 코드를 작성해 보기로 했어요.
int형 변수 num을 우선 string으로 바꾸기 위해 to_string() 함수를 이용해 snum이라는 새로운 string 변수를 선언해 주었습니다.
그리고 우선은 sort() 함수로 정렬을 해줘야겠다는 생각을 했어서 vector <int> even, odd를 선언해 주고 이에 수를 넣어서 sort() 해준다는 생각으로 먼저 접근을 했었습니다.
근데 코드를 작성하면서 직관적이긴 하지만 너무 돌아가고 있는 방법으로 코드를 작성하고 있다는 생각을 하였어요.
뭔가 잘못됐다는 것을 느낀 것이었죠. 너무 많은 조건이 들어가기엔 부족하다고 느껴서 다시 작성하기 시작했습니다.
class Solution {
public:
int largestInteger(int num) {
string snum = to_string(num); // 문자열로 취급해서 풀면 쉬우니 string으로 변환
vector <int> even; // 짝수 저장할 vector even 선언
vector <int> odd; // 홀수 저장할 vector odd 선언
for (int i = 0; i < snum.size(); i++) {
int n = stoi(snum[i]); // 홀짝을 구분해주기 위해 다시 정수로 변환
if (n / 2 == 1) { // 홀수라면
odd.push_back(n);
}
else { // 짝수라면
even.push_back(n);
}
}
// 각 vector를 내림차순으로 정렬해줌 (즉, 큰수가 가장 앞 요소에 저장)
sort(even.begin(), even.end());
sort(odd.begin(), odd.end());
}
};
이번엔 홀수와 짝수를 비교할 사용자 정의 함수를 먼저 정의해 주고 우선순위 큐를 이용해 보자라는 생각을 하였습니다.
(은근 문제를 풀면서 우선순위 큐를 사용을 많이 하더라고요.)
좋은 자료구조 같아서 이번에도 무작정 사용해보려고 했어요. swap을 해주니까 각 요소의 인덱스까지 알아놓아야 하는 것 아닌가?라는 생각으로 <string, int>를 동시에 받는 우선순위 큐를 선언했었죠.
swap 함수도 사용해 보고 이런저런 고민을 해보았는데 뭔가 코드를 작성하다가 생각이 붕뜬다고 해야 할까요 뭔가 이상하더라고요. 자료형을 너무 바꾸는뿐더러 코드 길이는 긴데 뭔가 실속이 없는 코드라고 생각해서 다시 한번 깊게 생각해 보기로 했어요.
class Solution {
public:
bool compare (int n) {
if (n % 2 == 1) { // 홀수 일때
return false; // false 반환
} // 짝수 일때
return true; // true 반환
}
int largestInteger(int num) {
string snum = to_string(num); // 문자열로 취급하여 다루기 위해 문자열 변수 snum 선언
priority_queue <string, int> even; // 짝수와 인덱스를 저장할 우선순위 큐 even 선언
priority_queue <string, int> odd; // 홀수와 인덱스를 저장할 우선순위 큐 odd 선언
for (int i = 0; i < snum.size(); i++) {
int n = stoi(snum[i]); // 홀짝을 구분해주기 위해 정수형으로 변환
if (compare(n)) {// 짝수라면
even.push({to_string(n),i}); // 해당 수를 문자열로 변환한 것과 인덱스를 even에 넣어줌
}
else { // 홀수라면
odd.push({to_string(n), i}); // 해당 수를 문자열로 변환한 것과 인덱스를 odd에 넣어줌
}
}
for (int i = 0; i < even.size(); i++) {
int evenindex1 = even[i].second;
int evenindex2 = even[i+1].second;
swap(snum[evenindex1], snum[evenindex2]);
}
for (int i = 0; i < odd.size(); i++) {
int oddindex1 = odd[i].second;
int oddindex2 = odd[i+1].second;
swap(snum[oddindex1], snum[oddindex2]);
}
return stoi(snum);
}
};
그냥 단순하게 인덱스를 생각하지 않고 int만 받는 우선순위 큐를 받아오기로 결정했습니다.
인덱스를 통해 바꿔주는 것이 아니라 그냥 참조를 통해서 원래변수를 바로바로 바꿔주면 된다는 생각을 했던 것이었죠.
여기서 다른 사람분의 코드를 잠깐 참고를 했는데요. string 내에 있는 요소를 char 형으로 받아온 후에 -'0'을 붙여주면 바로 정수형으로 취급가능하다는 아이디어를 가져왔습니다.
이게 킥이거덩요. (역시 세상사람들은 똑똑하다,,)
아스키코드표에 의해 char 형 변수에 '0'을 빼주면 int형 변수처럼 계산이 가능하고 이를 반대로 하면 char 형으로 바꿀 수 있는 것이었어요.
그래서 이 개념을 적극활용을 하였습니다. 이를 통해서 홀짝을 판별해 우선순위 큐 even, odd에 각각 넣어주었습니다.
그런 다음 참조변수를 붙여 다시 반복문을 돌리는데 이를 각 우선순위큐의 top()에 + '0'을 해준 문자열과 바꾸어 snum을 새로 저장을 해주었습니다.
마지막으로 이를 문자열로 다시 바꾸어주어 출력해 주었습니다.
class Solution {
public:
int largestInteger(int num) {
string snum = to_string(num); // 문자열로 취급해서 풀어주기 위해 문자열 변수 snum 선언
priority_queue <int> even, odd; // 짝수와 홀수를 저장할 우선순위 큐 even, odd 각각 선언
// 내림차순으로 정렬
for (char digit : snum) { // snum의 요소를 char형태의 digit으로 받아와서
// char형 숫자 변수 - '0' = 정수형 변수을 의미함
if ((digit - '0') % 2 == 0) { // 짝수라면
even.push(digit - '0'); // 짝수 우선순위 큐에 정수형 형태로 저장
}
else { // 홀수라면
odd.push(digit - '0'); // 홀수 우선순위 큐에 정수형 형태로 저장
}
}
for (char &digit : snum) { // snum에서 참조 char형 변수 digit을 가져와서
if ((digit - '0') % 2 == 0) { // 짝수라면
// 정수형 변수 + '0' = char 변수를 의미함
digit = even.top() + '0'; // 짝수에서 가장 큰 수를 char 형으로 바꿔서 저장
even.pop(); // 그리고 even.top을 pop해줌
}
else { // 홀수라면
digit = odd.top() + '0'; // 홀수에서 가장 큰 수를 char 형으로 바꿔서 저장
odd.pop(); // 그리고 odd.top을 pop해줌
}
}
// & 참조자를 이용해줬기 때문에 digit을 이용해 snum이 변한거임
return stoi(snum);
}
};
공부한 내용 정리
이 문제의 킥이였던 아스키 코드표를 활용한 char -> int 변환을 잠깐 다루어보려고 해요.
📌 atoi()와 c_str() : string -> int
👉atoi() : char형 문자열 -> int 으로 변환한다!
#include<string>
char ch[20]="123456789";
atoi(ch) //char형 문자열의 경우 c_str()이 필요없다.🛑 atoi() 함수는 본래 char형 문자열 -> int 로 바꿔주는 함수이다. 따라서 string을 바꿀 경우 .c_str() 함수가 같이 필요한 것이다.
👉atoi(str 타입 변수.c_str()) : string -> int 으로 변환한다!
#include<string>
string str="123";
int num=atoi(str.c_str());
cout<<num<<"\n";123이 int 자료형으로 출력된다!
- atoi() 함수는 헤더 #include<stdlib.h> 를 사용해야한다.
int atoi(const char* str)
: C style의 문자열을 입력받아서 int 타입으로 변환해 리턴
- 헤더파일(C) : <stdlib.h>
- 헤더파일(C++) : <string>
std::string c_str()
: 반환형이 char* 이므로, 해당하는 string의 첫번째 문자의 주소값(포인터)를 반환
- 반환형이 char* 니까, atoi(str)만 하면 안돼! 그래서 atoi(str.c_str()) 로 해줘야해
3) char <-> int 간 형변환
📌 char - '0' : char -> int
문자를 정수로 변환하려면, 0의 아스키코드 값을 빼주면 된다.
int num = str[0] - '0'; //str[0]의 문자 '0'을 정수 0으로 변환
int num = str[1] - '0'; //str[1]의 문자 '3'을 정수 3으로 변환+) 뭣도 모르고 그냥 형변환하면 int num=(int)str[0] 0의 아스키 코드값 = 48이 출력됩니다~ 경험담
📌 int + '0' : int -> char
반대로 int 형 값에 0의 아스키코드 값(48)을 더해주면 char 형이 된다.
char ch = 0 + '0' //정수 0이 문자 '0'으로 변환
char ch = 3 + '0' //정수 3이 문자 '3'으로 변환
[C++] int <-> string(char) 간의 형변환 (+자료형 확인 함수)
string<->int | char<->int 간의 형변환 / typeid().name() 을 이용한 자료형 확인
velog.io
'코테 > 항해99' 카테고리의 다른 글
| [99클럽 코테 스터디 31일차 TIL] #정렬6 (0) | 2024.11.28 |
|---|---|
| [99클럽 코테 스터디 30일차 TIL] #정렬5 (1) | 2024.11.26 |
| [99클럽 코테 스터디 28일차 TIL] #정렬3 (0) | 2024.11.25 |
| [99클럽 코테 스터디 27일차 TIL] #정렬2 (2) | 2024.11.23 |
| [99클럽 코테 스터디 26일차 TIL] #정렬1 (1) | 2024.11.23 |