목차
[Lv.1]
▸ 삼총사
▸ 크기가 작은 부분문자열
▸ 최소직사각형
삼총사 : Lv.1
▼ 문제
한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.
한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.
▼ 제한사항
- 3 ≤ number의 길이 ≤ 13
- -1,000 ≤ number의 각 원소 ≤ 1,000
- 서로 다른 학생의 정수 번호가 같을 수 있습니다.
▼ 입출력 예
| number | result |
|---|---|
| [-2, 3, 0, 2, -5] | 2 |
| [-3, -2, -1, 0, 1, 2, 3] | 5 |
| [-1, 1, -1, 1] | 0 |
▼ 내 풀이
class Solution {
public int solution(int[] number) {
int answer = 0;
int sum = 0;
for(int i = 0; i < number.length; i++){
for(int j = i+1; j < number.length; j++){
for(int k = j+1; k < number.length; k++){
sum = number[i] + number[j] + number[k];
if(sum == 0){
answer ++;
}
}
}
}
return answer;
}
}- 3개의 숫자를 조합해야 하므로 for문을 사용하면 어떨지 고민함
- 첫번째 for문에서는 첫번째 숫자에 대해 반복하고 두번째 for문에서는 두번째 숫자에 대한 반복한다.
크기가 작은 부분문자열 : Lv.1
▼ 문제
숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.
예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.
▼ 제한사항
- 1 ≤ p의 길이 ≤ 18
- p의 길이 ≤ t의 길이 ≤ 10,000
- t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.
▼ 입출력 예
| t | p | result |
|---|---|---|
| "3141592" | "271" | 2 |
| "500220839878" | "7" | 8 |
| "10203" | "15" | 3 |
▼ 내 풀이
- 먼저 전달받은 문자열을 char타입의 배열로 바꾸고 부분 문자열을 구해야 한다.
- for문을 활용하여 부분 문자열을 구한다.
- 두번째 for문에서 j의 조건을 구하는데 시간이 걸렸다. p의 길이에서 1을 뺀 수 만큼 반복을 하기 때문에 j = i+1; j < i + legnth; j++ 와 같이 정했다.
[런타임 에러 코드]
class Solution {
public int solution(String t, String p) {
int answer = 0;
int length = p.length();
int num = Integer.parseInt(p);
char[] numbers = t.toCharArray();
for(int i = 0; i <= numbers.length - length; i++){
String part = String.valueOf(numbers[i]);
for(int j = i+1; j<i + length; j++){
part += String.valueOf(numbers[j]);
}
if(Integer.parseInt(part)<=num){
answer++;
}
}
return answer;
}
}- 위와 같이 코드를 작성하고 채점한 결과 많은 테스트에서 런타임 에러가 떴다.
- 런타임 에러의 원인은 바로 int로 형변환했기 때문이다. int타입은 10자리까지 밖에 담지 못하기 때문에 long으로 고쳤다.
- 코드를 고치기 위해 알아보던 중 substring 메소드를 발견하고 적용했다.
[수정코드]
class Solution {
public int solution(String t, String p) {
int answer = 0;
int tlength = t.length();
int plength = p.length();
long num = Long.parseLong(p);
for(int i = 0; i <= tlength - plength; i++){
String part = t.substring(i,i + plength);
if(Long.parseLong(part)<=num){
answer++;
}
}
return answer;
}
}최소직사각형 : Lv.1
▼ 문제
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.
아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.
| 명함 번호 | 가로 길이 | 세로 길이 | |
|---|---|---|---|
| 1 | 60 | 50 | |
| 2 | 30 | 70 | |
| 3 | 60 | 30 | |
| 4 | 80 | 40 |
가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.
모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
▼ 제한 사항
- sizes의 길이는 1 이상 10,000 이하입니다.
- sizes의 원소는 [w, h] 형식입니다.
- w는 명함의 가로 길이를 나타냅니다.
- h는 명함의 세로 길이를 나타냅니다.
- w와 h는 1 이상 1,000 이하인 자연수입니다.
▼ 입출력 예
| sizes | result |
|---|---|
| [[60, 50], [30, 70], [60, 30], [80, 40]] | 4000 |
| [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] | 120 |
| [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] | 133 |
▼ 내 풀이
- 우선, 가장 긴 가로와 세로의 길이부터 구하기
- 회전시키는 경우도 고려해야 한다. 만약 최대 세로 길이가 최대 가로길이보다 작다면 회전을 고려하고 이때 다시 한번 최대 세로,가로 길이를 구하고 최대 세로길이가 바뀌었다면 그 때의 최대 세로, 가로 길이로 지갑의 크기를 return하도록 한다.
[오답 코드]
class Solution {
public int solution(int[][] sizes) {
int answer = 0;
int maxw = sizes[0][0];
int maxh = sizes[0][1];
int indexW1 = 0;
int indexH1 = 0;
for(int i = 0; i < sizes.length; i++){
if(sizes[i][0] > maxw){
maxw = sizes[i][0];
indexW1 = i;
}
if(sizes[i][1] > maxh){
maxh = sizes[i][1];
indexH1 = i;
}
}
if(maxh<maxw){
int tempW = sizes[indexH1][1];
int tempH = sizes[indexH1][0];
sizes[indexH1][0] = tempW;
sizes[indexH1][1] = tempH;
} else if(maxh>maxw){
int tempW = sizes[indexW1][1];
int tempH = sizes[indexW1][0];
sizes[indexW1][0] = tempW;
sizes[indexH1][1] = tempH;
}
int maxww = sizes[0][0];
int maxhh = sizes[0][1];
for(int i = 0; i < sizes.length; i++){
if(sizes[i][0] > maxww){
maxww = sizes[i][0];
}
if(sizes[i][1] > maxhh){
maxhh = sizes[i][1];
}
}
if(maxhh != maxh || maxww != maxw){
maxh = maxhh;
maxw = maxww;
}
answer = maxw*maxh;
return answer;
}
}- 위와 같이 작성한 코드는 회전하는 카드가 하나일 때만을 고려한 코드이다.
- 회전할 수 있는 카드가 여러 개일 수 있기 때문에 이 상황도 고려해야한다.
- 이렇게 하나 하나 회전하는 경우를 고려하니까 시간도 너무 오래걸리고 코드가 너무 길어져서 접근 방식에 대해서 처음부터 다시 생각해보았다.
- 임의로 가로가 세로보다 더 길다고 가정하고 접근해보았다.
- 같은 행의 두 값 중 큰 값이 가로가 되고 작은 값이 세로가 된다.
- 그 다음 최대값을 반복문을 통해 갱신하면 된다.
[수정코드]
class Solution {
public int solution(int[][] sizes) {
int answer = 0;
int maxW = 0;
int maxH = 0;
for(int i = 0; i < sizes.length; i++){
int w = Math.max(sizes[i][0], sizes[i][1]);
int h = Math.min(sizes[i][0], sizes[i][1]);
maxW = Math.max(w, maxW);
maxH = Math.max(h, maxH);
}
answer = maxH*maxW;
return answer;
}
}💡 너무 문제에서 나온 방법에 사로잡혀 시간이 오래걸렸던 것 같다.
