냥냥개발펀치

이 문제는.... 쉬울 거 같은데 은근 생각이 안났다. 처음 문제를 읽었을 때 내가 눈으로 보면 당연히 바로 구할 수 있지만 이걸 어떻게 코드로 구현하지..? 이런 생각이 들었다.

 이 문제는 '벌집' 자체가 핵심이다. 육각형으로 이루어진 것에서 규칙을 생각해 그대로 구현하면 되는 문제다. 1을 중심으로 주변을 둘러쌀 때 2칸, 3칸 등 칸이 증가할수록 둘러싸는 개수는 6개씩 증가한다. 이걸 생각해내는 게 첫 번째 포인트이다.

 두 번째로 막혔던 부분이다. 처음엔 수열공식을 생각해 

1 : 1칸

2~7 : 2칸

8~19 : 3칸

20~37 : 4칸

.

.

.

이런 식으로 경계값을 이용해 해당 범위 내에 있으면 칸을 구하게끔 로직을 짜서 했다. 하지만 어째서인지 채점 마지막 100% 직전에 틀렸습니다 하고 오답처리가 됐다. 아무리 생각해도 이해가 안되서 그럼 1,7,19,37 ... 등 구간의 마지막 수를 이용해 칸의 개수를 구해보자 라고 생각이 들어 로직을 짜보았다. 난 왜 여기서 공식을 생각해내는 데 오래걸렸을까? 바보 멍청이이기 때문이다.

마지막 수를 기억해 다음에 더해주면 되는데 이걸 생각못해서 조금 생각하는 시간이 길었다.  첫번째 방법으로 풀었을 때보다 훨씬 로직이 간단해서 이 방법을 채택했다. 결국 문제를 풀었고 또 하나의 교훈점을 얻어가는 문제였다.

(역시 아직도 알고리즘 문제풀 때 뭔가 불안?해서 그런지 뇌가 굳는다. 왜 생각이 안나지 이상하다.) 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int prev = 1;

if(num == 1) {
System.out.println("1");
return;
}
int n=1;
while(true) {
int pNum = 6*n + prev;
if(num <= pNum) {
System.out.println(n+1);
break;
}else {
prev = pNum;
}
n++;
}

}


}

이 문제를 풀면서 다시 한 번 새기고 간 개념 네 가지.

int의 범위는  -21억~21억까지이다.

제한 시간이 1초 미만이고 숫자가 크다면 반복문으로 해결할 수 없다.

BufferedReader의 개념

StringTokenizer의 사용

BufferedReader는 버퍼를 이용하는 대표적인 i/o 클래스이다.

스페이스와 엔터 둘 다 경계값으로 인식하는 Scanner와 다르게 엔터만을 경계값으로 인식한다.

또한 버퍼가 가득 차거나 엔터값이 들어왔을 때까지 입력값을 버퍼에 저장해뒀다 한 번에 전송한다. 입력값이 많이 않을 때는 Scanner와 속도 차이가 별로 없지만 값이 많아질수록 속도, 성능 면에서 BufferedReader가 훨씬 효율적이다.

BufferedReader로 입력받을 때 한 줄로 입력받고 공백으로 값을 구분할 때 StringTokenizer를 이용하는 것이 좋다. 단지 공백만을 없애고 값을 바로바로 인식하기 때문에 내부적으로 복잡한 split보다 훨씬 속도가 빠르다. (물론 구분자 설정을 아무것도 안해주었을 때 공백을 구분자로 인식한다는 말이다.) split은 인덱스로 접근해야 될 때 사용하면 훨씬 효율적이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

public static void main(String[] args) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());
int fix = Integer.parseInt(st.nextToken());
int variable = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());


if(price <= variable) {
System.out.println("-1");
}else {
System.out.println(fix/(price - variable) + 1);
}

}


}

 이 문제 풀때는 '손익분기점'에 대해 좀 알아야했던 거 같다. 그리고 입력값의 범위가 크기 때문에 일일이 반복문으로 합계를 구해서 하면 시간초과로 틀린다. 그래서 위와 같은 방법으로 풀었다.

 단순한 개념을 이용한 문제인데 흠칫 했던 거 같다. 정신 차려!!!!!!!!!

이 문제를 풀 때 로직을 제대로 생각하지 못했다. 

아스키코드값을 이용, 함수로 구현, 연속된 문자인지 알기 위해 prev 변수 사용하는 것 까지 생각하지 못해 문제 푸는데 애를 먹었다.

 처음엔 문자열 인덱스로 접근해야하나 싶었는데 아무리 생각해도 적절한 로직이 떠오르지 않았고 자꾸 산으로 가는 느낌이었다.

 두 번째로는 함수로 처리할 생각을 못해서 반복문을 몇 개씩이나 계속 사용해야 되는 거 같아 시간복잡도가 너무 커져 적절하지 않다는 생각을 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;



public class Main {

    static BufferedReader br;
    static int number;

    public static void main(String[] args) throws IOException {

          br = new BufferedReader(new InputStreamReader(System.in));
          number = Integer.parseInt(br.readLine());

          int count = 0;
          for(int i=0;i<number;i++) {
              if(check()) {
                 count++;
              }
          }

         System.out.println(count);

   }

   public static boolean check() throws IOException {

        boolean[] check = new boolean[26];
        String st = br.readLine();

        char prev = ' ';
        for(char c : st.toCharArray()) {
           if(check[c - 'a']){
             if(prev == c) {
                continue;
             }else {
                return false;
             }

           }else {
               check[c - 'a'] = true;
               prev = c;
          }
       }

       return true;
    }
}

문자열 문제를 많이 안풀었더니 확실히 많이 까먹은 거 같다는 생각이 들었다. 또 알고리즘 문제 풀 때는 뭐랄까. 머리가 좀 굳는 느낌이다. 알고리즘 문제를 푼다하면 일단 겁부터 먹어서 그런 거 같기도하다.. 그래서 생각이 잘 안난다.

 계속 꾸준히 풀어서 무서움을 좀 없애야겠다.

문자열 문제인 2941 문제를 풀어보았다. 

처음엔 문제를 읽고 출력인 '몇 개의 크로아티아 알파벳으로 이루어져 있는지' 이 부분을 '몇 가지 종류의 크로아티아 알파벳' 인지라고 이해하고 문제를 풀었던 것 같다. 그래서 중복인 경우를 제외해줘야 되겠다고 생각했고 HashMap을 이용해서 풀었다. 

Map<String, Integer> maps = new HashMap<>();

maps.put("c=", 0);
maps.put("c-", 0);
maps.put("dz=", 0);
maps.put("d-", 0);
maps.put("lj", 0);
maps.put("nj", 0);
maps.put("s=", 0);
maps.put("z=", 0);

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;

str = br.readLine();
for(String key : maps.keySet()) {

if(str.contains(key)) {
maps.put(key, maps.getOrDefault(key, 0) + 1);
str = str.replace(key, "");
}
}

int sum = 0;
for(String key : maps.keySet()) {
sum += maps.get(key);
}
sum += str.length();
System.out.println(sum);

이 생각이 잘못되서 예제 입력 4도 틀렸었고, 예제 입력 5도 틀려서 의문을 갖기 시작했다.

print로 일일이 찍어보니 예제 입력 5인 "dz=ak"에서 keySet()으로 key값 하나씩 비교하는데 순서가 가장 마지막인 z=, dz=, 이 순서대로 key가 뽑혀나와 비교할 때 dz=를 제외해야하는데 z=을 먼저 제외해버려서 결과 출력이 틀리게 나왔던 것이다. 

 여기서 다시한번 알게 된 개념이 Set은 List와 다르게 순서가 지켜지지 않기 때문에 keySet()이나 iterator()로 접근할 때도 순서가 저장 순서와 동일하지 않다는 것이다.

 그래서 두 개의 의문점이 생겼다. 첫 번째는 그럼 Hash의 접근 순서를 내가 지정할 수 없는 것인가, 순서를 출력해보았을 때 할 때마다 달라지는 것은 아니던데 그렇다면 랜덤으로 순서가 정해지는 것인가? 였다. 두 번째는 예제 입력 5에서 과연 dz= 이 알파벳을 d와 z=으로 볼 것인지, 하나의 dz=으로 볼 것인지 기준이 뭔가 라는 것이었다.

 두 번째 의문점은 내가 문제를 제대로 읽지 않아서 생겨난 의문점이었다. 역시 문제에 나온 내용은 괜히 나오는 내용, 조건이 아니다. 분명히 해결하는데 필요한 조건들이니 꼼꼼하게 읽을 필요가 있다는 깨달음을 주게 된 의문점이었다. 

 첫 번째 의문점은 아직도 완전하게 의문을 해소하지 못했다. key를 정렬해주면 원하는 순서대로 나올까 했는데 그것도 아닌거 같다. Hash에 대해 다시 자세하게 공부를 해야할 것 같다.

 그래서 결론은 다른 방법을 생각해내는 것이었다. 중복을 제외하는 것이 아니라 사용된 알파벳 개수를 구하면 되니까 Hash를 안쓰고 그냥 문자열 배열을 이용해 해결하면 될 것 같았다. 

String[] arr = {"c=","c-", "dz=", "d-", "lj", "nj", "s=", "z="};


BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;

str = br.readLine();

for(String s : arr) {
if(str.contains(s)) {
str = str.replaceAll(s, " ");

}
}

System.out.println(str.length());

  입력받은 문자열이 해당 배열 값을 포함하고 있으면 공백으로 바꿔준 뒤 문자열의 길이만 구하면 된다.

  ('공백으로 바꿔준다' : 되게 간단한 방법인데 은근 생각해내기 힘들다. 문제를 많이 풀다 보면 이런 센스가 생길려나?)

 이렇게 간단하게 해결할 수 있는 문제를 문제를 잘못 읽고 이해해서 한참을 돌아 헤맸다. 앞으론 문제를 꼼꼼하게 잘 읽어야겠다.