반응형

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.


N까지의 수중에 소수를 판단하는 상황이 생길 경우 유용하다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void primeNumber(int n){
        // 에라토스테네스의 체
        // N 보다 작은 소수를 구한다.
        boolean[] arr = new boolean[n+1];
        Arrays.fill(arr, true);
        
        for (int i=2; i<=n; i++){
            if (arr[i]){
                
                for (int j=i*i; j<=n; j=j+i){
                    arr[j] = false;
                }
            }
        }
        
        for(int i=0; i<arr.length; i++){
            if (arr[i]){
                System.out.print(i + " " );
            }
        }
    }
cs



참고자료 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4


728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
반응형

문자열에서 첫번째 대문자를 찾아서 출력한다. 

(출처 : http://www.try-cat.ch/contest/view/exercise/70)

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner input = new Scanner(System.in);
  6.        
  7.         String data = input.nextLine();
  8.         char result = ' ';   
  9.         for (int i=0; i=65 && charData <91){
  10.                 result = charData;
  11.                 System.out.println(result);
  12.                 break;
  13.             }
  14.         }
  15.     }
  16. }
입력 : TdfkjslkfjsdkfsdDddf sdkfsl;dfjsdA 
출력 : T



728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
반응형

맬리드네시아(Malidnesia)의 고대 희극인들은 비극보다 희극을 선호한다. 불행히도 고대 연극의 대부분은 비극이다. 따라서, ACM의 드라마 작가는 몇 편의 비극을 희극으로 바꾸기로 결정한다. 극의 모든 것을 반대로 바꿔야 함에도 불구하고 극의 기본 의미를 보존해야 하기 때문에 이 작업이 매우 어렵다는 것은 분명하다. 숫자를 예로 들어보자. 비극에서 어떤 숫자가 나타나면 희극에서 사용하기 전에 이 숫자를 거꾸로 변환해야 한다. 
거꾸로 쓴 숫자(Reversed number)라는 것은 비트 순서를 반대로 하는 것이 아니라 아라비아 숫자를 반대로 쓰는 것을 의미한다. 첫번째 자리가 마지막이 되고, 마지막이 첫번째가 되는 것이다. 예를 들어, 주인공이 비극에서 1245 딸기(1245 strawberries)이면, 희극에서는 5421 딸기가 된다. 자리채움 0은 생략된다. 즉, 0으로 끝나는 숫자를 반전하게 되면 0은 사라진다.(예를 들어, 1200을 바꾸면 21이 된다). 또한, 반전된 숫자는 0으로 끝나는 경우가 없다. 
ACM은 반전한 숫자를 계산해야 한다. 여러분의 작업은 반전한 두 수를 더한 합계를 구하고, 이 합계를 다시 반전하여 출력하는 것이다. 물론, 어떤 숫자들은 순서를 바꿔쓰면 같은 수가 되기 때문에 결과가 항상 유일한(unique) 것은 아니다.(예를 들어, 12, 120, 1200은 바꿔 쓰면 모두 21이 된다) 따라서, 반전했을 경우 0이 사라지는 경우는 없다고 가정해야 한다. (즉, 반전된 수가 21이면 원래 숫자는 12라고 가정하는 것이다)

 

입력

입력은 경우의 수 N이다. 입력의 첫번째 라인은 양의 정수 N만 입력한다. 그 다음에 각 케이스를 입력한다. 각 줄에는 두 개의 정수를 공백으로 구분해서 입력한다. 이 숫자들의 순서를 바꿔서 덧셈을 해야 한다. 숫자는 최대 200자까지 될 수 있다.

출력

각 케이스에 대해서 한 줄에 하나의 정수를 출력한다. 이 정수는 반전한 두 수의 합이다. 출력에서 자리 채움 0은 모두 생략한다

입력예제

3
24 1
4358 754
305 794

출력예제

34
1998
1

  1. import java.io.*;
  2. import java.util.StringTokenizer;
  3. public class AddingReversedNumberMain {
  4.  public static void main(String[] args) throws IOException{
  5.   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  6.   String[][] temp = null;
  7.   int caseNum = 0;
  8.   StringTokenizer st = null;
  9.   int[] sum = null;
  10.   AddingReversedNumber arn = new AddingReversedNumber();
  11.   System.out.print("inout case : " );
  12.   caseNum = System.in.read() - 48;
  13.   System.in.read();
  14.   System.in.read();
  15.  
  16.   temp = new String[caseNum][2];
  17.   sum = new int[caseNum];
  18.  
  19.   for (int i = 0; i < caseNum; i++){
  20.    System.out.print(i + ". caseSet : ");
  21.    String str = in.readLine();
  22.    
  23.    st = new StringTokenizer(str, " " );
  24.    for (int j = 0; j < 2; j++){
  25.     temp[i][j] = st.nextToken();
  26.     sum[i] = sum[i] + arn.reverseNumber(temp[i][j]);
  27.    }
  28.   }
  29.  
  30.   for (int i = 0; i < sum.length; i++){
  31.    System.out.println(arn.reverseNumber(Integer.toString(sum[i])));
  32.   }
  33.  }
  34.  
  35. }
  36. public class AddingReversedNumber {
  37.  public int reverseNumber(String num){
  38.   StringBuffer sb = new StringBuffer();
  39.   String temp = null;
  40.   int len = num.length()-1;
  41.   int number;
  42.  
  43.   for (int i = len; i >= 0 ; i--){
  44.    sb.append(num.charAt(i));
  45.   }
  46.  
  47.   temp = new String(sb);
  48.   number = Integer.parseInt(temp);
  49.   return number;
  50.  }
  51. }

728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Try-catch]대문자 출력  (0) 2013.11.04
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
반응형

After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.

John knows the following: for each index i, where k <= i < n, m[i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.

For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.

John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.

Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).

Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given non-negative integers abc and positive integer r, the known values of m can be calculated as follows:

  • m[0] = a
  • m[i] = (b * m[i - 1] + c) % r, 0 < i < k

Input

The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, nk (1 <= k <= 105k < n <= 109).
The second line of each test case contains 4 space separated integers abcr (0 <= abc <= 109, 1 <= r <= 109).

Output

For each test case, output a single line containing the case number and the nth element of m.


Example input

5
97 39
34 37 656 97
186 75
68 16 539 186
137 49
48 17 461 137
98 59
6 30 524 98
46 18
7 11 9 46

Example output
Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12

728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
반응형
흠... 왜 이렇게 생각을 못했을까

Balanced Smileys

Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(

Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.

A message has balanced parentheses if it consists of one of the following:

  • - An empty string ""
  • - One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
  • - An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
  • - A message with balanced parentheses followed by another message with balanced parentheses.
  • - A smiley face ":)" or a frowny face ":("

Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Input

The first line of the input contains a number (1 ≤ T ≤ 50), the number of test cases. 
The following T lines each contain a message of length s that you got from John.

Output

For each of the test cases numbered in order from 1 to T, output "Case #i: " followed by a string stating whether or not it is possible that the message had balanced parentheses. If it is, the string should be "YES", else it should be "NO" (all quotes for clarity only)

Constraints

  • 1 ≤ length of s ≤ 100

Example input
5
:((
i am sick today (:()
(:)
hacker cup: started :):)
)(

Example output
Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO

  1. public class BalancedSmileys {
  2.     public static void main(String[] args) {
  3.         try {
  4.             BufferedReader in = new BufferedReader(new FileReader("src/code/smile.txt"));
  5.             String lineData;
  6.             int lineNumber = 0;
  7.                        
  8.             while ((lineData = in.readLine()) != null) {
  9.                
  10.                 if (lineNumber >= 1){
  11.                     char[] charData = lineData.toCharArray();
  12.                     int parenthesisOpenCount = 0;
  13.                     int parenthesisCloseCount = 0;             
  14.                        
  15.                     String result = "YES";
  16.                    
  17.                     for(int i=0; i<charData.length; i++){
  18.                         char data = charData[i];
  19.                         char preData = ' ';
  20.                        
  21.                         if (i > 0){
  22.                             preData = charData[i-1];
  23.                         }
  24.                                                
  25.                         if (data == '('){                  
  26.                             parenthesisOpenCount++;
  27.                            
  28.                             if (i > 0 && preData != ':'){
  29.                                 parenthesisCloseCount++;
  30.                             }
  31.                         }else if (data == ')'){
  32.                             parenthesisCloseCount = Math.max(0, parenthesisCloseCount-1);
  33.                            
  34.                             if (i > 0 && preData != ':'){
  35.                                 parenthesisOpenCount--;
  36.                                
  37.                                 if (parenthesisOpenCount < 0){
  38.                                     break;
  39.                                 }
  40.                             }
  41.                         }
  42.                     }
  43.                    
  44.                     if (parenthesisOpenCount >= 0 && parenthesisCloseCount == 0 ){
  45.                         result = "YES";
  46.                     }else{
  47.                         result = "NO";
  48.                     }
  49.                    
  50.                    
  51.                     System.out.println("Case #" + lineNumber + ": " + result);
  52.                 }
  53.                 lineNumber++;
  54.             }
  55.             in.close();
  56.         } catch (IOException e) {
  57.             System.err.println(e);
  58.             System.exit(1);
  59.         }
  60.     }
  61. }


728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01
반응형

정수 n에서 시작해 n이 짝수면 2로 나누고 홀수면 3을 곱한 다음 1을 더한다.
이렇게 해서 새로 만들어진 숫자를 n으로 놓고 n=1이 될때까지 같은 작업을 반복한다.
1이 나올때까지 만들어진 수의 개수(1포함)를 n의 사이클 길이라고 한다.

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
22의 사이클은 16


입력 
- 입력은 일련의 정수 쌍 i와 j로 구성되며 한 줄에 한쌍의 수가 입력된다. 모든 정수는 1,000,000보다 작고 0보다 크다

출력
- i, j를 입력된 순서대로 출력
- i, j의 최대 사이클 길이 출력 

입력 예          출력 예
1  10            1 10 20
100 200       100 200 125
210 210        201 210 89 

풀이) 풀긴 했는데  http://www.programming-challenges.com 들어가서 돌려보면 계속 틀렸다고 나온다 -_-;;젠장 . 뭐가 문제야

  1. import java.io.*;
  2.  
  3. class Main implements Runnable{
  4.     static String ReadLn(int maxLength){  // utility function to read from stdin,
  5.                                           // Provided by Programming-challenges, edit for style only
  6.         byte line[] = new byte [maxLength];
  7.         int length = 0;
  8.         int input = -1;
  9.         try{
  10.             while (length < maxLength){//Read untill maxlength
  11.                 input = System.in.read();
  12.                 if ((input < 0) || (input == ' ')) break//or untill end of line ninput
  13.                 line [length++] += input;
  14.             }
  15.  
  16.             if ((input < 0) && (length == 0)) return null;  // eof
  17.             return new String(line, 0, length);
  18.         }catch (IOException e){
  19.             return null;
  20.         }
  21.     }
  22.  
  23.     public static void main(String args[])  // entry point from OS
  24.     {
  25.         Main myWork = new Main();  // Construct the bootloader
  26.         myWork.run();            // execute
  27.     }
  28.  
  29.     public void run() {
  30.         new MyStuff().run();
  31.     }
  32. }
  33.  
  34. class MyStuff implements Runnable{
  35.     public void run(){
  36.             String input = (Main.ReadLn(20));
  37.             calcCycle(input);       
  38.     }
  39.    
  40.     // You can insert more classes here if you want.
  41.    
  42.     public void calcCycle(String input){
  43.         String[] inputArray     = input.trim().split(" ");
  44.         int startInput    = Integer.parseInt(inputArray[0]);
  45.         int endInput          = Integer.parseInt(inputArray[1]);
  46.         int maxCount            = 0;
  47.         int maxNumber         = 0;
  48.        
  49.         if (startInput > endInput){
  50.             int temp    = endInput;
  51.             endInput        = startInput;
  52.             startInput  = temp;
  53.         }
  54.                
  55.         while(startInput <= endInput){    
  56.             int count      = 1;             
  57.             int number   = startInput;
  58.            
  59.             if (number != 1){
  60.                 while (number > 1){
  61.                     if (number % 2 == 0){
  62.                         number = number /2;
  63.                     }else {        
  64.                         number = number * 3 + 1;           
  65.                     }
  66.                     count++;
  67.                 }             
  68.             }
  69.  
  70.             if (maxCount < count){
  71.                 maxCount    = count;
  72.             }
  73.             startInput++;
  74.         }
  75.  
  76.         System.out.println( inputArray[0] + " " + inputArray[1] + " " + maxCount);
  77.     }
  78.    
  79. }


728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

에라토스테네스의 체  (0) 2016.12.07
[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31

+ Recent posts