목차
▸ 괄호 회전하기
▸ 연속 부분 수열의 합의 개수
💡괄호 회전하기 : Lv.2
▼ 문제
출처: 프로그래머스 코딩테스트 연습 > 월간 코드 챌린지 시즌2 > 괄호 회전하기
▼ 내 풀이
- Stack을 활용하고자 했다. stack을 활용하여 해당 괄호 문자열이 올바른 문자열이면 true, 아니면 false를 반환하는 메서드를 만들었다.
- 또한, 문자열에 있는 문자를 왼쪽으로 한칸씩 이동시키는 메서드를 만들었다.
- 괄호 별 stack을 만들어서 문제에 접근했다.
[오답 코드]
import java.util.*;
class Solution {
public int solution(String s) {
int answer = 0;
//문자열 바꾸기
for(int i = 0; i < s.length(); i++){
boolean result = isCorrected(s);
if(result == true){
answer++;
}
String newstring = move(s);
s = newstring;
}
return answer;
}
public boolean isCorrected(String s){
Stack st1 = new Stack();
Stack st2 = new Stack();
Stack st3 = new Stack();
for(char c : s.toCharArray()){
if(c == '('){
st1.push(c);
}else if(c == '{'){
st2.push(c);
}else if(c == '['){
st3.push(c);
}else if(c == ')'){
if(st1.size() == 0){
return false;
}
st1.pop();
}else if(c == '}'){
if(st2.size() == 0){
return false;
}
st2.pop();
}else if(c == ']'){
if(st3.size() == 0){
return false;
}
st3.pop();
}
}
if(st1.size() == 0 && st2.size() == 0 && st3.size() == 0){
return true;
} else{
return false;
}
}
public String move(String s){
char[] chars = s.toCharArray();
char firstChar = chars[0]; // 저장 후 이동시킬 문자열의 첫 번째 문자
// 문자열을 왼쪽으로 이동
for (int i = 0; i < chars.length - 1; i++) {
chars[i] = chars[i + 1];
}
// 마지막 문자는 처음 문자로 대체
chars[chars.length - 1] = firstChar;
return new String(chars);
}
}- 코드를 돌렸더니 마지막 14번 테스트 케이스에서만 실패가 떴다.
- "([{)}]" 이러한 경우 실제 정답은 0이지만 내가 작성한 코드에의해서는 1이 나온다.
- 문제를 다시 보니 위와 같은 방식으로 푸는 것은 그냥 괄호를 열고 닫는 것에 대해서이고 문제는 괄호 안이 올바른 괄호 문자열이어야 올바른 괄호 문자열이 되는 것이다.
- 따라서, 한 스택안에 괄호가 여는 괄호면 스택에 넣고 닫는 괄호일 때 스택안에 괄호가 존재하는 경우 pop하면 나오는 여는 괄호와 현재 닫는 괄호가 일치할 경우 다음 반복으로 넘어가게 했다.
[수정 코드]
import java.util.*;
class Solution {
public int solution(String s) {
int answer = 0;
//문자열 바꾸기
for(int i = 0; i < s.length(); i++){
boolean result = isCorrected(s);
if(result == true){
answer++;
}
String newstring = move(s);
s = newstring;
}
return answer;
}
public boolean isCorrected(String s){
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
st.push(s.charAt(i));
} else {
if (!st.isEmpty()) {
char c = st.pop();
char a = s.charAt(i);
if(c == '(' && a == ')') {
continue;
}else if(c == '{' && a == '}') {
continue;
}else if(c == '[' && a == ']') {
continue;
}else {
return false;
}
} else {
return false;}
}
}
if(st.isEmpty()) {
return true;
} else {
return false;
}
}
public String move(String s){
char[] chars = s.toCharArray();
char firstChar = chars[0]; // 저장 후 이동시킬 문자열의 첫 번째 문자
// 문자열을 왼쪽으로 이동
for (int i = 0; i < chars.length - 1; i++) {
chars[i] = chars[i + 1];
}
// 마지막 문자는 처음 문자로 대체
chars[chars.length - 1] = firstChar;
return new String(chars);
}
}💡연속 부분 수열 합의 개수 : Lv.2
▼ 문제
출처: 프로그래머스 코딩테스트 연습 > 연습문제 > 연속 부분 수열 합의 개수
▼ 내 풀이
- 주어진 배열이 [7,9,1,1,4] 일때, [7,9,1,1,4,7,9,1,1]로 만든다. 즉, 마지막 숫자를 제외하고 주어진 배열에 같은 배열을 더한다.
[오답 코드]
import java.util.*;
class Solution {
public int solution(int[] elements) {
int answer = 0;
int lastNum = elements[elements.length - 1]; // 마지막 숫자 저장
int[] result = new int[2*(elements.length) - 1];
List<Integer> sumList = new ArrayList<>();
// 기존 배열 복사
System.arraycopy(elements, 0, result, 0, elements.length);
// 두 번째 부분 붙이기
System.arraycopy(elements, 0, result, elements.length, elements.length - 1);
int count = 1;
for(int i = 1; i <= elements.length; i++){
for(int j = 0; j < elements.length; j++){
int sum = 0;
for(int k = j; k < j+count; k++){
sum += result[k];
if(!sumList.contains(sum)){
sumList.add(sum);
}
}
}
count++;
}
return sumList.size();
}
}- 작성한 코드를 돌렸더니 하나의 테스트 케이스 제외하고는 다 시간초과가 떴다.
- 시간을 줄이기 위해 sum을 List가 아니라 HashSet에 저장하기로 했다.
- 또한, 기존의 배열을 복사하는 부분이 불필요한 과정이었다.
- 따라서 % 연산자를 활용하여 인덱스를 조정하여 원형 배열 처럼 접근하고자 했다.
[수정 코드]
import java.util.HashSet;
import java.util.Set;
class Solution {
public int solution(int[] elements) {
Set<Integer> sumSet = new HashSet<>();
//부분 배열의 길이 len
for(int len = 1; len <= elements.length; len++){
//시작지점 start
for(int start = 0; start < elements.length; start++){
int sum = 0;
//sum 구하기
for(int i = 0; i < len; i++){
sum += elements[(start + i) % elements.length];
}
sumSet.add(sum);
}
}
return sumSet.size(); // 고유 합계의 개수 반환
}
}
▼ 알게된 점
- 인덱스에서 원형 순환처럼 하고 싶을 때 접근 하고자하는 인덱스를 크기나 길이로 나누면 된다.
안녕하세요