[Java] 03/20 알고리즘 문제

1. 프로그래머스 : 짝수는 싫어요

https://school.programmers.co.kr/learn/courses/30/lessons/120813

프로그래머스

풀이 접근법 : n 까지의 홀수를 출력하는 것이므로 짝수일 때는 배열의 크기를 n/2, 홀수일 때는 n/2+1로 잡고 1~n까지

나머지가 1인 수를 배열에 담아 출력한다.

class Solution {
    public int[] solution(int n) {
        int[] answer;
        
        if( n % 2 == 0){
            answer = new int[n/2];
        }else{
            answer = new int[n/2+1];
        }
        
        int idx = 0;
        
        for(int i = 1; i <= n; i++){
            if(i % 2 == 1){
               answer[idx] = i;  
               idx++;
            }            
        }
        return answer;
    }
}

2. 프로그래머스 : 숫자 문자열과 영단어

https://school.programmers.co.kr/learn/courses/30/lessons/81301

프로그래머스

풀이 접근법 : 배열 String[]로 알파벳 String[] alpa = {"zero", "one", "two", "three", "four", "five", "six", "seven","eight", "nine"} 와 같이 넣고, replace 함수를 사용하여 string값을 변경해 출력.

class Solution {
    public int solution(String s) {
        int answer = 0;
        String[] alpa = {"zero", "one", "two", "three", "four", "five", "six", 
                    "seven","eight", "nine"};
        String[] digits = {"0","1","2","3","4","5","6","7","8","9"};
        
        for(int i=0; i<=9; i++){
            
            s = s.replace(alpa[i], digits[i]);
        }
        System.out.print(s);
        answer = Integer.parseInt(s);
        
        return answer;
    }
}

문제를 풀 때에는 String[] digits = {"0","1","2","3","4","5","6","7","8","9"} 대신 replace(alpa[i], i+"") 을 사용하여 string 값을 변경시켜주었는데, 실행 속도가 100배이상 차이가 났다. 알아보니 { +"" } 으로 하는  것은 String 을 새로 만들어 넣는 구조라 시간이 훨씬 많이 든다고 한다.

 

3. 백준 :  괄호

https://www.acmicpc.net/problem/9012

9012번: 괄호

풀이 접근법 : "(" 일 때는 stack에 담고 ")" 일 때는 stack에서 뺸다. stack에서 뺄 "("이 없거나 "("이 아니면 문제에서 요구하는 VPS이 아니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int number = Integer.parseInt(br.readLine());

        for (int i = 0; i < number; i++) {
            String line = br.readLine();
            if (isBalanced(line)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

    private static boolean isBalanced(String line) {
        Stack<Character> stack = new Stack<>();
        for (char c : line.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

4. 백준 : 행성 

https://www.acmicpc.net/problem/2830

2830번: 행성 X3

접근 풀이법 : n개의 숫자를 배열에 담아 각각 XOR 연산을 통해 문제에서 요구하는 친밀도를 계산하고, sum에 하나씩 더해 result를 출력 -> O(n^2) 으로 문제에서 요구하는  (1 ≤ N ≤ 1,000,000) N이 상당히 클 떄 시간 초과로 통과하지 못했다...

오래 생각해봤지만 문제를 풀 수 없어 구글링 시작 -> 아래 코드는 값을 하나씩 받아서 최대값인 1,000,000 < 2^20 이기 때문에 배열의 크기를 20개로 잡아주고, 들어오는 값들을 2진수로 나타내어 각 비트 자리에 갯수를 카운트한다. 

카운트한 1의 개수는 cnt, 이면 0의 개수가 N-cnt 이기 때문에 XOR해서 1이 나오는 1,0이 다를 경우의 수는 Cnt * (N - Cnt) 이기 때문에 비트의 표시 값 2^19 ~ 2^0 (for 0~19)에 cnt * (N-cnt) 값을 해주어 친밀도를 구할 수 있다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[] onecnt = new long[20];
        for (int i = 0; i < N; i++) {
            int v = sc.nextInt();
            int j = 0;
            while (true) {
                if (v / 2 == 0) {
                    onecnt[j]++;
                    break;
                }
                onecnt[j++] += v % 2;
                v /= 2;
            }
        }
        long ans = 0;
        for (int i = 0; i < 20; i++) {
            ans += (1 << i) * (N - onecnt[i]) * onecnt[i];
        }
        System.out.println(ans);
    }
}

아래 코드는 백준 정답자 중에 비트 연산자를 잘 사용해 가져와 보았다. 위 풀이와 같이 각 비트 자리에 1의 개수를 구하는 코드이지만 입력 받은 값 name에 대해 1 << i 쉬프트 연산자를 사용해 1 - > 2 -> 4 - > 8 ... -> 2^19 까지 값을 증가시키면서 & 연산을 사용해 값이 1이면 1, 0이면 0의 카운트를 올린다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] zero = new int[20];
        int[] one = new int[20];
        for (int c = 0; c < N; c++) {
            int name = Integer.parseInt(br.readLine());
            for (int i = 0; i < 20; i++) {
                if ((name & (1 << i)) == 0) zero[i] += 1;
                else one[i] += 1;
            }
        }
        BigInteger acc = new BigInteger("0");
        for (int i = 0; i < 20; i++) {
            BigInteger x1 = BigInteger.valueOf(zero[i]);
            BigInteger x2 = BigInteger.valueOf(one[i]);
            BigInteger x3 = BigInteger.valueOf(1 << i);
            acc = acc.add(x1.multiply(x2).multiply(x3));
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(acc.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

5. 백준 : 개수 세기

https://www.acmicpc.net/problem/10807

10807번: 개수 세기

풀이 접근법 : 배열에 담아서 같은 값이 있으면 count를 올려서 출력한다. O(n)

 

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));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int cnt = 0;

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int target = Integer.parseInt(br.readLine());

        for (int number : arr) {
            if(number == target){
                cnt++;
            }
        }
        System.out.print(cnt);
        br.close();
    }
}