대문자와 소문자가 같이 존재하는 문자열을 입력받아 대문자는 소문자로 소문자는 대문자로
변환하여 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 줄에 문자열이 입력된다. 문자열의 길이는 100을 넘지 않습니다.
문자열은 영어 알파벳으로만 구성되어 있습니다.

▣ 출력설명
첫 줄에 대문자는 소문자로, 소문자는 대문자로 변환된 문자열을 출력합니다.

▣ 입력예제 1

StuDY

▣ 출력예제 1

sTUdy

▣ 생각해둘 것

알파벳을 아스키코드값으로 변환했을 때
소문자: 97 ~ 122
대문자: 65 ~ 90

▣ 풀이

public static void main(String[] args) throws IOException {
    BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    String str = read.readLine();

    char[] tempStr1 = str.toCharArray();
    char[] tempStr2 = str.toLowerCase().toCharArray();
    String result = "";

    for(int i = 0; i < tempStr1.length; i++) {
        if(tempStr1[i] != tempStr2[i]) {
            result += (char)(tempStr1[i] + 32);
        } else {
            result += (char)(tempStr1[i] - 32);
        }
    }

    System.out.println(result);

}

한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개
존재하는지 알아내는 프로그램을 작성하세요. 대소문자를 구분하지 않습니다.
문자열의 길이는 100을 넘지 않습니다.

▣ 입력설명
첫 줄에 문자열이 주어지고, 두 번째 줄에 문자가 주어진다.
문자열은 영어 알파벳으로만 구성되어 있습니다.

▣ 출력설명
첫 줄에 해당 문자의 개수를 출력한다.

▣ 입력예제 1

Computercooler
c

▣ 출력예제 1

2

▣ 풀이

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

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

    char findChar = reader.readLine().toLowerCase().charAt(0); 

    char []tempArr = str.toLowerCase().toCharArray();

    int count = 0;

    for(int i = 0; i < tempArr.length; i++) {
        if(tempArr[i] == findChar) {
            count++;
        }
    }
    System.out.println(count);
}

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예제

phone_bookreturn

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

알림

2019년 5월 13일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

출처

풀이

한 개라도 조건에 맞는 값이 나오면 break 문을 걸었고, 두 번째 for문 만 break 문을 걸면 효율성에서 틀리게 된다. 첫 번째 for문은 끝까지 돌기 때문이다. 그렇기 때문에 첫 번째 for문에도 break 문을 걸어준다.

def solution(phone_book):
    answer = True
    phone_book = sorted(phone_book, key = lambda item: len(item))
    for i in range(len(phone_book)):
        temp = phone_book[i]
        for j in range(i+1, len(phone_book)):
            if temp == phone_book[j][:len(temp)]:
                answer = False
                break
        if answer == False:
            break
    
    return answer

다른 풀이

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer
    

www.acmicpc.net/problem/1004

어린 왕자 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

문제

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.

빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.

위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. (행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.)

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 (cx, cy, r)이 주어진다. 입력제한은 다음과 같다. (-1000 ≤ x1, y1, x2, y2, cx, cy ≤ 1000, 1 ≤ r ≤ 1000, 1 ≤ n ≤ 50)

좌표와 반지름은 모두 정수이다.

출력

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

풀이

cx, cy, r 부분에서 행성이 생길 때마다 그 행성 중점과 도착점의 거리 (d1), 출발점과의 거리 (d2)를 나타낸다. 그리고 한 행성 안에 출발점과 도착점이 동시에 있을 수 있기 때문에 이러한 경우를 제외 하여 if문을 걸어주었다.

case = int(input())

for i in range(case):
    x1, y1, x2, y2 = map(int, input().split())
    a = int(input())
    total = 0
    for j in range(a):
        cx, cy, r = map(int, input().split())
        d1 = ((x1 - cx)**2 + (y1-cy)**2)**0.5
        d2 = ((x2 - cx)**2 + (y2-cy)**2)**0.5
        if(d1 < r and d2 > r) or (d1 > r and d2 < r):
            total += 1
    print(total)

문제

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 x1, y1, r1, x2, y2, r2가 주어진다. x1, y1, x2, y2는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이고, r1, r2는 10,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

풀이

두 점의 거리를 구한 뒤 내접원 외접원을 사용하여 구현했다.

n = int(input())
for i in range(n):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    r = ((x1-x2)**2 + (y1-y2)**2)**(1/2)
    R = [r1, r2, r]
    m = max(R)
    R.remove(m)
    print(-1 if (r == 0 and r1==r2) else 0 if (m > sum(R)) else 1 if (m == sum(R)) else 2)

참고

• velog.io/@adam2/TREE
• gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
• monsieursongsong.tistory.com/6?category=754667

트리

트리란 비선형 구조로 계층 구조이며 그래프의 일종이다. Node와 Edge로 이루어져 있다. 트리는 최소 연결 트리 라고도 불린다.

트리 용어

• Root Node : 트리의 최상위 노드를 칭하며 그림에서는 A의 노드가 해당 된다.
• Node : 트리를 이루는 요소들을 뜻하고 그림에서 A,B,C,D,E,F,G,H,I,J가 이 트리의 노드이다.
• Siblings(형제) : 부모 노드가 같은 노드들을 의미한다. F노드의 형제는 G가 된다.
• Degree(차수) : 각 노드가 가지는 간선의 수를 의미한다. D의 차수는 2 이다.
• Depth(깊이) : Root 노드에서 특정 노드까지 도달하기 위해 거치는 간선의 수.
• Size(크기) : 자신을 포함한 모든 자손 노드의 개수. B의 크기는 5이다.
• Level : 트리에서 각 층별 번호를 매김. Root가 0으로 시작함.
• Height(높이) : 트리의 최고 레벨 (3)

트리의 종류

• Binary Tree - 이진 트리
  • 각 노드가 최대 두 개의 자식을 갖음.
  • 이진 트리 순회로는 중위, 전위, 후위 순회가 있다.
  • 레벨 h의 높이에서 최대 노드 수는 2^h 이다.
  • 깊이가 k의 
• Full Binary Tree  - 전 이진 트리
  • 모든 노드가 0개 또는 2개의 자식 노드를 가진다.
• Complete Binary Tree - 완전 이진 트리
  • 마지막 레벨을 제외하고 모든 레벨의 노드가 완전히 채워져 있다.
  • 완전 이진 트리는 배열을 사용해 효율적 표현이 가능하다.
• BST (Binary Search Tree) - 이진 탐색 트리
  • 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들(모든 노드 n에 대해 반드시 참)
• Balanced binary tree - 균형 이진 트리
  • 모든 잎새 노드의 깊이 차이가 많아야 1인 트리를 의미 함.
  • 한 쪽으로 완전 치우치지 않고 적당한 균형만 이루면 됨.
  • AVL 트리, 레드 블랙 트리가 있음.

트리의 구현 방법

• 인접 배열 구현
  1. 1차원 배열에 자신의 부모 노드만 저장하는 방법.
  2. 이진 트리의 경우, 2차워 배열에 자식 노드를 저장하는 방법.
• 인접 리스트 구현
  1. 가중치가 없는 트리
  2. 가중치가 있는 트리

참고

• ahribori.com/article/5952f94f22eced098cbd8e3c

힙

특징

• 최대값과 최소값을 구하기 위해 사용되며 완전 이진 트리를 따른다.
• 최대 힙과 최소 힙이 있다.
• 최대 힙은 부모가 자식 노드보다 값이 항상 크다.
• 최소 힙은 부조가 자식 노드보다 값이 항상 작다.

참고

• ahribori.com/article/591a5824c686bd0d48e95f47
• woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/

배열(Array)

특징

• 데이터를 물리적 주소에 순차적으로 저장한다.
• 인덱스를 가지고 있기 때문에 인덱스를 알고 있다면 바로 접근이 가능하다. 시간복잡도 O(1)
• 크기가 정해져 있기 때문에 삽입 시 공간이 부족하면 배열을 늘리는 연산을 해야한다.
• 삽입과 삭제 시 모든 데이터를 한 칸씩 앞 뒤로 미뤄야하는 비용이 든다.
• Array가 할당되어 지면 즉시 compile time에 할당된다. 이를 정적 메모리 할당이라 한다.
• Stack 영역에 메모리가 할당된다.

연결 리스트(Linked List)

특징

• 데이터 뿐만 아니라 다음 데이터의 물리적 주소까지 같이 저장한다.
• 단순 연결은 다음 데이터 주소로만 노드를 구성하고, 이중 연결은 전 후 노드로 구성된다.(위 사진은 이중 연결이다)
• 링크를 따라 검색되기 때문에 배열에 비해 접근 속도가 느리다.
• 삽입 삭제 시 해당 위치까지 탐색 후 노드를 노드들 중간에 삽입하거나 노드를 제거하기만 하면 된다.
• 노드 할당 시 runtime에 할당되며 이를 동적 메모리 할당이라 한다.
• Heap 영역에 메모리가 할당된다.

Array Vs LinkedList

# 데이터 접근 속도

Array는 인덱스를 사용하여 바로 접근이 가능하다. 시간 복잡도는 O(1)이다.

LinkedList는 노드가 링크로 연결되어 순차 접근 방식을 사용한다. 그렇기 때문에 첫 노드부터 원하는 노드를 찾을 때까지 진행된다. 시간 복잡도는 O(n)이다.

# 데이터 삽입 삭제 속도

Array는 삽입 시 크기가 부족하다면 늘리는 연산이 필요하며, 삽입과 삭제 시 모든 데이터를 한칸씩 옮겨야 한다. 그렇기 때문에 많은 시간이 걸린다.

LinkedList는 삽입 삭제 할 노드까지 순차적으로 검색 후 해당 위치나 노드를 삽입 삭제하기 때문에 O(n)의 시간이 걸리지만 모든 데이터를 옮길 필요가 없다. 첫 부분과 끝 부분에 데이터 삽입 시 시간 복잡도는 O(1)이다

# 결론

Array는 데이터 접근이 자주 일어나는 경우에 사용한다.

LinkedList는 삽입 삭제가 자주 일어나는 경우에 사용한다.

• Array vs Linked List
• Stack and Queue
• Tree
  • Binary Tree
  • Full Binary Tree
  • Complete Binary Tree
  • BST (Binary Search Tree)
• Binary Heap
• Red Black Tree
  • 정의
  • 특징
  • 삽입
  • 삭제
• Hash Table
  • Hash Function
  • Resolve Collision
    • Open Addressing
    • Separate Chaining
  • Resize
• Graph
  • Graph 용어정리
  • Graph 구현
  • Graph 탐색
  • Minimum Spanning Tree
    • Kruskal algorithm
    • Prim algorithm

www.acmicpc.net/problem/1193

내 코드

# 짝수 일때와 홀수 일때
n = int(input())
i = 1
while i * (i + 1) // 2 < n:
    i += 1
total = i + 1
a = (i * (i + 1)) // 2 - n
if i % 2 != 0:
    print("{}/{}".format(total - i + a , i - a))
else:
    print("{}/{}".format(i - a, total - i + a ))
print(i)

• n(n+1)/2 값이 > 입력 값: 최초로 큰 값을 n에 저장한다.
• 홀수일때와 짝수일 때를 구별하여 값을 구한다.